Мурашиний алгоритм (алгоритм оптимізації мурашиної колонії, англ. ant colony optimization, ACO) — один з ефективних поліноміальних алгоритмів для знаходження наближених розв'язків задачі комівояжера, а також аналогічних завдань пошуку маршрутів на графах. Підхід запропонований бельгійським дослідником Марко Доріго (англ. Marco Dorigo). Суть підходу полягає в аналізі та використанні моделі поведінки мурах, що шукають дороги від колонії до їжі.

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

${\displaystyle P_{i}={\frac {{l_{i}}^{q}\cdot {f_{i}}^{p}}{\sum _{k=0}^{N}{{l_{k}}^{q}\cdot {f_{k}}^{p}}}}}$,

де:

${\displaystyle P_{i}}$ — ймовірність переходу шляхом ${\displaystyle i}$,

${\displaystyle l_{i}}$ — величина, обернена до довжини (ваги) ${\displaystyle i}$-ого переходу,

${\displaystyle f_{i}}$ — кількість феромонів на ${\displaystyle i}$-ому переході,

${\displaystyle q}$ — величина, яка визначає «жадібність» алгоритму,

${\displaystyle p}$ — величина, яка визначає «стадність» алгоритму і

${\displaystyle q+p=1}$

Результат не є точним і навіть може бути одним з гірших, проте, в силу імовірності рішення, повторення алгоритму може видавати (досить) точний результат.

Висхідна діяльність у цьому напрямі призвела до проведення конференцій, присвячених виключно штучним мурахам, а також численним комп'ютерним програмам від спеціалізованих компаній, таких як AntOptima. Як приклад, мурашиний алгоритм є класом алгоритмів оптимізації за зразком колонії мурашок. Штучні «мурашки» знаходять оптимальні варіанти, рухаючись простором параметрів, який представляє усі можливі рішення.

Реальні мурахи виділяють феромони, щоб спрямувати один одного до ресурсів та досліджувати своє оточення. Модельовані «мурахи» аналогічно фіксують свої позиції та якість своїх рішень, таким чином, в подальших ітераціях моделювання мурахи приймають кращі рішення^[1]. Одним з варіантів цього підходу є бджолиний алгоритм, який аналогічний структурі роботи медоносних бджіл, іншої соціальної комахи.

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

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

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

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

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

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

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

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

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

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

Природа дала нам кілька прикладів того, як мізерні організми, якщо всі вони слідують одному і тому ж основному правилу, можуть створити форму колективного інтелекту на макроскопічному рівні. Колонії соціальних комах чудово ілюструють цю модель, яка сильно відрізняється від людських суспільств. Ця модель базується на взаємодії незалежних підрозділів з простою та непередбачуваною поведінкою^[5]. Вони рухаються по навколишній території, щоб виконувати певні завдання і володіти лише обмеженою кількістю інформації для цього. Наприклад, колонія мурах представляє якості, які можуть бути застосовані до мережі штучних об'єктів. Колонії мурах мають дуже високу здатність пристосовуватися до змін у навколишньому середовищі, а також величезною силою у вирішенні ситуацій, коли одна людина не в змозі виконати дане завдання. Така гнучкість також буде дуже корисною для мобільних мереж об'єктів, що постійно розвиваються. Пакети інформації, які переміщуються з комп'ютера на інший, мають таку ж поведінку, як і мурашки. Вони переміщуються мережею і переходять від одного вузла до наступного з метою прибуття до кінцевого пункту призначення якнайшвидше^[6].

Зв'язок на основі феромонів є одним з найбільш ефективних способів спілкування, який широко спостерігається в природі. Феромон використовується соціальними комахами, такими як бджоли, мурахи і терміти. У зв'язку з його доцільністю штучні феромони були прийняті в системах мультироботів і робототехнічних систем зі структурою роя. Зв'язок на основі феромонів був реалізований різними засобами, такими як хімічний^[7][8] або фізичний (RFID-мітки^[9], світло^{[10][11][12][13]}, звук^[14]) способи. Проте, ці реалізації не змогли повторити всі аспекти феромонів, які використовуються в живій природі.

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

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

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

Пройдений мурахою шлях відображається, коли мураха відвідає всі вузли графу. Цикли заборонено, оскільки в алгоритм включено список табу. Після завершення довжина шляху може бути підрахована — вона дорівнює сумі довжин всіх ребер, якими подорожувала мураха. Рівняння (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.

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

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

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

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

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

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

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

• 1959, П'єр-Поль Грассе^[en] винайшов теорію Стіґмерґі, щоб пояснити поведінку будування гнізда термітами^[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 [Архівовано 25 лютого 2019 у Wayback Machine.] та AntOptima [Архівовано 10 січня 2019 у Wayback Machine.]);
• 2001, Іреді та його колеги опублікували перший багатоцільовий алгоритм^[34];
• 2002, перші програми в розробці графіка, байєсівських мереж;
• 2002, Бьянчі та її колеги запропонували перший алгоритм стохастичної проблеми^[35];
• 2004, Доріго та Штюцл публікують книгу з оптимізації колонії мурах з пресою MIT Press^[36];
• 2004, Злочін та Доріго показують, що деякі алгоритми еквівалентні стохастичному спуску градієнта, метод перехресної ентропії та алгоритми для оцінки розподілу^[37];
• 2005, перше застосування до проблем згортання білків;
• 2012, Прабхакар і його колеги публікують дослідження, пов'язані з функціонуванням окремих мурах, які спілкуються в тандемі без феромонів, відображаючи принципи організації комп'ютерних мереж. Модель зв'язку була порівняна з TCP^[38];
• 2016, перше застосування до дизайну послідовностей пептидів^[39];
• 2017, успішна інтеграція багатокритеріального методу прийняття рішень PROMETHEE в мурашиному алгоритмі (алгоритм HUMANT^[en])^[40].

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

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

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

Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її.