37478

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

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

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

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

Украинкский

2013-09-24

235.5 KB

30 чел.

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

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

Кафедра ПЗОТ

Група АК-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 стр.


 

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

40296. Острые алкогольные психозы 35.5 KB
  Гипнагогический делирий ограничивается многочисленными яркими в ряде случаев сценоподобными сновидениями или зрительными галлюцинациями при засыпании и закрывании глаз. Гипнагогический делирий фантастического содержания называют гипнагогическим ониризмом. Делирий без делирия возникает остро. Делирий длится 1 3 дня.
40297. Параклинические методы исследования 36 KB
  Методы психологического исследования традиционно подразделяются на методы исследования психических процессов восприятия ощущения внимания памяти мышления и т. и методы исследования личности. Для исследования переключаемости внимания часто используется двухцветная таблица Горбова где изображены в случайном порядке черные числа от 1 до 25 и красные – от 1 до 24.
40298. Параноидная форма шизофрении 38.5 KB
  В стереотипе развития бредовых синдромов в типичных случаях наблюдаются этап бреда не сопровождающегося галлюцинациями и явлениями психического автоматизма паранойяльный синдром этапы параноидного бреда синдром Кандинского Клерамбо и фантастического бреда парафренный синдром. Манифестация болезни проявляется развитием интерпретативного бреда с большей или меньшей степенью систематизации бредовых идей. При бредовом варианте параноидной шизофрении манифестный период болезни характеризуется формированием интерпретативного...
40299. Аналіз роботи підприємства, стану і перспектив розвитку міжнародної економічної діяльності на підприємстві 495 KB
  За таких умов підприємствам надані широкі права і можливості у реалізації своїх економічних інтересів, виборів способів організації виробництва, збуту продукції. При цьому підприємство виходить із власних ресурсних можливостей
40300. Показания к недобровольной госпитализации 32.5 KB
  Основания для госпитализации в психиатрический стационар в недобровольном порядке: Лицо страдающее психическим расстройством может быть госпитализировано в психиатрический стационар без его согласия или без согласия его законного представителя до постановления судьи если его обследование или лечение возможны только в стационарны условиях а психическое расстройство является тяжелым и обусловливает: а его непосредственную опасность для себя или окружающих или б его беспомощность то есть неспособность самостоятельно удовлетворять основные...
40301. Показания к помещению и выписке 29 KB
  Основания для госпитализации: 1 Основаниями для госпитализации в психиатрический стационар являются наличие у лица психического расстройства и решение врача психиатра о проведении обследования или лечения в стационарных условиях либо постановление судьи. 3 Помещение лица в психиатрический стационар за исключением случаев предусмотренных статьей 29 настоящего Закона осуществляется добровольно по его просьбе или с его согласия. 4 Несовершеннолетний в возрасте до 15 лет помещается в психиатрический стационар по просьбе или с...
40302. ПОМРАЧЕНИЕ СОЗНАНИЯ 30.5 KB
  дезориентировка аллопсихическая амнестическая аутопсихическая бредовая ложные представления об окружающем соматопсихическая двойная ориентировка амнезия на период нарушенного сознания тотальная или частичная симптомы расстройства сознания: анозогнозия неузнавание или отрицание собственной болезни невозможность правильно оценить собственный дефект. СИНДРОМЫ ПОМРАЧЕНИЯ СОЗНАНИЯ Оглушение характеризуется повышением порога ко всем раздражителям и обеднением психической деятельности. ДЕЛИРИЙ это иллюзорногаллюцинаторное...
40303. Прогрессивный паралич 34 KB
  Неврологические симптомы: синдром Аргайла Робертсона отсутствие прямой и содружественной реакции зрачков на свет при сохранении реакции на конвергенцию и аккомодацию; сужение миоз реже расширение мидриаз зрачков их неравномерность анизокория и деформация. Формы: экспансивная маниакальная форма; эйфорическая форма; простая дементная; депрессивная форма; циркулярная форма. Стационарный паралич форма с особенно медленным течением.
40304. ПСИХООРГАНИЧЕСКИЙ СИНДРОМ 25 KB
  Снижение интеллекта снижение уровня суждений. Снижение дисфория злобная раздражительность эйфорический апатический.