Спостерігайте, як мурахи знаходять їжу за допомогою феромонів — поведінка, що виникає з простих правил і створює складний колективний інтелект. Кожна мураха слідує локальним хімічним градієнтам, але разом вся колонія знаходить оптимальні шляхи.
Стигмергія — непряме спілкування через навколишнє середовище. Мурахи залишають феромони, що приваблюють інших, створюючи позитивний зворотний зв'язок для ефективного збирання їжі.
Використовуйте повзунки для зміни кількості мурах, джерел їжі та швидкості випаровування феромонів. Клікайте на поле, щоб додати їжу. Правою кнопкою видаліть її. Увімкніть режим двох колоній, щоб спостерігати конкуренцію.
Реальні мурашині колонії використовують понад 20 різних феромонних хімікатів. Ця модель симулює два найважливіших: «їжа знайдена» та «шлях додому».
Ця симуляція моделює поведінку мурах під час пошуку їжі через стигмергію — форму непрямого спілкування, за якої мурахи залишають хімічні феромонні стежки, що скеровують інших членів колонії. Кожна мураха дотримується простих локальних правил: блукає, відчуває концентрацію феромону попереду, повертає до найсильнішого сигналу й залишає власну стежку. З цих мінімальних поведінок колонія в цілому відкриває ефективні маршрути до джерел їжі — класичний приклад рійового інтелекту та емерджентної складності.
Пошук їжі мурашиними колоніями надихнув сімейство алгоритмів оптимізації мурашиною колонією (ACO), вперше формалізованих Марко Дориго на початку 1990-х років. Сьогодні ACO широко застосовують для розв'язання комбінаторних задач, як-от маршрутизація транспорту, проєктування мереж і задача комівояжера.
Стигмергія — механізм непрямої координації, за якого особини змінюють спільне навколишнє середовище, а інші реагують на ці зміни. У мурашиних колоніях спільним середовищем виступають феромонні стежки, залишені на землі, — жодній мурасі не потрібно спілкуватися напряму з іншою. Цей принцип дозволяє колоніям із тисяч особин колективно розв'язувати складні задачі пошуку їжі без будь-якого центрального керування.
Використовуйте повзунки на панелі, щоб налаштувати кількість мурах (10–300), джерела їжі (1–8), швидкість згасання феромонів, швидкість мурах і кут огляду для зчитування сигналу. Клацніть лівою кнопкою будь-де на канві, щоб розмістити нове джерело їжі; правою кнопкою — щоб прибрати його. Увімкніть «Два колонії», щоб спостерігати за двома конкурентними гніздами з окремими феромонними системами. Натисніть «Restart» у будь-який момент, щоб перезапустити симуляцію з поточними налаштуваннями.
Помаранчево-червоні стежки позначають феромон «до їжі», який залишають мурахи, що несуть їжу назад до гнізда, — він скеровує мурах-шукачок до знайдених джерел їжі. Сині стежки — це феромон «додому», який залишають мурахи-шукачки, і він допомагає мурахам з їжею знайти гніздо. Саме поєднання цих двох накладених градієнтних полів скеровує всю колонію до ефективності.
Концентрація феромону в кожній клітинці сітки множиться на коефіцієнт згасання (0 < d < 1) кожен кадр симуляції, моделюючи випаровування. Кількість, що залишається після t кадрів, слідує експоненційній кривій: P(t) = P(0) × d^t. Коли d близьке до 1 (наприклад, 0,999), стежки зберігаються багато секунд; коли d нижче (наприклад, 0,9), вони згасають за частку секунди. Баланс між швидкістю виділення феромону та швидкістю згасання визначає, чи здатен позитивний зворотний зв'язок підтримувати стабільну стежку.
У класичному експерименті з подвійним містком Госса та колег (1989) колонії пропонували два маршрути різної довжини між гніздом і їжею. Спочатку мурахи випадково обирали обидва, але оскільки коротший маршрут займав менше часу, мурахи, що поверталися ним, підкріплювали його більшою кількістю феромону за одиницю часу — швидше, ніж стежки довшого маршруту встигали набрати таку саму силу. Колонія стабільно сходилася на коротшому шляху — той самий механізм зворотного зв'язку, що ця симуляція демонструє з кількома джерелами їжі на різних відстанях.
Правильно — це один із найважливіших моментів у розумінні рійового інтелекту. Жодна мураха не знає мети колонії; кожна дотримується лише локальних хімічних сигналів і кількох простих поведінкових правил. Здавалося б, розумна поведінка на рівні колонії — пошук коротких шляхів, пріоритет багатших джерел їжі, відновлення після перешкод — виникає повністю з взаємодії багатьох простих агентів. Ця децентралізована самоорганізація — визначальна риса складних адаптивних систем.
Марко Дориго представив алгоритм Ant System у своїй кандидатській дисертації 1992 року в Міланському політехнічному університеті, надихнувшись етологічними дослідженнями пошуку їжі у видів на кшталт Lasius niger. Перша стаття про ACO була опублікована разом з Альберто Колорні та Вітторіо Маніеццо в 1991 році. Пізніше Дориго розширив підхід у Колонія Мурах System (1997) та варіантах MAX-MIN Ant System, які досі конкурентоспроможні на еталонних задачах маршрутизації. У 2015 році він отримав премію IEEE Frank Rosenblatt Award частково за цю роботу.
Boids (зграйна поведінка) поділяє ту саму основу рійового інтелекту: агенти дотримуються локальних правил, а глобальний порядок виникає сам по собі. Мураха Лангтона демонструє одноагентний клітинний автомат із дивовижно складною довгостроковою поведінкою. Симуляція задачі комівояжера на цьому сайті використовує ACO безпосередньо як розв'язувач. Генетичні алгоритми належать до ширшого класу натхнених природою метаевристик. Симуляції слизовика моделюють подібний механізм «виділити і слідувати» феромону в організмі Physarum polycephalum.
Оптимізацію мурашиною колонією застосовують у логістиці (маршрутизація на кшталт UPS і FedEx), маршрутизації мережевих пакетів (AntNet), плануванні шляху роботів, передбаченні згортання білків та плануванні виробничих цехів. Телекомунікаційні компанії використовували алгоритми, натхнені ACO, для динамічної переспрямування трафіку в обхід перевантажень. У проєктуванні чипів ACO допомагає розміщувати й з'єднувати компоненти інтегральних схем. Її головна перевага — стійкість до динамічних змін: оскільки мурахи продовжують досліджувати, колонія здатна адаптуватися, коли середовище змінюється, — перевага над статичними оптимізаторами.
Активні напрями досліджень включають гібридні системи ACO з машинним навчанням, де ваги феромону визначаються прогнозами нейронної мережі, багатокритеріальну ACO для одночасної оптимізації вартості й надійності, а також квантово-натхненні варіанти, що ефективніше досліджують простір розв'язків. З біологічного боку дослідники використовують кальцієву візуалізацію та швидкісне відео, щоб картографувати індивідуальне прийняття рішень щодо феромонів у видів Camponotus та Pogonomyrmex з мілісекундною роздільною здатністю, а результати живлять точніші алгоритмічні моделі.
Це агентна модель збирання їжі мурахами, яка повністю керується локальними правилами. Кожна мураха блукає, відчуває концентрацію феромонів у трьох напрямках попереду й повертає до найсильнішого сигналу, водночас залишаючи власну стежку. На сітці відстежуються два скалярні поля: стежка «до їжі», яку прокладають мурахи у пошуку, і стежка «додому», яку прокладають ті, що повертаються. Поєднання згасання стежок із позитивним зворотним зв'язком дозволяє колонії сходитися на коротких маршрутах — це приклад стигмергії, принципу, що лежить в основі оптимізації за мурашиними колоніями.
Емерджентний пошук шляху простими агентами. Мурахи зчитують феромон у конусі прямо, ліворуч і праворуч, заданому кутом огляду, повертають до найгустішої клітинки, узятої за 12 пікселів попереду, і додають невелике випадкове блукання. Стежки зберігаються як дві сітки Float32Array (клітинки по 4 пікселі), що множаться на коефіцієнт згасання кожен кадр, тож невикористані шляхи зникають, а підкріплені — лишаються.
Повзунки задають кількість мурах (10–300), число джерел їжі (1–8), згасання феромонів (0,9–0,999), швидкість мурах і кут огляду для зчитування (10–120°). Лівий клік додає джерело їжі; правий клік прибирає найближче. Позначте «Дві колонії», щоб зіткнути гніздо A з гніздом B, кожне з власними стежками. Панель показує зібрану їжу, кількість мурах і FPS; «Restart» перезапускає все.
Реальні мурахи використовують понад двадцять різних стежкових і тривожних феромонів. Ця модель абстрагує лише два канали — «їжа знайдена» та «шлях додому» — проте цієї мінімальної пари достатньо, щоб відтворити знамениті досліди з подвійним містком, у яких колонії надійно знаходять коротший із двох маршрутів.
Стигмергія — це непряма координація через навколишнє середовище, а не через прямі повідомлення. Мураха змінює світ, залишаючи феромонну позначку, і ця позначка впливає на наступну мураху, що проходить повз. Жодна мураха не має ні карти, ні плану, проте накопичені позначки дозволяють колонії поводитися так, ніби вони в неї є — саме це й візуалізує ця симуляція.
На кожному кроці мураха зчитує сітку феромонів, за якою наразі слідує — стежку їжі під час пошуку, стежку додому під час перенесення їжі — у трьох точках за 12 пікселів попереду: прямо, ліворуч і праворуч, розділених кутом огляду. Вона повертає до того напрямку, де сигнал найсильніший, а потім додає невеликий випадковий поштовх, щоб рій продовжував досліджувати, а не застигав на одному шляху.
Згасання — це множник, який застосовується до кожної клітинки сітки в кожному кадрі, від 0,9 до 0,999. Значення близькі до 0,999 змушують стежки зберігатися дуже довго, тож навіть погані маршрути затримуються, і колонія адаптується повільно. Нижчі значення швидко стирають стежки, змушуючи постійно досліджувати наново. Найцікавіша поведінка виникає посередині, де добрі шляхи підкріплюються швидше, ніж згасають.
Вона точно відтворює основний механізм: залишити, слідувати й випарувати. Реальні мурахи додають чинники, які ця модель опускає, як-от інтенсивність вербування на стежку, рельєф і безліч типів хімікатів. Схема подвійної стежки й експоненційне згасання тут відображають стандартну підручникову модель і алгоритм оптимізації за мурашиними колоніями, тож це обґрунтоване концептуальне, а не біологічно точне зображення.
Оптимізація за мурашиними колоніями, або ACO, — це клас алгоритмів, натхнених саме цією поведінкою збирання їжі. Віртуальні мурахи будують кандидатні розв'язки, залишають феромон пропорційно до якості розв'язку, а випаровування знецінює старіші вибори. Запущений на графі замість відкритого поля, той самий цикл «залишити-слідувати-згаснути» розв'язує задачі маршрутизації на кшталт задачі комівояжера — ось чому ця симуляція належить до сімейства алгоритмів.