37478

Метод мурашиних колоній

Лабораторная работа

Информатика, кибернетика и программирование

Технічне завдання Розробити програму що здійснює пошук оптимального шляху між двома клітинками ігрового поля яке являє собою двовимірну матрицю клітинок заданого розміру. Пошук шляху повинен здійснюватись за допомогою алгоритму мурашиної колонії параметри алгоритму повинні налаштовуватись користувачем вручну. Пізніше список використовується для визначення довжини шляху між вузлами. Справжня мураха під час переміщення по шляху залишає за собою деяку кількість феромону.

Украинкский

2013-09-24

235.5 KB

36 чел.

Міністерство освіти і науки України

Житомирський державний технологічний університет

Кафедра ПЗОТ

Група АК-27М

Курсова робота

з предмету “Інтелектуальні агенти”

на тему:

«Метод мурашиних колоній»

Виконав:          Лабенський В .В.

Перевірив:          Скачков В. О.

Житомир

2009

Зміст

[1] Зміст

[2]
Вступ

[3]
Технічне завдання

[4]
Теоретичні відомості

[4.1] Основні поняття

[4.2] Виконання алгоритму

[5]
Керівництво користувача

[6]
Керівництво розробника

[7]
Висновок

[8]
Література

  1.  
    Вступ

Природні обчислення (анг. «Natural computation») – напрямок досліджень в комп‘ютерних науках, джерелом натхнення для яких є природа і природні системи. Мета таких досліджень – розробка нових засобів обчислень (програмних чи апаратних) для розв‘язання комплексних, складних за умовами задач. Це часто приводить до використання природніх шаблонів поведінки організмів і, в результаті, випливає в розробку обчислювальних систем, що використовують для обчислень прототипи з живої природи.

Розрізняють три основні напрямки природніх обчислень:

• Обчислення, що навіяні природою: використання природи, як джерела натхнення для розробки рішень комплексних і складних задач.

• Симуляція і емуляція природи обчислювальними засобами: в основному, це процес синтезу шаблонів, форм, поведінок і організмів, що мають спільні риси із «справжнім» життям. Такі продукти використовують для відтворення різних природніх феноменів, таким чином покращуючи наше розуміння природи і глибини комп‘ютерного моделювання.

• Обчислення із використанням природніх матеріалів: це означає використання природніх агентів для здійснення обчислень, що є найбільш правильною паратигмою для сучасної техніки на основі кремнію.

У останні два десятиліття для оптимізації складних систем дослідники все частіше застосовують природні механізми пошуку найкращих рішень. Ці механізми забезпечують ефективну адаптацію флори і фауни до довкілля впродовж мільйонів років. Сьогодні інтенсивно розробляється науковий напрям Natural Computing — «Природні обчислення», що об'єднує методи оптимізації складних систем з природними механізмами ухвалення рішень, а саме:

• Genetic Algorithms — генетичні алгоритми;

• Evolution Programming — еволюційне програмування;

• Neural Network Computing — нейромережеві обчислення;

• DNA Computing — ДНК- обчислення;

• Cellular Automata — клітинні автомати;

• Ant Colony Algorithms — мурашині алгоритми.

Розглянемо приклад практичного вживання мурашиних алгоритмів - нового перспективного методу оптимізації, поведінки колонії мурашок, що базується на моделюванні. Колонія мурашок може розглядатися як багатоагентна система, в якій кожен агент (мурашка) функціонує автономно у відповідності з дуже простими правилами. На противагу майже примітивній поведінці агентів, поведінка всієї системи виходить на подив розумною. Мурашині алгоритми серйозно досліджуються європейськими ученими з середини 90-х років. На сьогодні вже отримані хороші  результати мурашиної оптимізації таких складних комбінаторних завдань, як: завдання комівояжера, завдання оптимізації маршрутів вантажівок, завдання розфарбовування графа, квадратичного завдання про призначення, оптимізації мережевих графіків, завдання календарного планерування і інших. Не дивлячись на стрімкі успіхи мурашиних алгоритмів, переважна більшість російськомовних фахівців з дослідження операцій не знайома з цією технологією оптимізації.

  1.  
    Технічне завдання
  2.  Розробити програму, що здійснює пошук оптимального шляху між двома клітинками ігрового поля, яке являє собою двовимірну матрицю клітинок заданого розміру.
  3.  Користувач повинен мати можливість задавати початкову і кінцеву клінтинки, а також позначати «непрохідні» клітинки, що являють собою перешкоди. Програма повинна шукати оптимальний шлях, що не перетинає клітинки-перешкоди.
  4.  Пошук шляху повинен здійснюватись за допомогою алгоритму мурашиної колонії, параметри алгоритму повинні налаштовуватись користувачем вручну.
  5.  Результат (оптимальний шлях від початкової до кінцевої клітинки) має бути виведено на екран в графічному вигляді.
  6.  
    Теоретичні відомості
    1.  Основні поняття

Мурашині алгоритми серйозно досліджуються європейськими вченими із середини 1990-х років. На сьогоднішній день вже отримано гарні результати для оптимізації таких складних комбінаторних задач, як задача комівояжера, задача оптимізації маршрутів вантажівок, задача розфарбування графа, квадратична задача про призначення, задача оптимізації сіткових графіків, задача календарного планування і т. ін. Особливо ефективні мурашині алгоритми при динамічній оптимізації процесів у розподілених нестаціонарних системах, наприклад, трафіків у телекомунікаційних мережах.

Метод мурашиних колоній заснований на взаємодії декількох мурах (програмних агентів, що є членами великої колонії) і використовується для вирішення різних оптимізаційних задач. Агенти спільно вирішують проблему й допомагають іншим агентам у подальшій оптимізації розв’язку.

Методи мурахи (Ant algorithms), або оптимізація за принципом мурашиної колонії, мають специфічні особливості, властиві мурахам, і використовують їх для орієнтації у фізичному просторі. Природа пропонує різні методики для оптимізації деяких процесів. Методи мурашиних колоній особливо цікаві тому, що їх можна використовувати для вирішення не тільки статичних, але й динамічних задач, наприклад, задач маршрутизації в мінливих мережах.

Базова ідея методу мурашиних колоній полягає у вирішенні оптимізаційної задачі шляхом застосування непрямого зв'язку між автономними агентами.

У методі мурашиних колоній передбачається, що навколишнє середовище являє собою закриту двовимірну мережу – групу вузлів, з'єднаних за допомогою граней. Кожна грань має вагу, що позначається як відстань між двома вузлами, з'єднаними нею. Граф – двонаправлений, тому агент може подорожувати по грані в будь-якому напрямку.

Агент забезпечується набором простих правил, які дозволяють йому вибирати шлях у графі. Він підтримує список табу – список вузлів, які він вже відвідав. Таким чином, агент повинен проходити через кожний вузол тільки один раз.

Вузли в списку “поточної подорожі” табу розташовуються в тому порядку, у якому агент відвідував їх. Пізніше список використовується для визначення довжини шляху між вузлами.

Справжня мураха під час переміщення по шляху залишає за собою деяку кількість феромону. У методі мурашиних колоній агент залишає феромон на гранях мережі після завершення подорожі.

  1.  Виконання алгоритму

Метод мурашиних колоній виконується в наступній послідовності кроків.

Крок 1. Задати параметри методу: α – коефіцієнт, що визначає відносну значимість шляху (кількість феромона на шляху); β – параметр, що означає пріоритет відстані над кількістю феромона; ρ – коефіцієнт кількості феромона, що агент залишає на шляху, де (1-ρ) показує коефіцієнт випару феромона на шляху після його завершення; Q – константу, що відноситься до кількості феромона, яку було залишено на шляху.

Крок 2. Ініціалізація методу. Створення популяції агентів. Після створення популяція агентів розміщується у стартовому вузлі графу.

Крок 3. Рух агентів. Якщо агент ще не закінчив шлях, тобто не відвідав кінцевий вузол мережі, для визначення наступної грані шляху використовується формула:

де J – множина граней, ще не відвіданих агентом; – інтенсивність феромона на грані між вузлами r і u, які утворять k-у грань, у момент часу t;    – функція, що представляє собою зворотну величину відстані грані.

Агент подорожує тільки по вузлах, які ще не були відвідані ним, тобто по вузлах, яких немає у списку табу. Тому ймовірність розраховується тільки для граней, які ведуть до ще не відвіданих вузлів.

Крок 4. Пройдений агентом шлях відображається, коли агент дійде до кінцевого вузла маршруту. Цикли заборонені, оскільки в метод включений список табу. Після завершення може бути розрахована довжина шляху. Вона дорівнює сумі довжин всіх граней, по яких подорожував агент. Кількість феромону, що було залишено на кожній грані шляху i-го агенту, визначається за формулою:

де – довжина шляху i-го  агенту.

Результат є засобом вимірювання шляху: короткий шлях харак-теризується високою концентрацією феромону, а більш довгий шлях -більш низькою. Потім отриманий результат використовується для збільшення кількості феромону уздовж кожної грані пройденого i- им агентом шляху:

де r, u – вузли, що утворюють грані, які відвідав i-ий агент.

Дана формула застосовується до всього шляху, при цьому кожна грань позначається феромоном пропорційно довжині шляху. Тому варто дочекатися, поки агент закінчить подорож і тільки потім оновити рівні феромону, у противному випадку дійсна довжина шляху залишиться невідомою. Константа ρ приймає значення між 0 і 1.

Тому для випаровування феромону використовується зворотний коефіцієнт відновлення шляху (1-р).

Крок 5. Перевірка на досягнення оптимального результату. Перевірка може виконуватися для постійної кількості шляхів. Якщо перевірка дала позитивний результат, то відбувається закінчення роботи методу (перехід до кроку 7), у протилежному випадку – перехід до кроку 6.

Крок 6. Повторний запуск. Після того як шлях агента завершений, грані оновлені відповідно до довжини шляху, й відбулося випаровування феромону на всіх гранях, метод виконується повторно. Список табу очищується, і довжина шляху анулюєтся. Після цього виконується перехід до кроку 3.

Крок 7. Кінець. Визначається кращий шлях, що і є розв’язком.

  1.  
    Керівництво користувача

Після запуску програми на екрані з’являється головне вікно програми.

Рис. . Головне вікно програми

У лівій частині вікна знаходиться панель «Налаштування». В верхній частині панелі задається розмір ігрового поля і за допомоги кнопки «Створити» поле генерується і відображається у правій частині вікна.

Нижче в налаштуваннях користувач може вибрати тип клітинки і розмістити ці клітинки на полі, використовуючи натискання лівої клавіші миші на відповідній клітинці поля. Варто пам‘ятати, що на полі не можуть бути присутні одночасно більш ніж одна стартова клітинка або більш ніж одна фінішна клітинка.

Також, користувач має можливість вводити всі параметри алгоритму в нижній частині панелі «Налаштування».

В правій частині вікна відображається ігрове поле. Стартова та фінішна клітинки на полі позначаються зеленим кольором і літерами «С» та «Ф», відповідно. Першкоди позначені чорним кольором.

Після натискання кнопки «Вперед!» запускається алгоритм пошуку, результат якого виводиться згодом у маленькому вікні.

Рис. . Довжина оптимального шляху в модальному вікні

Сам оптимальний шлях рисується в головному вікні програми; клітинки, що входять в цей шлях позначаються рожевим кольором і нумеруються, починаючи з фінішної і закінчуєюи стартовою клітинкою.

Рис. . Зображення оптимального шляху у головному вікні програми

  1.  
    Керівництво розробника

Програма Ant Colony Optimization була написана мовою C# з використанням платформи .NET версії 3.5, скомпільована в середовищі MS Visual Studio 2008 відповідним компілятором. Програма являє собою Windows Forms Application (додаток на основі вікон). Програма була спроектована із використанням об‘єктно-орієнтованого підходу у програмуванні.

Нижче, на  наведено діаграму класів програми:

Головний клас, який інкапсулює всю роботу алгоритму – AntColony. Робота клієнтського коду з цим класом здійснюється за допомогою методу Process. Цей метод виконує всю роботу алгоритму. Перед його викликом обов‘язково потрібно ініціалізувати екземпляр класу AntColony за допомоги конструктора і задати всі праметри алгоритму, такі як:

AntColony.Alpha – коефіцієнт, що визначає відносну значимість шляху (кількість феромона на шляху), число з плаваючою точкою від 0 до 1.

AntColony.Beta – параметр, що означає пріоритет відстані над кількістю феромона, дорівнює (1-AntColony.Alpha).

AntColony.Ro – коефіцієнт кількості феромона, що агент залишає на шляху, число з плаваючою точкою від 0 до 1.

AntColony.Q – константа, що відноситься до кількості феромона, яка була залишена на шляху, ціле число від 1 до 1000000.

Також, перед викликом методу Process, необхідно створити і проініціалізувати екземпляр класу Field. Цей клас містить список клітинок Cells, що використовується в об‘єкті AntColony. Клас Field представляє програмну модель графа, що заданий на вході, і в якому необхідно знайти оптимальний шлях між заданими вершинами.

Після виклику методу Process об‘єкта AntColony оптимальний шлях буде зберігатись у вигляді списку індексів вершин графу у властивості OptimalPath, а його довжина – у OptimalPathLength.

Клас Cell представляє одну клітинку ігрового поля, містить такі властивості, як список сусідніх клітинок Neighbours, список довжин переходів з даної клітинки до сусідніх клітинок NeighboursPaths.

Клас AdjacencyInfo є допоміжним класом для формування списків сусідніх клітинок для кожної клітинки поля. Цей клас використовується в класі Field.

Клас Ant реалізує поведінку одного агента – мурахи по вибору шляху із поточної клітинки в наступну. Для цього використовується метод Move, який повертає булеве значення false у випадку, коли мураха не може рухатись далі (якщо немає непройдених вершин графа і не досягнуто фінішної вершини). В такому випадку викликається метод Reset, що повертає мураху у стартову вершину і мураха розпочинає свій рух знову.

  1.  
    Висновок

В ході даної курсової роботи було реалізовано алгоритм мурашиної колонії для пошуку оптимального шляху з у рахуванням перешкод між двома точками на двовимірній поверхні, що представлена у вигляді поля із клітинками.

Було проведено ряд експериментів, в яких задавалися різні параметри роботи програми, а саме: розмірність поля, розташування перешкод на полі, кількість мурах у колонії, кількість ітерації алгоритму, коефіцієнти «жадібності» і «стадності», загальна кількість феромону, коефіцієнт кількості феромона, що агент залишає на шляху. В результаті було виявлено, що при збільшенні розмірності поля, на сходимість алгоритму позитивно впливає збільшення загальної кількості феромону, кількості мурах у колонії та кількості ітерацій алгоритму. Але найперше значення мають коефіцієнти «жадібності» і «стадності» та коефіцієнт кількості феромона, що агент залишає на шляху.

Загалом, алгоритм діє досить повільно і дає результат лише наближений до найкращого в даному випадку. Це пов‘язано з тим, що внаслідок великої кількості ребер графа (кожна вершина має, як правило, вісім сусідів-вершин), мурашки часто потрапляють у ситуації, коли немає більше невідвіданих вершин і не досягнуто фінішної вершини. В такому випадку мураха повертається в стартову вершину і розпочинає свій шлях знову. З огляду на це, робимо висновок, що замість розглянутого алгоритму мурашиної колонії для даної задачі варто використовувати інші, більш ефективні алгоритми пошуку оптимального шляху, наприклад алгоритм хвильового пошуку або А*/Б*-алгоритми.

  1.  
    Література
  2.  M. Dorigo, V. Maniezzo, et A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics--Part B , volume 26, 1996.
  3.  Штовба С. Д. Муравьиные алгоритмы. Exponenta Pro. Математика в приложениях, 2003, №4, стр. 70-75.
  4.  МакКоннелл Дж. Основы современных алгоритмов. – М.: Техносфера, 2004. – 368 с.
  5.  Шилдт Г. «Полный справочник по C#.: Пер. с англ.» – М.: Издательский дом «Вильямс», 2007. – 752 стр.


 

А также другие работы, которые могут Вас заинтересовать

77241. ПРОВОДЯЩИЙ ПУТЬ БОЛЕВЫХ И ТЕМПЕРАТУРНЫХ ИМПУЛЬСОВ 183.39 KB
  Spinothlmicus lterlis болевая и температурная чуствительность Tr. Spinothlmicus nterior тактильная чувствительность В СМ эти тракты проходят в боковом и переднем канатиках соответственно В продолговатом мозге латеральный и передний тракты объединяются в единый tr. Spinothlmicus lemniscus spinlis Спинноталамический тракт проходит в покрышке моста и среднего мозга II зона ствола и заканчивается на вентролатеральных ядрах таламуса Большая часть аксонов nuclei ventrolterles thlmi 3 нейроны в составе таламокоркового тракта через заднюю...
77242. Экстрапирамидная система. Современные представления о строении и связи с другими отделами ЦНС 16.55 KB
  Нейроны клетки коры полушарий мозжечка 2 нейроны клетки зубчатых ядер аксоны которых переходят на противоположную сторону в среднем мозге перекрёст Вернекинга и заканчиваются на нейронах красного ядра. Аксоны переходят на противоположную сторону decusstio tegmenti dorslis фонтановидный Мейнерта. rubrospinlis пучок Монакова обеспечивает выполнение сложных привычных движений ходьба бег делая их пластичными способствует длительному сохранению позы и поддержанию тонуса мускулатуры;...
77243. Оболочки головного мозга. Межоболочечные пространства. Их сообщение с полостями головного мозга. А.В.Н. твердой мозговой оболочки 16.3 KB
  Оболочки головного мозга. твердой мозговой оболочки. Оболочки головного мозга. Образует выросты грануляции паутинной оболочки Пахионовы grnultiones rchnoidles которые служат для оттока спиномозговой жидкости в кровеносное русло.
77245. Вспомогательный аппарат глаза 371.42 KB
  nulus tendineus communis Верхняя прямая мышца Нижняя прямая мышца Латеральная прямая Медиальная прямая Верхняя косая Нижняя косая Мышца поднимающая верхнее веко Бровь supercilium Веко plpebre защитная функция: plpebr superior plpebr inferior fcies nterior покрыта кожей fcies posterior покрыта хрящевой и орбитальной коньюктивой. Верхняя прямая мышца Нижняя прямая мышца Медиальная прямая Нижняя косая Мышца поднимающая верхнее веко. Латеральная прямая 6 пара ЧН отводящий Верхняя косая 4 пара ЧН блоковый Нервы слезной...
77246. Наружнее и среднее ухо,их отделы. Барабанная полость, ее стенки сообщения и содержимое. Артерии, вены, нервы барабанной полости 43.54 KB
  Артерии вены нервы барабанной полости. Наружний слуховой проход metus custicus externus Prs cortilgine Cortillgo metus custici externiсоставляет одно целое с хрящем ушной раковины Incisure crtilginis metus custici externi Сартолиниевы шели Хрящевая часть выстлана тонкой кожей в которой имеются волоски сальные и цируминозные железы prs osse Образованна барабанной частью височной кости 3.Внутреннийпродолжение слизистой оболочки выстилающей барабанную полость Кровоснабжение Среднее ухо uris medi включает в себя: Cvits timpnic tub...
77248. Внутреннее ухо. Его части, содержимое. Строение полукружных каналов и преддверия. Преддверно-улитковый нерв, ядра, части. Вестибулярный путь 145.78 KB
  Преддверноулитковый нерв ядра части. Ядра слуховые ядра: nuclei cochleres nterior et posterior вестибулярные ядра: верхнееБехтерева нижнее Роллера латеральное Дейтерса медиальное Швальбе в области латерального угла foss rhomboide 2. Место выхода из черепа: porus custicus internus Вестибулярный путь От рецепторов статокинетического аппаратаампулярные гребешки и отолитовые аппараты внутреннего уха импульсы поступают к gnglion vestibulre 1 нейроны Далее в составе rdix vestibulris они входят в мостомозжечковый угол и...
77249. Глазодвигательный, блоковый, отводящий нервы. Медиальный продольный пучок 14.76 KB
  oculomotorius IIIсмешанный: Ядра серое вещество среднего мозга: N. ciliris Место выхода из мозга foss interpedunculris 3 Место выхода из черепа fissur orbitlis superior. trochleris IV двигательный: Ядрасерое вещество среднего мозга: N.obliquus superior 2 Место выхода из мозга сбоку от velum medullre superius.