37478

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

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

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

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

Украинкский

2013-09-24

235.5 KB

35 чел.

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

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

Кафедра ПЗОТ

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


 

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

9249. Гражданские процессуальные принципы 38 KB
  ТЕМА №2: Гражданские процессуальные принципы понятие и классификация принципов ГПП принцип законности принцип состязательности принцип диспозитивности принципы непосредственности и непрерывности конституционные пр...
9250. Гражданские процессуальные правоотношения 62 KB
  Тема №3: Гражданские процессуальные правоотношения. понятие гражданского процессуального правоотношения классификация гражданских процессуальных правоотношений элементы гражданских процессуальных правоотношений основания возн...
9251. Стороны в гражданском судопроизводстве 47 KB
  Тема №4: Стороны в гражданском судопроизводстве. понятие сторон процессуальные права и обязанности сторон процессуальное соучастие надлежащая и ненадлежащая сторона. Замена не надлежащего ответчика гражданское процессуа...
9252. Третьи лица в гражданском судопроизводстве 43 KB
  Тема №5. Третьи лица в гражданском судопроизводстве. понятие и виды 3-х лиц 3-е лица, заявляющие самостоятельные требования относительно предмета спора. 3-е лица, не заявляющие самостоятельные требования относительно предмета спора...
9253. Участие прокурора и субъектов, защищающих от своего имени права и интересы других лиц, в гражданском судопроизводстве 65.5 KB
  Тема №6. Участие прокурора и субъектов, защищающих от своего имени права и интересы других лиц, в гражданском судопроизводстве. задачи прокуратуры в гражданском судопроизводстве. цель и основания участия прокурора в гражданском судопроиз...
9254. Судебное представительство 61.5 KB
  Тема №7. Судебное представительство. понятие представительства в суде виды представительства в суде полномочия и их оформление ФЗ от 31.05.2002г. Об адвокатской деятельности и адвокатуре в РФ. Постановление Пленума Ве...
9255. Гражданская процессуальная ответственность. 54.5 KB
  Тема № Гражданская процессуальная ответственность. понятие и значение гражданской процессуальной ответственности предпосылки и основания привлечения к гражданской процессуальной ответственности виды гражданской процессуальной ответ...
9256. Подведомственность гражданских дел 50 KB
  Тема №9. Подведомственность гражданских дел. понятие и виды подведомственности судебная подведомственность ГД правовые последствия не подведомственности дела суду Постановление Пленума ВС РФ от 18.08.1992г. №12/12 НК, СК, ФЗ «О тре...
9257. Подсудность гражданских дел 47 KB
  Тема № Подсудность гражданских дел. понятие и виды родовая подсудность территориальная подсудность передача дела и 1 суда в другой правовые последствия несоблюдения правил подсудности ФКЗ О военных судах в РФ от 23.06...