Мурашиний алгоритм: як мурахи розв’язують складні задачі

3D Simulations

🐜 Алгоритми · Рійовий інтелект

📅 Березень 2026⏱ 13 хв🟡 Середній · Останнє оновлення: 28 травня 2026 р.

Мурашиний алгоритм: як мурахи розв’язують складні задачі

Одна мураха має мозок приблизно з 250 000 нейронів. Колонія зі 100 000 мурах колективно розв’язує задачі найкоротшого шляху, що ставлять у глухий кут комп’ютери. Секрет: стигмергія — координація через хімічні стежки, без жодного плану чи централізованого керування.

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

1. Біологія мурашиних стежок

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

Це призводить до примітної емерджентної поведінки, яку біологи спостерігали у 1980-х: коли два джерела їжі розміщено на однакових відстанях, але з’єднано шляхами різної довжини, мурашина колонія незмінно збігається на коротшому шляху — без того, щоб будь-яка мураха заздалегідь знала довжини шляхів.

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

2. Стигмергія та позитивний зворотний зв’язок

Стигмергія (з грецької: stigma = мітка, ergon = робота) означає непряму координацію через зміну середовища. Жодна мураха не віддає команд; жодна мураха не має карти. Саме середовище зберігає накопичений досвід колонії як хімічний градієнт.

Дві конкурентні сили утримують систему від передчасного застрягання в локальному оптимумі:

Випаровування феромонів: стежки, залишені поганими розв’язками, згасають. Це механізм «забування», що дозволяє колонії покидати погані шляхи й заново досліджувати.
Випадковість дослідження: мурахи не слідують феромонним стежкам детерміновано. Вони мають малу ймовірність спробувати невідвідані шляхи — це «мутація», що підтримує різноманіття.

Аналогія емерджентності: стигмергія — це також те, як терміти будують терміти-куполи (до 9 метрів заввишки, з вентиляцією, грибними садами та королівськими камерами) без жодного центрального плану. Кожен терміт реагує лише на локальні стимули — проте колектив створює складну, адаптивну архітектуру.

3. Алгоритм ACO

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

Загальний цикл ACO:

Ініціалізація: розмістити невелику кількість феромону τ₀ на всіх ребрах. Розмістити m штучних мурах у випадкових вузлах.
Побудова розв’язків: кожна мураха будує повний розв’язок, відвідуючи вузли. На кожному кроці мураха обирає наступний вузол ймовірнісно, надаючи перевагу ребрам із більшою кількістю феромону й коротшою відстанню.
Оцінка розв’язків: обчислити довжину маршруту (або значення цільової функції) для розв’язку кожної мурахи.
Оновлення феромонів: випарувати феромон на всіх ребрах (помножити на 1−ρ). Потім відкласти новий феромон на ребрах, використаних найкращими розв’язками.
Повторювати до збіжності або вичерпання бюджету часу.

4. Формула ймовірності та оновлення

Імовірність переходу для мурахи у вузлі i, що обирає перейти до вузла j, дорівнює:

p(i\toj) = [τ(i,j)^α \cdot η(i,j)^β] / Σₖ [τ(i,k)^α \cdot η(i,k)^β] τ(i,j) = рівень феромону на ребрі (i,j) η(i,j) = евристична бажаність, зазвичай 1/d(i,j), де d = відстань α = параметр важливості феромону (зазвичай 1) β = параметр важливості евристики (зазвичай 2-5) Σₖ = сума по всіх невідвіданих сусідах k Якщо α \to 0: мурахи ігнорують феромони (жадібний найближчий сусід) Якщо β \to 0: мурахи сліпо слідують феромонам (лише позитивний зворотний зв’язок)

Після того як усі мурахи завершують свої маршрути, феромон оновлюється:

τ(i,j) \leftarrow (1-ρ)\cdotτ(i,j) + Δτ(i,j) ρ \in [0,1] = швидкість випаровування (зазвичай 0.1-0.5) Δτ(i,j) = Σ_ants [ Q / L_ant ], якщо мураха використала ребро (i,j), інакше 0 Q = стала відкладання феромону L_ant = загальна довжина маршруту тієї мурахи Кращі розв’язки \to коротший маршрут \to більше феромону на ребро \to вища ймовірність повторного використання

5. Варіанти ACO

Ant Colony System (ACS)

Доріго та Гамбарделла (1997). Ключові покращення: (1) лише глобально найкраща мураха відкладає феромон на своєму маршруті, (2) локальне оновлення феромону під час побудови (мураха зменшує феромон, проходячи ребро, заохочуючи дослідження інших ребер), (3) псевдовипадкове пропорційне правило — мурахи роблять найкращий детермінований крок з імовірністю q₀, інакше ймовірнісний крок. ACS зазвичай швидший і кращий за оригінальний Ant System на TSP.

Max-Min Ant System (MMAS)

Штютцле та Гоос (2000). Рівні феромону обмежені між τ_min та τ_max, що запобігає застою (коли всі мурахи слідують одним шляхом). Підкріплює лише найкраща мураха (або найкраща донині). Велике емпіричне тестування показує, що MMAS дає найкращі результати на більшості еталонів TSP.

Мурашиний алгоритм з кількома станами мурах (гіперкубовий ACO)

Нормалізує феромон до [0,1], уможливлюючи пряме порівняння між різними екземплярами задач та простіше налаштування параметрів.

6. Еталон: задача комівояжера

Задача комівояжера (TSP) — знайти найкоротший маршрут, що відвідує n міст рівно один раз — це канонічний еталон для ACO. Вона NP-складна: повний перебір потребує (n−1)!/2 маршрутів.

Кількість маршрутів TSP проти повного перебору: 10 міст: 181 440 маршрутів (можливо) 20 міст: 6\times10¹⁶ маршрутів (неможливо) 50 міст: 3\times10⁶² маршрутів (безнадійно багато) Продуктивність ACO на стандартних еталонах (TSPLIB): eil51 (51 місто, оптимум = 426): MMAS знаходить 426-429 (у межах 1%) pr1002 (1002 міста): ACO у межах 1-2% від оптимуму за секунди

ACO не гарантує оптимального маршруту, але швидко знаходить близькі до оптимальних розв’язки. Для більшості практичних задач (логістика, свердління друкованих плат, секвенування генів) відхилення 1–2% від оптимуму цілком прийнятне.

7. Застосування та обмеження

Маршрутизація мереж (AntNet): пакети в телекомунікаційних мережах маршрутизуються алгоритмами, схожими на ACO. Мурахи зондують мережу; феромони кодують статистику затримок. Динамічно адаптується до збоїв і заторів. Використовувалося в дослідженнях керування мережею AT&T.
Маршрутизація транспорту: планування доставок вантажівками з часовими вікнами, обмеженнями місткості та кількома депо. ACO незмінно входить до найкращих метаевристик на цих еталонах.
Передбачення структури білків: ACO шукає конформаційний простір послідовностей амінокислот, щоб знайти низькоенергетичні згортки.
Планування шляхів для багатьох роботів: фізичні роботи або рої дронів використовують варіанти ACO для дослідження середовищ, з віртуальними феромонами, що зберігаються у спільній пам’яті.
Відбір ознак у машинному навчанні: ACO обирає, які ознаки включити до класифікатора, трактуючи простір пошуку як граф можливих підмножин ознак.

Обмеження

Чутливість до параметрів: α, β, ρ, кількість мурах треба налаштувати. Погані параметри → повільна збіжність або передчасний застій.
Послідовне вузьке місце: оновлення феромонів потребують синхронізації між усіма мурахами. Підходи з паралелізацією частково пом’якшують це.
Швидкість збіжності: ACO повільніший за спеціалізовані точні розв’язувачі (метод гілок і меж, динамічне програмування) для малих розмірів задач. Він блискучий на великих, складних реальних задачах, де точні методи нездійсненні.
Неперервна оптимізація: ACO був розроблений для дискретних графів. Існують варіанти ACO-R (неперервна область), але вони менш переконливо конкурують з іншими метаевристиками (PSO, CMA-ES).