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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Поведінка мурах надихнула метаевристичну техніку оптимізації

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

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

,

де:

 — ймовірність переходу шляхом ,
 — довжина -ого переходу,
 — кількість феромонів на -ому переході,
 — величина, яка визначає «жадібність» алгоритму,
 — величина, яка визначає «стадність» алгоритму і

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

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

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

Огляд[ред. | ред. код]

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

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

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

Прийняття рішень[ред. | ред. код]

Aco branches.svg

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

  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 є константою.

(1)

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

(2)

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

Випаровування феромонів[ред. | ред. код]

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

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

(3)

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

Області застосування[ред. | ред. код]

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

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

Історія[ред. | ред. код]

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

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

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


Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Marco., Dorigo, (2004). Ant colony optimization. Cambridge, Mass.: MIT Press. ISBN 9780262256032. OCLC 57182707. 
  2. 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
  3. 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
  4. Waldner, Jean-Baptiste (2008). Nanocomputers and Swarm Intelligence. London: ISTE John Wiley & Sons. с. 214. ISBN 978-1-84704-002-2. 
  5. Waldner, Jean-Baptiste (2007). Inventer l'Ordinateur du XXIème Siècle. London: Hermes Science. с. 259–265. ISBN 978-2-7462-1516-0. 
  6. Waldner, Jean-Baptiste (2008). Nanocomputers and Swarm Intelligence. London: ISTE John Wiley & Sons. p. 215. ISBN 978-1-84704-002-2.
  7. Russell, R.A. Ant trails - an example for robots to follow?. Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C) (IEEE). ISBN 0780351800. doi:10.1109/robot.1999.774005. Процитовано 2019-02-25. 
  8. Fujisawa, Ryusuke; Dobata, Shigeto; Sugawara, Ken; Matsuno, Fumitoshi (2014-08-26). Designing pheromone communication in swarm robotics: Group foraging behavior mediated by chemical substance. Swarm Intelligence 8 (3). с. 227–246. ISSN 1935-3812. doi:10.1007/s11721-014-0097-z. Процитовано 2019-02-25. 
  9. Herianto; Sakakibara, Toshiki; Kurabayashi, Daisuke (2007-12). Artificial pheromone system using RFID for navigation of autonomous robots. Journal of Bionic Engineering 4 (4). с. 245–253. ISSN 1672-6529. doi:10.1016/s1672-6529(07)60038-9. Процитовано 2019-02-25. 
  10. Arvin, Farshad; Turgut, Ali Emre; Krajník, Tomáš; Yue, Shigang (2016-03-07). Investigation of cue-based aggregation in static and dynamic environments with a mobile robot swarm. Adaptive Behavior 24 (2). с. 102–118. ISSN 1059-7123. doi:10.1177/1059712316632851. Процитовано 2019-02-25. 
  11. Arvin, Farshad; Samsudin, Khairulmizam; Ramli, Abdul Rahman; Bekravi, Masoud (2011). Imitation of Honeybee Aggregation with Collective Behavior of Swarm Robots.. International Journal of Computational Intelligence Systems 4 (4). с. 739. ISSN 1875-6883. doi:10.2991/ijcis.2011.4.4.26. Процитовано 2019-02-25. 
  12. Schmickl, Thomas; Thenius, Ronald; Moeslinger, Christoph; Radspieler, Gerald; Kernbach, Serge; Szymanski, Marc; Crailsheim, Karl (2008-08-08). Get in touch: cooperative decision making based on robot-to-robot collisions. Autonomous Agents and Multi-Agent Systems 18 (1). с. 133–155. ISSN 1387-2532. doi:10.1007/s10458-008-9058-5. Процитовано 2019-02-25. 
  13. Garnier, Simon; Combe, Maud; Jost, Christian; Theraulaz, Guy (2013-03-28). Do Ants Need to Estimate the Geometrical Properties of Trail Bifurcations to Find an Efficient Route? A Swarm Robotics Test Bed. PLoS Computational Biology 9 (3). с. e1002903. ISSN 1553-7358. doi:10.1371/journal.pcbi.1002903. Процитовано 2019-02-25. 
  14. Arvin, Farshad; Turgut, Ali Emre; Bazyari, Farhad; Arikan, Kutluk Bilge; Bellotto, Nicola; Yue, Shigang (2014-05). Cue-based aggregation with a mobile robot swarm: a novel fuzzy-based method. Adaptive Behavior 22 (3). с. 189–206. ISSN 1059-7123. doi:10.1177/1059712314528009. Процитовано 2019-02-25. 
  15. 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.
  16. Ермолаев С.Ю., Слюсар В.И. Синтез антенн на основе муравьиных алгоритмов оптимизации. // 19-я Международная Крымская конференция «СВЧ-техника и телекоммуникационные технологии» (КрыМиКо’2009). Материалы конференции.- Севастополь, 14-18 сентября. — 2009. — С. 431 - 432.
  17. Ermolaev S.Y., Slyusar V.I. Antenna synthesis based on the ant colony optimization algorithm.// 7-я Международная конференция по теории и технике антенн (ICATT’09), Львов, Украина, 6 - 9 октября 2009 г.. — 2009. — С. 298 - 300.
  18. Wolfe, M. Massive parallelism through program restructuring. [1990 Proceedings] The Third Symposium on the Frontiers of Massively Parallel Computation (IEEE Comput. Soc. Press). ISBN 0818620536. doi:10.1109/fmpc.1990.89491. Процитовано 2019-02-25. 
  19. Grassé, Plerre-P. (1959-03). 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. Insectes Sociaux 6 (1). с. 41–80. ISSN 0020-1812. doi:10.1007/bf02223791. Процитовано 2019-02-25. 
  20. Deneubourg, J.L.; Pasteels, J.M.; Verhaeghe, J.C. (1983-01). Probabilistic behaviour in ants: A strategy of errors?. Journal of Theoretical Biology 105 (2). с. 259–271. ISSN 0022-5193. doi:10.1016/s0022-5193(83)80007-1. Процитовано 2019-02-25. 
  21. Goss, S.; Aron, S.; Deneubourg, J. L.; Pasteels, J. M. (1989-12). Self-organized shortcuts in the Argentine ant. Naturwissenschaften 76 (12). с. 579–581. ISSN 0028-1042. doi:10.1007/bf00462870. Процитовано 2019-02-25. 
  22. Reiher, P.L.; Jefferson, D.; Wieland, F. Limitation Of Optimism In The Time Warp Operating System. 1989 Winter Simulation Conference Proceedings (IEEE). ISBN 0911801588. doi:10.1109/wsc.1989.718752. Процитовано 2019-02-25. 
  23. Tagliabue, Lavinia C.; Ciribini, Angelo L.C.; Pasquinelli, Alice; Giuda, Giuseppe M. Di; Villa, Valentina; Angelis, Enrico De (2016-10-10). Cognitive Adaptve Urban Systems for the Living Built Environment. Global Science & Technology Forum (GSTF). doi:10.5176/2425-0112_uppd16.43. Процитовано 2019-02-25. 
  24. Tagliabue, Lavinia C.; Ciribini, Angelo L.C.; Pasquinelli, Alice; Giuda, Giuseppe M. Di; Villa, Valentina; Angelis, Enrico De (2016-10-10). Cognitive Adaptve Urban Systems for the Living Built Environment. Global Science & Technology Forum (GSTF). doi:10.5176/2425-0112_uppd16.43. Процитовано 2019-02-25. 
  25. Dorigo, M.; Maniezzo, V.; Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics) 26 (1). с. 29–41. ISSN 1083-4419. doi:10.1109/3477.484436. Процитовано 2019-02-25. 
  26. Appleby, Stephen; Steward, Simon (1999). Mobile Software Agents for Control in Telecommunications Networks. Software Agents for Future Communication Systems. Berlin, Heidelberg: Springer Berlin Heidelberg. с. 270–286. ISBN 9783642635847. 
  27. Dorigo, M.; Maniezzo, V.; Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics) 26 (1). с. 29–41. ISSN 1083-4419. doi:10.1109/3477.484436. Процитовано 2019-02-25. 
  28. Stützle, Thomas; Hoos, Holger H. (2000-06). – Ant System. Future Generation Computer Systems 16 (8). с. 889–914. ISSN 0167-739X. doi:10.1016/s0167-739x(00)00043-1. Процитовано 2019-02-25. 
  29. Dorigo, M.; Gambardella, L.M. (1997-04). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1 (1). с. 53–66. ISSN 1089-778X. doi:10.1109/4235.585892. Процитовано 2019-02-25. 
  30. Schoonderwoerd, Ruud; Holland, Owen E.; Bruten, Janet L.; Rothkrantz, Leon J. M. (1997-01). Ant-Based Load Balancing in Telecommunications Networks. Adaptive Behavior 5 (2). с. 169–207. ISSN 1059-7123. doi:10.1177/105971239700500203. Процитовано 2019-02-25. 
  31. From Real to Artificial Ants. Ant Colony Optimization. The MIT Press. 2004. ISBN 9780262256032. 
  32. Stützle, Thomas (1998). Parallelization strategies for Ant Colony Optimization. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. с. 722–731. ISBN 9783540650782. 
  33. Anderson, Carl (2001-06). Swarm Intelligence: From Natural to Artificial Systems. Eric Bonabeau , Marco Dorigo , Guy Theraulaz. The Quarterly Review of Biology 76 (2). с. 268–269. ISSN 0033-5770. doi:10.1086/393972. Процитовано 2019-02-25. 
  34. Dorigo, Marco; Di Caro, Gianni; Stützle, Thomas (2000-06). Ant algorithms. Future Generation Computer Systems 16 (8). с. v–vii. ISSN 0167-739X. doi:10.1016/s0167-739x(00)00041-8. Процитовано 2019-02-25. 
  35. Gutjahr, Walter J. (2000-06). A Graph-based Ant System and its convergence. Future Generation Computer Systems 16 (8). с. 873–888. ISSN 0167-739X. doi:10.1016/s0167-739x(00)00044-3. Процитовано 2019-02-25. 
  36. Iredi, Steffen; Merkle, Daniel; Middendorf, Martin (2001). Bi-Criterion Optimization with Multi Colony Ant Algorithms. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. с. 359–372. ISBN 9783540417453. 
  37. Bianchi, Leonora; Gambardella, Luca Maria; Dorigo, Marco (2002). An Ant Colony Optimization Approach to the Probabilistic Traveling Salesman Problem. Parallel Problem Solving from Nature — PPSN VII. Berlin, Heidelberg: Springer Berlin Heidelberg. с. 883–892. ISBN 9783540441397. 
  38. M., Merkle, D. Middendorf,. Bookreview on ``Ant Colony Optimization by M. Dorigo, T. Stützle, MIT Press, 2004. OCLC 1019798642. 
  39. Zlochin, Mark; Birattari, Mauro; Meuleau, Nicolas; Dorigo, Marco (2004-10). Model-Based Search for Combinatorial Optimization: A Critical Survey. Annals of Operations Research 131 (1-4). с. 373–395. ISSN 0254-5330. doi:10.1023/b:anor.0000039526.52305.af. Процитовано 2019-02-25. 
  40. Prabhakar, Balaji; Dektar, Katherine N.; Gordon, Deborah M. (2012-08-23). The Regulation of Ant Colony Foraging Activity without Spatial Information. У Couzin, Iain D. PLoS Computational Biology (en) 8 (8). с. e1002670. ISSN 1553-7358. PMC PMC3426560. PMID 22927811. doi:10.1371/journal.pcbi.1002670. Процитовано 2019-02-25. 
  41. 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. PMID 27153578.
  42. Mladineo, Marko; Veza, Ivica; Gjeldum, Nikola (2017-05-03). Solving partner selection problem in cyber-physical production networks using the HUMANT algorithm. International Journal of Production Research (en) 55 (9). с. 2506–2521. ISSN 0020-7543. doi:10.1080/00207543.2016.1234084. Процитовано 2019-02-25. 

Посилання[ред. | ред. код]