Мурашиний алгоритм

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

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

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

Прийняття рішень

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

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

В серії дослідів на колонії мурах з вибором між двома шляхами різної довжини, які ведуть до джерела їжі, біологи спостерігали, що мурахи тяжіють до використання найкоротшого шляху. [2] [3] Модель, що пояснює таку поведінку така:

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

Мурахи використовують навколишнє середовище як посередник для зв'язку. Вони обмінюються інформацією непрямо через відкладання феромонів, які уточнюють статус їхньої роботи. Інформація розповсюджувана через феромони має місцеву дію, лише мурахи розташовані поруч із відкладеними феромонами помічають їх. Таку систему називають «Стіґмерґі» (англ. stigmergy) і вона трапляється в багатьох спільнотах соціальних тварин (її вивчали на прикладі розбудови стовпів у гніздах термітів). Спільне розв'язання проблем занадто складних для одного мурахи є хорошим прикладом самоорганізованої системи. Система покладається на позитивний зворотний зв'язок (відкладення феромонів приваблюють інших мурах, які підсилять їх у свою чергу) і негативний (зникнення маршруту через випаровування забезпечує оптимальність роботи системи). Теоретично, якщо щільність феромонів залишатиметься постійною на всіх відтинках, жоден із шляхів не стане головним. Однак, через зворотний зв'язок, малі відмінності на підмаршрутах підсилюватимуться і дозволятимуть зробити вибір. Алгоритм зсуватиметься з нестабільного стану, де жоден з підмаршрутів не привабливіший за інші, у бік стабільного стану, де маршрут утворений з найсильніших підмаршрутів.

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

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

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

Пройдений мурахою шлях відображається, коли мураха відвідає всі вузли графу. Цикли заборонено, оскільки в алгоритм включено список табу. Після завершення довжина шляху може бути підрахована — вона дорівнює сумі довжин всіх ребер, якими подорожувала мураха. Рівняння (1) показує кількість феромону, який був залишений на кожному ребрі шляху для мурашки k. Змінна Q є константою.

${\displaystyle \bigtriangleup \tau _{ij}^{k}(t)={\frac {Q}{L^{k}(t)}}}$ (1)

Результат рівняння є засобом вимірювання шляху, — короткий шлях характеризується високою концентрацією феромонів, а більш довгий шлях — більш низькою. Далі, отриманий результат використовується в рівнянні (2), щоб збільшити кількість феромону вздовж кожного ребра пройденого мурахою шляху.

${\displaystyle \tau _{ij}(t)=\bigtriangleup \tau _{ij}(t)+(\tau _{ij}^{k}\times \rho )}$(2)

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

Петльові вібраторні антени формату 10×10, синтезовані на основі мурашиного алгоритму оптимізації

Непетльові вібратори формату 10×10, синтезовані за допомогою мурашиного алгоритму

На початку шляху у кожного ребра є шанс бути обраним. Щоб поступово видалити ребра, які входять у гірші шляхи графу, до всіх ребер застосовується процедура випаровування феромону. Використовуючи константу p з рівняння (2), отримуємо рівняння (3):

${\displaystyle \tau _{ij}(t)=\tau _{ij}(t)\times (1-\rho )}$(3)

Для випаровування феромону використовується зворотний коефіцієнт оновлення шляху.

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

Типовими прикладами вирішення такого завдання є задача календарного планування, завдання маршрутизації транспорту, різних мереж (GPRS, телефонні, комп'ютерні тощо), розподіл ресурсів та робіт, оптимізація форми антен, наприклад, RFID-тегів[15][16][17]. Ці задачі виникають у бізнесі, інженерії, виробництві та багатьох інших областях. Дослідження показали, що метод мурашиних колоній може давати результати, навіть кращі, ніж при використанні генетичних алгоритмів і нейронних мереж^{[джерело?]}.

Засновниками є Франс Мойсон і Бернард Мандерик. Піонерами поля є Марко Доріго, Лука Марія Гамбардела[18].

Хронологія алгоритмів оптимізації колонії мурах.

• 1959, П'єр-Поль Грассе винайшов теорію Стіґмерґі, щоб пояснити поведінку будування гнізда термітами[19];
• 1983, Денубур та його колеги вивчали колективну поведінку мурах[20];
• 1989, праці Госса, Арона, Денбура і Пастеля про колективну поведінку аргентинських мурах, які дадуть уявлення про алгоритми оптимізації колонії мурашок[21];
• 1989, впровадження моделі поведінки для харчових продуктів Еблінг та його колег[22];
• 1991, Марко Доріго запропонував систему мурах в своїй докторській дисертації (яка була опублікована в 1992 році[23]). Технічний звіт, витягнутий з дисертації та співавторів В. Манеццо та А. Колорні[23], був опублікований через п'ять років[24];
• 1994, Appleby і Steward British Telecommunications Plc опублікували першу заявку на телекомунікаційні мережі[25];
• 1996, публікація статті про мурашкову систему[24];
• 1996, Хус і Штюцл придумали max-min систему мурах[26];
• 1997, Доріго та Гамбарделла публікують систему колоній мурах[27];
• 1997, Шундервоерд та його колеги опублікували вдосконалене застосування до телекомунікаційних мереж[28];
• 1998, Доріго запускає першу конференцію, присвячену мурашиним алгоритмам[29];
• 1998, Штюцл пропонує початкові паралельні реалізації[30];
• 1999, Бонабеу, Доріго та Зераулаз видають книгу, що займається переважно штучними мурахами[31];
• 2000, спеціальний випуск журналу «Комп'ютерні системи майбутнього покоління» про алгоритми мурашок[32];
• 2000, перші програми для планування, послідовності планування і задоволення обмежень;
• 2000, Гутьяр дає перші докази конвергенції для алгоритму колоній мурашок[33];
• 2001, перше використання мурашиних алгоритмів компаніями (Eurobios та AntOptima);
• 2001, Іреді та його колеги опублікували перший багатоцільовий алгоритм[34];
• 2002, перші програми в розробці графіка, байєсівських мереж;
• 2002, Бьянчі та її колеги запропонували перший алгоритм стохастичної проблеми[35];
• 2004, Доріго та Штюцл публікують книгу з оптимізації колонії мурах з пресою MIT Press[36];
• 2004, Злочін та Доріго показують, що деякі алгоритми еквівалентні стохастичному спуску градієнта, метод перехресної ентропії та алгоритми для оцінки розподілу[37];
• 2005, перше застосування до проблем згортання білків;
• 2012, Прабхакар і його колеги публікують дослідження, пов'язані з функціонуванням окремих мурах, які спілкуються в тандемі без феромонів, відображаючи принципи організації комп'ютерних мереж. Модель зв'язку була порівняна з TCP[38];
• 2016, перше застосування до дизайну послідовностей пептидів[39];
• 2017, успішна інтеграція багатокритеріального методу прийняття рішень PROMETHEE в мурашиному алгоритмі (алгоритм HUMANT)[40].

• Задача оптимізації
• Теорема схем
• Функція допасованості
• Генетичний алгоритм

• Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 2009. — 375 с.
• Оптимізація мурашиної колонії (англ.)