ACO: Як Мурахи Вирішують Важкі Проблеми

Стигмерія: координація без командира

У 1959 році ентомолог П’єр-Поль Грасс вперше використав термін ‘стигмерія’ – це координація, яка відбувається повністю через спільне середовище, а не шляхом безпосереднього сигналу. Реальні мурахи ніколи не видають інструкцій один одному. Кожна мураха залишає феромоновий слід під час ходьби, і кожна мураха, що йде за нею, реагує лише на накопичений слід, залишений всією колонією. Якщо поставити перешкоду між пахотню камеру та джерело їжі з коротким об’їздом і довгим, мурахи спочатку розкидаються рівномірно по обох маршрутах. Мурахи, які пройшли коротшим шляхом, повертаються раніше й залишають феромон швидше, тому коротший шлях накопичує запах швидше – позитивний зворотний зв’язок, який протягом декількох хвилин спрямовує майже весь трафік на оптимальний маршрут, незважаючи на те, що жодна мураха ніколи не бачить всю картину.

Від стигмерегії до алгоритму

Оптимізація колоній мурах (ACO), запропонована Марко Доріго в 1992 році, перетворює цю поведінку на загального розв’язувача для комбінаторних задач, найчастіше — задачу про туристи: знайти найкоротший гамільтонів цикл через n міст. Кількість можливих маршрутів становить (n−1)!/2 – для 20 міст це вже приблизно ~6×10¹⁶, тому грубе обчислення неможливе. Кожне ребро (i, j) між двома містами несе дві величини: фіксовану відстань d[i][j] та змінний рівень феромонів τ[i][j], а також похідну видимість η[i][j] = 1/d[i][j], яка сприяє коротким ребрам.

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

Пробудований вибір крайових елементів та оновлення феромонів

Стоячи в місті i, мураха обирає наступне невідвідане місто j з ймовірністю пропорційною сумі феромонів та видимості, зважених за показниками α і β:

p[i][j] = ( τ[i][j]^α · η[i][j]^β ) / Σ_l∈allowed ( τ[i][l]^α · η[i][l]^β ) α — коефіцієнт, що визначає вагу накопичених феромонів (зазвичай: 1) β — коефіцієнт, що визначає вагу віддаленості (зазвичай: 2–5) allowed — множина міст, які ще не відвідані цією мурахою Після завершення роботи всіх мурах відбувається оновлення феромонів у два етапи – випаровування та відкладення:

τ[i][j] ← (1 − ρ) · τ[i][j] // випаровування, ρ ≈ 0.1 τ[i][j] ← τ[i][j] + Σ_k Δτ_k[i][j] // відкладення Δτ_k[i][j] = Q / L_k якщо мураха k використала край (i,j), інакше 0 Q — константа, L_k — довжина туру мурахи k Випаровування – це не незначна деталь – без нього перша посередньо хороша траєкторія, що була знайдена, продовжувала б лише накопичувати феромони назавжди, і колонія ніколи б не переглянула її. Мурахи, які знайшли коротші тури, відкладають пропорційно більше феромонів (Q/L є більшим, коли L менша), тому хороші краї найшвидше зміцнюються.

p[i][j] = ( τ[i][j]^α · η[i][j]^β ) / Σ_l∈allowed ( τ[i][l]^α · η[i][l]^β )
  α — weight given to accumulated pheromone (typical: 1)
  β — weight given to raw distance (typical: 2–5)
  allowed — the set of cities not yet visited by this ant

Міні-Макс ACO: усунення передчасного збігу

Простий Ант System має відому слабкість, яку називають застій: після кількох сотень ітерацій практично всі мурахи слідують одному й тому ж маршруту, і дослідження повністю припиняється. MAX-MIN Ант System (Stützle & Hoos, 2000) встановлює обмеження для кожного значення феромону всередині чітких меж τ_min ≤ τ[i][j] ≤ τ_max та дозволяє лише найкращій мурашиній колонії з даного раунду залишати феромони на краю. Це забезпечує, щоб кожен край був достатньо правдоподібним для повторного відвідування пізніше, що призводить до результатів на 15–35% кращих за класичний Ант System на великих прикладах.

Де насправді використовується ACO

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

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.