Про оптимізацію мурашиної колонії
Оптимізація мурашиної колонії (ACO) — ймовірнісна метаевристика, натхненна поведінкою реальних мурах під час пошуку їжі, запропонована Марко Доріго в 1992 році. Реальні мурахи спочатку блукають хаотично, але залишають на шляху хімічну мітку — феромон. Коротші шляхи долаються частіше, феромон на них накопичується швидше, і інші мурахи дедалі більше тяжіють до насичених феромоном доріжок — позитивний зворотний зв’язок, що конвергує до найкоротшого маршруту. ACO успішно застосовується до задачі комівояжера, маршрутизації транспорту, мережевої маршрутизації і навіть фолдингу білків.
Симулятор розміщує набір міст (вузлів) на полотні й запускає колонію віртуальних мурах, що будують тури ймовірнісно, керуючись рівнем феромону та зворотньою відстанню. Ви можете регулювати кількість мурах, швидкість випаровування феромону (ρ), а також відносний вплив феромону (α) і відстані (β).
Поширені запитання
Як мурашка вибирає, яким ребром іти?
У кожному вузлі мурашка вибирає наступне місто з ймовірністю Pᵢⱼ = (τᵢⱼ𝑚 ⋅ ηᵢⱼᵇ) / Σ(τ𝕪𝓂 ⋅ η𝕪𝓂), де τᵢⱼ — рівень феромону на ребрі (i,j), ηᵢⱼ = 1/dᵢⱼ — евристика (обернена відстань), α керує впливом феромону, β — відстані. При α=0 алгоритм стає жадібним методом найближчого сусіда; при β=0 орієнтується лише на феромон без урахування відстані.
Що таке випаровування феромону і чому воно важливе?
Після кожної ітерації феромон на всіх ребрах зменшується на коефіцієнт (1−ρ), де ρ — швидкість випаровування, зазвичай 0,01–0,5. Без випаровування алгоритм заклинюється на першому прийнятному розв’язку, бо феромон лише накопичується. Випаровування є механізмом «забування», що запобігає передчасній збіжності та дозволяє колонії адаптуватися — аналогічно тому, як реальний феромон деградує під дією сонця й вітру.
Як ACO порівнюється з генетичними алгоритмами?
Обидва методи — популяційні метаевристики, що уникають локальних оптимумів через дослідження. ACO будує розв’язки покроково й обмінюється інформацією через феромонні сліди (стигмергія), тоді як ГА оперують повними розв’язками через схрещування й мутацію. ACO зазвичай краще підходить для маршрутних задач, ГА — гнучкіший для задач із непослідовною структурою розв’язків.
Що таке задача комівояжера?
Задача комівояжера (TSP) вимагає: маючи N міст, знайти найкоротший замкнений тур, що відвідує кожне місто рівно один раз і повертається до початку. Задача є NP-важкою — кількість можливих турів зростає як (N−1)!/2. Для 20 міст це понад 60 трильйонів варіантів. ACO знаходить близькі до оптимальних розв’язки значно швидше, ніж повний перебір.
Що регулює параметр швидкості випаровування ρ?
Висока ρ (близька до 1) — феромон зникає швидко, всі ребра залишаються майже рівноцінними, є широке дослідження, але збіжність повільна. Низька ρ (близька до 0) — феромон накопичується багато ітерацій, посилюючи кращі шляхи, але ризикуючи стагнацією. Значення 0,1–0,3 зазвичай добре балансують дослідження й експлуатацію для задач середнього розміру.
Яку роль грають параметри α і β?
α контролює, наскільки сильно мурахи надають перевагу ребрам із більшою кількістю феромону; β — наскільки сильно вони надають перевагу коротким ребрам. При типових значеннях β=5, α=1 (оригінальна стаття Доріго) евристична відстань домінує на початку, коли феромон рівномірний, і дає розумні початкові тури, а феромон поступово зрушує баланс. Занадто висока α прив’язує алгоритм до ранніх, можливо поганих, феромонних слідів.
Чи вирішує ACO інші задачі, крім маршрутизації?
Так — ACO адаптований до розфарбовування графів, планування завдань на виробництві, передбачення структури білків і навіть неперервної оптимізації (ACOR). У мережевій маршрутизації «мурашині пакети» зондують шляхи і залишають цифровий феромон, динамічно об’їжджаючи перевантаження. Cisco реалізувала варіанти цієї ідеї в адаптивних алгоритмах маршрутизації.
Що таке стигмергія?
Стигмергія — непряма координація через зміну середовища: агенти взаємодіють, модифікуючи спільне оточення, а не безпосередньо один з одним. Феромонні сліди мурах — канонічний приклад: кожна мурашка реагує на сліди попередніх і залишає власні, які впливають на наступних — без жодного центрального контролера. Стигмергія також спостерігається у будівництві термітників і гніздувань ос.
Якими є обмеження ACO?
ACO може зазнавати стагнації, коли всі мурахи сходяться до неоптимального туру і різноманітність феромону колапсує. Метод також вимагає тонкого налаштування параметрів (α, β, ρ, кількість мурах), а швидкість збіжності нижча, ніж у спеціалізованих алгоритмів для TSP. Гібридні системи ACO + локальне покращення (2-opt або 3-opt) зазвичай значно перевершують чистий ACO на великих прикладах.
Скільки мурах потрібно?
Практичне правило — по одній мурашці на місто. Більше мурах підвищують різноманітність і зменшують ризик передчасної збіжності, але збільшують обчислювальні витрати на ітерацію. Для TSP з 10–200 містами достатньо 10–50 мурах. Оптимальна кількість взаємопов’язана з ρ: швидше випаровування може компенсувати менше мурах, підтримуючи різноманітність.