Спостерігайте, як справжня метаевристика мурашиного алгоритму (Ant Colony Optimization) наживо еволюціонує маршрути дронів доставки: справжнє підкріплення феромонних слідів сходиться до коротших багатозупинкових шляхів упродовж послідовних колоній.
Ця симуляція запускає справжній алгоритм мурашиної оптимізації (ACO) для розв'язання задачі багатозупинкової маршрутизації дронів доставки — дрон має відвідати кожну точку доставки рівно один раз і повернутися на базу, класична задача комівояжера. Замість того, щоб скриптувати маршрут, сторінка підтримує справжню матрицю феромону τ для кожної пари точок доставки. У кожній колонії кожна симульована мураха будує повний тур, повторно обираючи наступну ще не відвідану зупинку з ймовірністю, пропорційною τ(i,j)α · η(i,j)β, де η(i,j) = 1/відстань(i,j) — евристична привабливість короткого переходу. Коли кожна мураха в колонії завершує свій тур, феромон випаровується на коефіцієнт (1 − ρ), і кожна мураха відкладає новий феромон, пропорційний Q / L, на ребрах побудованого нею маршруту — тож коротші маршрути підкріплюють свої ребра набагато сильніше, ніж довгі.
Запустіть це на достатню кількість колоній, і карта слідів помітно вигострюється: слабкі, рідко використовувані ребра згасають до нуля, тоді як жменька ребер — тих, що постійно з'являються в найкоротших турах — стають яскравішими, а довжина найкращого відомого маршруту (яку відстежує живий графік) невпинно зменшується. Ви можете наживо налаштовувати кількість точок доставки, кількість мурах на колонію та швидкість випаровування ρ, а також показники ваги феромону α і ваги відстані β, що визначають, наскільки сильно мурахи довіряють досвіду колонії проти чистої відстані. Ніщо тут не заскриптовано й не запечено заздалегідь — кожна колонія справді заново виводить свої маршрути з поточного стану феромону та випадкових рішень мурах, тож перезапуск із новою картою чи іншими параметрами щоразу дає іншу криву збіжності.
Що таке мурашиний алгоритм (Ant Colony Optimization) і яку задачу він тут розв'язує?
Мурашиний алгоритм (ACO) — це метаевристика, натхненна тим, як справжні мурахи знаходять короткі шляхи між гніздом і їжею за допомогою феромонних слідів. У цій симуляції він розв'язує задачу багатозупинкової маршрутизації доставки: дрон має відвідати кожну точку доставки рівно один раз і повернутися на базу — це класична задача комівояжера (TSP). TSP є NP-складною, тож для будь-якої кількості зупинок понад жменьку перевірити кожен можливий порядок непрактично. Натомість ACO запускає багато симульованих мурах, які ймовірнісно будують кандидатні маршрути, підкріплюючи ті ребра, що частіше з'являються в коротких маршрутах, тож популяція маршрутів покращується впродовж послідовних колоній без доведення оптимальності.
Як правило ймовірності переходу ACO вирішує, куди піде кожна мураха далі?
На кожному кроці мураха, що стоїть у точці доставки i, обирає наступну ще не відвідану зупинку j з ймовірністю, пропорційною [τ(i,j)]^α × [η(i,j)]^β, де τ(i,j) — рівень феромону на ребрі (i,j), а η(i,j) = 1/відстань(i,j) — евристична привабливість: ближчі точки виглядають привабливішими. α керує тим, наскільки сильно мураха слідує накопиченому досвіду колонії (феромону), тоді як β керує тим, наскільки сильно вона слідує чистій жадібній відстані. Потім мураха робить зважений випадковий вибір (у стилі рулетки) серед усіх невідвіданих кандидатів, використовуючи ці комбіновані оцінки, тож зазвичай — але не завжди — вона обирає перспективне ребро, що підтримує дослідження колонією.
Чому феромон випаровується і що контролює швидкість випаровування ρ?
Після того як кожна колонія завершує свої тури, усі значення феромону множаться на (1 − ρ), перш ніж додаються нові відкладення. Без випаровування феромон лише накопичувався б, і ті ребра, яким пощастило рано, домінували б назавжди — заганяючи пошук у посередній розв'язок. Випаровування дозволяє слабким чи застарілим слідам згасати, щоб колонія могла продовжувати досліджувати альтернативні маршрути. Високий ρ швидко забуває історію й досліджує більше, але сходиться повільніше й шумніше; низький ρ пам'ятає довше й сходиться швидше, але ризикує зафіксуватися на ранньому, неоптимальному маршруті (передчасна збіжність).
Після випаровування кожна мураха в колонії відкладає феромон величиною Q / L на кожному ребрі туру, який вона побудувала, де L — загальна довжина маршруту цієї мурахи, а Q — фіксована константа. Оскільки відкладення обернено пропорційне довжині, мураха, що знайшла короткий маршрут, підкріплює його ребра набагато сильніше, ніж мураха, що знайшла довгий, неефективний. Упродовж багатьох колоній це диференційне підкріплення перетворює суто випадковий пошук на такий, що концентрує феромон — а отже й майбутній рух мурах — на ребрах, які постійно з'являються в коротких маршрутах.
Встановлення α = 0 змушує мурах повністю ігнорувати феромон і поводитись як жадібна евристика в стилі найближчого сусіда, керована лише η (відстанню), тож пам'ять колонії не формується і покращення з часом мінімальне. Встановлення β = 0 змушує мурах повністю ігнорувати відстань і слідувати лише феромону, що може змусити всю колонію дуже швидко підкріпити один ранній, можливо, поганий маршрут (стагнація). Класичний баланс використовує помірний α (близько 1) із сильнішим β (близько 2–5), тож раннє дослідження враховує відстань, а феромон усе ще дозволяє хорошій структурі накопичуватися між колоніями.
Графік відстежує довжину найкращого знайденого досі маршруту, яка за визначенням ніколи не може погіршитися — це біжучий мінімум. Він виходить на плато щоразу, коли жодна мураха в останніх колоніях не змогла перевершити поточного чемпіона, що очікувано: коли феромон концентрується на хороших ребрах, більшість мурах сходяться до подібних турів, і справді нові покращення стають рідшими. Довгі плато зазвичай означають, що колонія осіла поблизу локального оптимуму для поточних параметрів; збільшення швидкості випаровування, кількості мурах або показника дослідження β іноді може зрушити її з місця для пошуку коротшого маршруту.
Точний розв'язувач (метод гілок і меж, динамічне програмування чи цілочислове програмування) може гарантувати справді найкоротший можливий маршрут, але час його роботи зростає вибухово з кількістю зупинок — динамічному програмуванню вже потрібно приблизно n²·2ⁿ операцій, що стає нездійсненним задовго до n = 30. ACO відмовляється від гарантії оптимальності в обмін на масштабованість: він видає хороші, часто близькі до оптимальних, маршрути для набагато більших екземплярів за фіксований обсяг обчислень — саме такий компроміс роблять реальні системи доставки й логістики, маршрутизуючи десятки чи сотні зупинок.