Перегляд вихідного коду сторінки Мурашиний алгоритм

[[Файл:Safari ants.jpg|thumb|Поведінка мурах надихнула метаевристичну техніку оптимізації]]'''Мурашиний алгоритм''' (алгоритм оптимізації мурашиної колонії, {{lang-en|ant colony optimization}}, ACO)&nbsp;— один з ефективних поліноміальних алгоритмів для знаходження наближених розв'язків [[Задача комівояжера|задачі комівояжера]], а також аналогічних завдань пошуку маршрутів на графах. Підхід запропонований бельгійським дослідником Марко Доріго ({{lang-en|Marco Dorigo}}). Суть підходу полягає в аналізі та використанні моделі поведінки [[мураха|мурах]], що шукають дороги від колонії до їжі.

У основі алгоритму лежить поведінка [[Мурашник|мурашиної колонії]]&nbsp;— маркування вдалих доріг великою кількістю [[феромон]]у. Робота починається з розміщення мурашок у вершинах [[Граф (математика)|графу]] (містах), потім починається рух мурашок&nbsp;— напрям визначається імовірнісним методом, на підставі формули:
: <math>P_i=\frac{{l_i}^{q}\cdot {f_i}^{p}}{\sum_{k=0}^{N}{{l_k}^{q}\cdot {f_k}^{p}}}</math>,
де:
: <math>P_i</math>&nbsp;— ймовірність переходу шляхом <math>i</math>,
: <math>l_i</math>&nbsp;— величина, обернена до довжини (ваги) <math>i</math>-ого переходу,
: <math>f_i</math>&nbsp;— кількість феромонів на <math>i</math>-ому переході,
: <math>q</math>&nbsp;— величина, яка визначає «жадібність» алгоритму,
: <math>p</math>&nbsp;— величина, яка визначає «стадність» алгоритму і
: <math>q+p=1</math>

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

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

Реальні мурахи виділяють феромони, щоб спрямувати один одного до ресурсів та досліджувати своє оточення. Модельовані «мурахи» аналогічно фіксують свої позиції та якість своїх рішень, таким чином, в подальших ітераціях моделювання мурахи приймають кращі рішення<ref>{{Cite book|url=https://www.worldcat.org/oclc/57182707|title=Ant colony optimization|last=Marco.|first=Dorigo,|date=2004|publisher=MIT Press|location=Cambridge, Mass.|isbn=9780262256032|oclc=57182707}}</ref>. Одним з варіантів цього підходу є [[Бджолиний алгоритм|бджолиний алгоритм]], який аналогічний структурі роботи медоносних бджіл, іншої соціальної комахи.

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

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

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

=== Прийняття рішень ===
[[Файл:Aco branches.svg|left|400px]]

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

# Перша мураха знаходить джерело їжі (Д), через якийсь шлях (а), тоді повертається до гнізда (Г), залишивши позаду слід з феромонів (б)
# Мурахи без розбору обирають всі чотири шляхи, але підсилення основної стежки робить її привабливішою як найкоротший шлях.
# Мурахи обирають коротший шлях, довгі відтинки втрачають щільність феромонового сліду.
В серії дослідів на колонії мурах з вибором між двома шляхами різної довжини, які ведуть до джерела їжі, біологи спостерігали, що мурахи тяжіють до використання найкоротшого шляху.
<ref name="S. Goss">S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, ''Self-organized shortcuts in the Argentine ant'', Naturwissenschaften, volume 76, pages 579—581, 1989</ref>
<ref>J.-L. Deneubourg, S. Aron, S. Goss et J.-M. Pasteels, ''The self-organizing exploratory pattern of the Argentine ant'', Journal of Insect Behavior, volume 3, page 159, 1990</ref>
Модель, що пояснює таку поведінку така:
# Мураха (звана «бліц») рухається більш-менш випадково по колонії;
# Якщо вона знаходить джерело їжі, вона повертається прямо до гнізда, залишаючи по собі феромоновий слід;
# Ці феромони заманливі, ближні мурахи схилятимуться до слідування, більш чи менш точно, цим шляхом;
# Повертаючись до колонії, мурахи підсилюватимуть маршрут;
# Якщо наявні два шляхи до одного й того самого джерела їжі тоді, за певний час, коротший шлях пройде більше мурах ніж довшій;
# Короткий шлях все більш посилюватиметься, і таким чином ставатиме привабливішим;
# Довгий шлях з часом зникне, бо феромони вивітряться;
# Зрештою, всі мурахи визначатимуть і через це обиратимуть найкоротший шлях.

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

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

Невеликі пристрої, які можна порівняти з комахами, не мають власного розвинутого інтелекту. Навпаки, їх інтелект можна назвати досить обмеженим. Наприклад, неможливо інтегрувати високоефективний калькулятор з можливістю вирішувати будь-яку математичну задачу в біочіп, який імплантується в організм людини. Однак, коли об'єкти взаємопов'язані, вони розпоряджаються формою інтелекту, яку можна порівняти з колонією мурах або бджіл. Для певних задач цей тип інтелекту може навіть перевершувати очікування про централізовану систему, подібну до мозку<ref>{{Cite book|title=Nanocomputers and Swarm Intelligence|url=https://archive.org/details/nanocomputersswa00wald|last=Waldner|first=Jean-Baptiste|year=2008|publisher=ISTE John Wiley & Sons|location=London|pages=[https://archive.org/details/nanocomputersswa00wald/page/n232 214]|language=|isbn=978-1-84704-002-2}}</ref>.

Природа дала нам кілька прикладів того, як мізерні організми, якщо всі вони слідують одному і тому ж основному правилу, можуть створити форму колективного інтелекту на макроскопічному рівні. Колонії соціальних комах чудово ілюструють цю модель, яка сильно відрізняється від людських суспільств. Ця модель базується на взаємодії незалежних підрозділів з простою та непередбачуваною поведінкою<ref>{{Cite book|title=Inventer l'Ordinateur du XXIème Siècle|last=Waldner|first=Jean-Baptiste|year=2007|publisher=Hermes Science|location=London|pages=259–265|language=|isbn=978-2-7462-1516-0}}</ref>. Вони рухаються по навколишній території, щоб виконувати певні завдання і володіти лише обмеженою кількістю інформації для цього. Наприклад, колонія мурах представляє якості, які можуть бути застосовані до мережі штучних об'єктів. Колонії мурах мають дуже високу здатність пристосовуватися до змін у навколишньому середовищі, а також величезною силою у вирішенні ситуацій, коли одна людина не в змозі виконати дане завдання. Така гнучкість також буде дуже корисною для мобільних мереж об'єктів, що постійно розвиваються. Пакети інформації, які переміщуються з комп'ютера на інший, мають таку ж поведінку, як і мурашки. Вони переміщуються мережею і переходять від одного вузла до наступного з метою прибуття до кінцевого пункту призначення якнайшвидше<ref>Waldner, Jean-Baptiste (2008). ''Nanocomputers and Swarm Intelligence''. London: ISTE John Wiley & Sons. p. 215. ISBN 978-1-84704-002-2.</ref>.

=== Система штучних феромонів ===
Зв'язок на основі феромонів є одним з найбільш ефективних способів спілкування, який широко спостерігається в природі. Феромон використовується соціальними комахами, такими як бджоли, мурахи і терміти. У зв'язку з його доцільністю штучні феромони були прийняті в системах мультироботів і робототехнічних систем зі структурою роя. Зв'язок на основі феромонів був реалізований різними засобами, такими як хімічний<ref>{{Cite news|title=Ant trails - an example for robots to follow?|url=http://dx.doi.org/10.1109/robot.1999.774005|publisher=IEEE|work=Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C)|accessdate=2019-02-25|isbn=0780351800|doi=10.1109/robot.1999.774005|first=R.A.|last=Russell}}</ref><ref>{{Cite news|title=Designing pheromone communication in swarm robotics: Group foraging behavior mediated by chemical substance|url=http://dx.doi.org/10.1007/s11721-014-0097-z|work=Swarm Intelligence|date=2014-08-26|accessdate=2019-02-25|issn=1935-3812|doi=10.1007/s11721-014-0097-z|pages=227–246|volume=8|issue=3|first=Ryusuke|last=Fujisawa|first2=Shigeto|last2=Dobata|first3=Ken|last3=Sugawara|first4=Fumitoshi|last4=Matsuno}}</ref> або фізичний ([[Радіочастотна ідентифікація|RFID-мітки]]<ref>{{Cite news|title=Artificial pheromone system using RFID for navigation of autonomous robots|url=http://dx.doi.org/10.1016/s1672-6529(07)60038-9|work=Journal of Bionic Engineering|date=2007-12|accessdate=2019-02-25|issn=1672-6529|doi=10.1016/s1672-6529(07)60038-9|pages=245–253|volume=4|issue=4|last=Herianto|first2=Toshiki|last2=Sakakibara|first3=Daisuke|last3=Kurabayashi}}</ref>, світло<ref>{{Cite news|title=Investigation of cue-based aggregation in static and dynamic environments with a mobile robot swarm|url=http://dx.doi.org/10.1177/1059712316632851|work=Adaptive Behavior|date=2016-03-07|accessdate=2019-02-25|issn=1059-7123|doi=10.1177/1059712316632851|pages=102–118|volume=24|issue=2|first=Farshad|last=Arvin|first2=Ali Emre|last2=Turgut|first3=Tomáš|last3=Krajník|first4=Shigang|last4=Yue}}</ref><ref>{{Cite news|title=Imitation of Honeybee Aggregation with Collective Behavior of Swarm Robots.|url=http://dx.doi.org/10.2991/ijcis.2011.4.4.26|work=International Journal of Computational Intelligence Systems|date=2011|accessdate=2019-02-25|issn=1875-6883|doi=10.2991/ijcis.2011.4.4.26|pages=739|volume=4|issue=4|first=Farshad|last=Arvin|first2=Khairulmizam|last2=Samsudin|first3=Abdul Rahman|last3=Ramli|first4=Masoud|last4=Bekravi}}</ref><ref>{{Cite news|title=Get in touch: cooperative decision making based on robot-to-robot collisions|url=http://dx.doi.org/10.1007/s10458-008-9058-5|work=Autonomous Agents and Multi-Agent Systems|date=2008-08-08|accessdate=2019-02-25|issn=1387-2532|doi=10.1007/s10458-008-9058-5|pages=133–155|volume=18|issue=1|first=Thomas|last=Schmickl|first2=Ronald|last2=Thenius|first3=Christoph|last3=Moeslinger|first4=Gerald|last4=Radspieler|first5=Serge|last5=Kernbach|first6=Marc|last6=Szymanski|first7=Karl|last7=Crailsheim}}</ref><ref>{{Cite news|title=Do Ants Need to Estimate the Geometrical Properties of Trail Bifurcations to Find an Efficient Route? A Swarm Robotics Test Bed|url=http://dx.doi.org/10.1371/journal.pcbi.1002903|work=PLoS Computational Biology|date=2013-03-28|accessdate=2019-02-25|issn=1553-7358|doi=10.1371/journal.pcbi.1002903|pages=e1002903|volume=9|issue=3|first=Simon|last=Garnier|first2=Maud|last2=Combe|first3=Christian|last3=Jost|first4=Guy|last4=Theraulaz}}</ref>, звук<ref>{{Cite news|title=Cue-based aggregation with a mobile robot swarm: a novel fuzzy-based method|url=http://dx.doi.org/10.1177/1059712314528009|work=Adaptive Behavior|date=2014-05|accessdate=2019-02-25|issn=1059-7123|doi=10.1177/1059712314528009|pages=189–206|volume=22|issue=3|first=Farshad|last=Arvin|first2=Ali Emre|last2=Turgut|first3=Farhad|last3=Bazyari|first4=Kutluk Bilge|last4=Arikan|first5=Nicola|last5=Bellotto|first6=Shigang|last6=Yue}}</ref>) способи. Проте, ці реалізації не змогли повторити всі аспекти феромонів, які використовуються в живій природі.

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

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

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

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

<math>\bigtriangleup\tau_{ij}^{k}(t) =\frac{Q}{L^{k}(t)} </math> (1)

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

<math>\tau_{ij}(t)=\bigtriangleup\tau_{ij}(t) + (\tau^{k}_{ij}\times\rho) </math>(2)

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

== Випаровування феромонів ==
[[Файл:ANT Antenna 1.jpg|thumb|Петльові вібраторні антени формату 10×10, синтезовані на основі мурашиного алгоритму оптимізації]]
[[Файл:ANT antenna 2.jpg|thumb|Непетльові вібратори формату 10×10, синтезовані за допомогою мурашиного алгоритму]]
На початку шляху у кожного ребра є шанс бути обраним. Щоб поступово видалити ребра, які входять у гірші шляхи графу, до всіх ребер застосовується процедура випаровування феромону. Використовуючи константу p з рівняння (2), отримуємо рівняння (3):

<math>\tau_{ij}(t)=\tau_{ij}(t)\times(1-\rho)</math>(3)

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

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

Типовими прикладами вирішення такого завдання є задача календарного планування, завдання маршрутизації транспорту, різних мереж (GPRS, телефонні, комп'ютерні тощо), розподіл ресурсів та робіт, оптимізація форми антен, наприклад, RFID-тегів<ref>{{стаття|автор=Marcus Randall, Andrew Lewis, Amir Galehdar, David Thiel.|назва= Using Ant Colony Optimisation to Improve the Efficiency of Small Meander Line RFID Antennas.// In 3rd IEEE International e-Science and Grid Computing Conference|ссылка=http://www98.griffith.edu.au/dspace/bitstream/10072/17063/1/47523_1.pdf|год=2007}}</ref><ref name=slyusarant>{{статья|автор=Ермолаев С.Ю., Слюсар В.И.|заглавие= Синтез антенн на основе муравьиных алгоритмов оптимизации. // 19-я Международная Крымская конференция «СВЧ-техника и телекоммуникационные технологии» (КрыМиКо’2009). Материалы конференции.- Севастополь, 14-18 сентября |ссылка=http://slyusar.kiev.ua/CriMiCo2009.pdf|год=2009|страницы= 431 - 432}}</ref><ref name=slyusarant1>{{статья|автор=Ermolaev S.Y., Slyusar V.I.|заглавие= Antenna synthesis based on the ant colony optimization algorithm.// 7-я Международная конференция по теории и технике антенн (ICATT’09), Львов, Украина, 6 - 9 октября 2009 г.|ссылка=http://slyusar.kiev.ua/298_300_ICATT_2009.pdf|год=2009|страницы= 298 - 300}}</ref>. Ці задачі виникають у бізнесі, інженерії, виробництві та багатьох інших областях. Дослідження показали, що метод мурашиних колоній може давати результати, навіть кращі, ніж при використанні генетичних алгоритмів і нейронних мереж{{Джерело}}.

== Історія ==
Засновниками є [[Франс Мойсон]] і [[Бернард Мандерик]]. Піонерами поля є {{не перекладено|Марко Доріго||en|Marco Dorigo}}, {{не перекладено|Лука Марія Гамбардела||en|Luca Maria Gambardella}}<ref>{{Cite news|title=Massive parallelism through program restructuring|url=http://dx.doi.org/10.1109/fmpc.1990.89491|publisher=IEEE Comput. Soc. Press|work=[1990 Proceedings] The Third Symposium on the Frontiers of Massively Parallel Computation|accessdate=2019-02-25|isbn=0818620536|doi=10.1109/fmpc.1990.89491|first=M.|last=Wolfe}}</ref>.

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

* 1959, {{не перекладено|П'єр-Поль Грассе||en|Pierre-Paul Grassé}} винайшов теорію Стіґмерґі, щоб пояснити поведінку будування гнізда термітами<ref>{{Cite news|title=La reconstruction du nid et les coordinations interindividuelles chezBellicositermes natalensis etCubitermes sp. la théorie de la stigmergie: Essai d'interprétation du comportement des termites constructeurs|url=http://dx.doi.org/10.1007/bf02223791|work=Insectes Sociaux|date=1959-03|accessdate=2019-02-25|issn=0020-1812|doi=10.1007/bf02223791|pages=41–80|volume=6|issue=1|first=Plerre-P.|last=Grassé}}</ref>;
* 1983, Денубур та його колеги вивчали [[Колективна поведінка тварин|колективну поведінку]] мурах<ref>{{Cite news|title=Probabilistic behaviour in ants: A strategy of errors?|url=http://dx.doi.org/10.1016/s0022-5193(83)80007-1|work=Journal of Theoretical Biology|date=1983-01|accessdate=2019-02-25|issn=0022-5193|doi=10.1016/s0022-5193(83)80007-1|pages=259–271|volume=105|issue=2|first=J.L.|last=Deneubourg|first2=J.M.|last2=Pasteels|first3=J.C.|last3=Verhaeghe}}</ref>;
* 1989, праці Госса, Арона, Денбура і Пастеля про '''колективну поведінку [[Аргентинська мурашка|аргентинських мурах]]''', які дадуть уявлення про алгоритми оптимізації колонії мурашок<ref>{{Cite news|title=Self-organized shortcuts in the Argentine ant|url=http://dx.doi.org/10.1007/bf00462870|work=Naturwissenschaften|date=1989-12|accessdate=2019-02-25|issn=0028-1042|doi=10.1007/bf00462870|pages=579–581|volume=76|issue=12|first=S.|last=Goss|first2=S.|last2=Aron|first3=J. L.|last3=Deneubourg|first4=J. M.|last4=Pasteels}}</ref>;
* 1989, впровадження моделі поведінки для харчових продуктів Еблінг та його колег<ref>{{Cite news|title=Limitation Of Optimism In The Time Warp Operating System|url=http://dx.doi.org/10.1109/wsc.1989.718752|publisher=IEEE|work=1989 Winter Simulation Conference Proceedings|accessdate=2019-02-25|isbn=0911801588|doi=10.1109/wsc.1989.718752|first=P.L.|last=Reiher|first2=D.|last2=Jefferson|first3=F.|last3=Wieland}}</ref>;
* 1991, Марко Доріго запропонував '''систему мурах''' в своїй докторській дисертації (яка була опублікована в 1992 році<ref name=":0">{{Cite news|title=Cognitive Adaptve Urban Systems for the Living Built Environment|url=http://dx.doi.org/10.5176/2425-0112_uppd16.43|publisher=Global Science & Technology Forum (GSTF)|date=2016-10-10|accessdate=2019-02-25|doi=10.5176/2425-0112_uppd16.43|first=Lavinia C.|last=Tagliabue|first2=Angelo L.C.|last2=Ciribini|first3=Alice|last3=Pasquinelli|first4=Giuseppe M. Di|last4=Giuda|first5=Valentina|last5=Villa|first6=Enrico De|last6=Angelis}}</ref>). Технічний звіт, витягнутий з дисертації та співавторів В. Манеццо та А. Колорні<ref name=":0"/>, був опублікований через п'ять років<ref name=":1">{{Cite news|title=Ant system: optimization by a colony of cooperating agents|url=http://dx.doi.org/10.1109/3477.484436|work=IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics)|date=1996|accessdate=2019-02-25|issn=1083-4419|doi=10.1109/3477.484436|pages=29–41|volume=26|issue=1|first=M.|last=Dorigo|first2=V.|last2=Maniezzo|first3=A.|last3=Colorni}}</ref>;
* 1994, Appleby і Steward British Telecommunications Plc опублікували першу заявку на [[Телекомунікаційна мережа|телекомунікаційні мережі]]<ref>{{Cite book|url=http://dx.doi.org/10.1007/978-3-642-58418-3_11|title=Mobile Software Agents for Control in Telecommunications Networks|last=Appleby|first=Stephen|last2=Steward|first2=Simon|date=1999|series=Software Agents for Future Communication Systems|publisher=Springer Berlin Heidelberg|location=Berlin, Heidelberg|pages=270–286|isbn=9783642635847}}</ref>;
* 1996, публікація статті про мурашкову систему<ref name=":1"/>;
* 1996, Хус і Штюцл придумали '''max-min систему мурах'''<ref>{{Cite news|title=– Ant System|url=http://dx.doi.org/10.1016/s0167-739x(00)00043-1|work=Future Generation Computer Systems|date=2000-06|accessdate=2019-02-25|issn=0167-739X|doi=10.1016/s0167-739x(00)00043-1|pages=889–914|volume=16|issue=8|first=Thomas|last=Stützle|first2=Holger H.|last2=Hoos}}</ref>;
* 1997, Доріго та Гамбарделла публікують '''систему колоній мурах'''<ref>{{Cite news|title=Ant colony system: a cooperative learning approach to the traveling salesman problem|url=http://dx.doi.org/10.1109/4235.585892|work=IEEE Transactions on Evolutionary Computation|date=1997-04|accessdate=2019-02-25|issn=1089-778X|doi=10.1109/4235.585892|pages=53–66|volume=1|issue=1|first=M.|last=Dorigo|first2=L.M.|last2=Gambardella}}</ref>;
* 1997, Шундервоерд та його колеги опублікували вдосконалене застосування до телекомунікаційних мереж<ref>{{Cite news|title=Ant-Based Load Balancing in Telecommunications Networks|url=http://dx.doi.org/10.1177/105971239700500203|work=Adaptive Behavior|date=1997-01|accessdate=2019-02-25|issn=1059-7123|doi=10.1177/105971239700500203|pages=169–207|volume=5|issue=2|first=Ruud|last=Schoonderwoerd|first2=Owen E.|last2=Holland|first3=Janet L.|last3=Bruten|first4=Leon J. M.|last4=Rothkrantz}}</ref>;
* 1998, Доріго запускає першу конференцію, присвячену мурашиним алгоритмам<ref>{{Cite book|url=http://dx.doi.org/10.7551/mitpress/1290.003.0003|title=From Real to Artificial Ants|date=2004|series=Ant Colony Optimization|publisher=The MIT Press|isbn=9780262256032}}</ref>;
* 1998, Штюцл пропонує початкові '''паралельні реалізації'''<ref>{{Cite book|url=http://dx.doi.org/10.1007/bfb0056914|title=Parallelization strategies for Ant Colony Optimization|last=Stützle|first=Thomas|date=1998|series=Lecture Notes in Computer Science|publisher=Springer Berlin Heidelberg|location=Berlin, Heidelberg|pages=722–731|isbn=9783540650782}}</ref>;
* 1999, Бонабеу, Доріго та Зераулаз видають книгу, що займається переважно штучними мурахами<ref>{{Cite news|title=Swarm Intelligence: From Natural to Artificial Systems. Eric Bonabeau , Marco Dorigo , Guy Theraulaz|url=http://dx.doi.org/10.1086/393972|work=The Quarterly Review of Biology|date=2001-06|accessdate=2019-02-25|issn=0033-5770|doi=10.1086/393972|pages=268–269|volume=76|issue=2|first=Carl|last=Anderson}}</ref>;
* 2000, спеціальний випуск журналу «Комп'ютерні системи майбутнього покоління» про алгоритми мурашок<ref>{{Cite news|title=Ant algorithms|url=http://dx.doi.org/10.1016/s0167-739x(00)00041-8|work=Future Generation Computer Systems|date=2000-06|accessdate=2019-02-25|issn=0167-739X|doi=10.1016/s0167-739x(00)00041-8|pages=v–vii|volume=16|issue=8|first=Marco|last=Dorigo|first2=Gianni|last2=Di Caro|first3=Thomas|last3=Stützle}}</ref>;
* 2000, перші програми для [[Планування ресурсів підприємства|планування]], послідовності планування і задоволення обмежень;
* 2000, Гутьяр дає перші докази [[Границя послідовності|конвергенції]] для алгоритму колоній мурашок<ref>{{Cite news|title=A Graph-based Ant System and its convergence|url=http://dx.doi.org/10.1016/s0167-739x(00)00044-3|work=Future Generation Computer Systems|date=2000-06|accessdate=2019-02-25|issn=0167-739X|doi=10.1016/s0167-739x(00)00044-3|pages=873–888|volume=16|issue=8|first=Walter J.|last=Gutjahr}}</ref>;
* 2001, перше використання мурашиних алгоритмів компаніями ([http://www.eurobios.com/ Eurobios] {{Webarchive|url=https://web.archive.org/web/20190225162445/http://www.eurobios.com/ |date=25 лютого 2019 }} та [https://www.antoptima.com/ AntOptima] {{Webarchive|url=https://web.archive.org/web/20190110173758/https://www.antoptima.com/ |date=10 січня 2019 }});
* 2001, Іреді та його колеги опублікували перший '''багатоцільовий алгоритм'''<ref>{{Cite book|url=http://dx.doi.org/10.1007/3-540-44719-9_25|title=Bi-Criterion Optimization with Multi Colony Ant Algorithms|last=Iredi|first=Steffen|last2=Merkle|first2=Daniel|last3=Middendorf|first3=Martin|date=2001|series=Lecture Notes in Computer Science|publisher=Springer Berlin Heidelberg|location=Berlin, Heidelberg|pages=359–372|isbn=9783540417453}}</ref>;
* 2002, перші програми в розробці графіка, байєсівських мереж;
* 2002, Бьянчі та її колеги запропонували перший алгоритм [[Стохастичність|стохастичної]] проблеми<ref>{{Cite book|url=http://dx.doi.org/10.1007/3-540-45712-7_85|title=An Ant Colony Optimization Approach to the Probabilistic Traveling Salesman Problem|last=Bianchi|first=Leonora|last2=Gambardella|first2=Luca Maria|last3=Dorigo|first3=Marco|date=2002|series=Parallel Problem Solving from Nature — PPSN VII|publisher=Springer Berlin Heidelberg|location=Berlin, Heidelberg|pages=883–892|isbn=9783540441397}}</ref>;
* 2004, Доріго та Штюцл публікують книгу з оптимізації колонії мурах з пресою MIT Press<ref>{{Cite book|url=http://worldcat.org/oclc/1019798642|title=Bookreview on ``Ant Colony Optimization'' by M. Dorigo, T. Stützle, MIT Press, 2004|last=M.|first=Merkle, D. Middendorf,|oclc=1019798642}}</ref>;
* 2004, Злочін та Доріго показують, що деякі алгоритми еквівалентні стохастичному спуску градієнта, метод перехресної ентропії та алгоритми для оцінки розподілу<ref>{{Cite news|title=Model-Based Search for Combinatorial Optimization: A Critical Survey|url=http://dx.doi.org/10.1023/b:anor.0000039526.52305.af|work=Annals of Operations Research|date=2004-10|accessdate=2019-02-25|issn=0254-5330|doi=10.1023/b:anor.0000039526.52305.af|pages=373–395|volume=131|issue=1-4|first=Mark|last=Zlochin|first2=Mauro|last2=Birattari|first3=Nicolas|last3=Meuleau|first4=Marco|last4=Dorigo}}</ref>;
* 2005, перше застосування до проблем [[Згортання білків|згортання білків]];
* 2012, Прабхакар і його колеги публікують дослідження, пов'язані з функціонуванням окремих мурах, які спілкуються в тандемі без феромонів, відображаючи принципи організації комп'ютерних мереж. Модель зв'язку була порівняна з [[TCP]]<ref>{{Cite news|title=The Regulation of Ant Colony Foraging Activity without Spatial Information|url=https://dx.plos.org/10.1371/journal.pcbi.1002670|work=PLoS Computational Biology|date=2012-08-23|accessdate=2019-02-25|issn=1553-7358|pmc=PMC3426560|pmid=22927811|doi=10.1371/journal.pcbi.1002670|pages=e1002670|volume=8|issue=8|language=en|first=Balaji|last=Prabhakar|first2=Katherine N.|last2=Dektar|first3=Deborah M.|last3=Gordon|editor-first=Iain D.|editor-last=Couzin}}</ref>;
* 2016, перше застосування до дизайну послідовностей [[Пептиди|пептидів]]<ref>Zaidman, Daniel; Wolfson, Haim J. (2016-08-01). «PinaColada: peptide–inhibitor ant colony ad-hoc design algorithm». ''Bioinformatics''. '''32''' (15): 2289—2296. doi:10.1093/bioinformatics/btw133. ISSN 1367-4803. <nowiki>PMID 27153578</nowiki>.</ref>;
* 2017, успішна інтеграція багатокритеріального методу прийняття рішень PROMETHEE в мурашиному алгоритмі ({{не перекладено|Алгоритм HUMANT|алгоритм HUMANT|en|HUMANT (HUManoid ANT) algorithm}})<ref>{{Cite news|title=Solving partner selection problem in cyber-physical production networks using the HUMANT algorithm|url=https://www.tandfonline.com/doi/full/10.1080/00207543.2016.1234084|work=International Journal of Production Research|date=2017-05-03|accessdate=2019-02-25|issn=0020-7543|doi=10.1080/00207543.2016.1234084|pages=2506–2521|volume=55|issue=9|language=en|first=Marko|last=Mladineo|first2=Ivica|last2=Veza|first3=Nikola|last3=Gjeldum}}</ref>.

== Див. також ==
{{Портал|Математика}}
* [[Задача оптимізації]]
* [[Теорема схем]]
* [[Функція допасованості]]
* [[Генетичний алгоритм]]

== Примітки ==
{{reflist}}

== Посилання ==
* [http://www.csit.narod.ru/subject/mag_SShI/mono.pdf Субботін С. О., Олійник А. О., Олійник О.&nbsp;О.&nbsp;Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С.&nbsp;О.&nbsp;Субботіна.&nbsp;— Запоріжжя: ЗНТУ, 2009.&nbsp;— 375 с.] {{Webarchive|url=https://web.archive.org/web/20131105131336/http://www.csit.narod.ru/subject/mag_SShI/mono.pdf |date=5 листопада 2013 }}
* [http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html Оптимізація мурашиної колонії] {{Webarchive|url=https://web.archive.org/web/20141014204655/http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html |date=14 жовтня 2014 }} {{ref-en}}

{{Методи оптимізації}}
{{Refimprove|дата=січень 2016}}
{{Algorithm-stub}}
[[Категорія:Методи оптимізації]]
[[Категорія:Еволюційні алгоритми]]
[[Категорія:Мурашки]]