Феромонні Шляхи Мураш: Стігмергія, Найкоротші Шляхи та Колонійний Оптимізація

Без лідера, без карти, лише хімія

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

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

Позитивний зворотний зв’язок обирає найкоротший шлях

Двійкові експерименти з мостами, проведені Денеборга та його колегами (1990), перевірили це: два шляхи різної довжини з'єднують гніздо та їжу, а мурашки вільно обирають будь-який з них на розгалуженні. Спочатку вибір майже 50/50, але шлях, який випадково отримує трохи більше раннього трафіку, швидше накопичує феромони, спотворюючи подальший вибір мурах у його бік, що ще більше підсилює цей ефект – автокаталіз. Оскільки короткий шлях завершується (і, відповідно, позначається) частіше на одиницю часу, його концентрація феромонів прискорюється, і колонія сходиться на коротшому маршруті, незважаючи на те, що жодна мураха ніколи не порівнювала ці довжини.

p(вибір гілки i) = (k + феромон_i)^n / Σ_j (k + феромон_j)^n k, n: константи, які контролюють, наскільки сильно спотворення феромонами впливає на вибір, (Оригінальна модель Денеборга використовувала n ≈ 2, що давало досить різку конвергенцію «переможця-завойовника», коли один з гілок виділявся вперед). Важливою є не випадковість, а постійне випаровування: без розкладання ранній інцидент (позначений довгішим шляхом випадково) міг би стати назавжди заблокованим. Оскільки феромонний слід постійно розкладається, шлях, який більше не підсилюється, зникає, і колонія може покинути його, якщо їжа закінчиться або буде виявлено коротший маршрут – саме це випаровування дозволяє забувати неправильні відповіді та коригувати їх.

p(choose branch i) = (k + pheromone_i)^n / Σ_j (k + pheromone_j)^n

k, n: constants controlling how strongly pheromone bias translates into choice
      (Deneubourg's original model used n ≈ 2, giving a fairly sharp,
      winner-take-most convergence once one branch pulls ahead)

Оптимізація колоній мурах

Марко Дориго формалізував це як оптимізацію колоній мурах (ОКМ), метаеуристику для комбінаторних задач, таких як задача про туристи. Віртуальні мурахи будують маршрути по одержуваним ребрам, з урахуванням віртуальної матриці феромонів; після кожного покоління маршрути з хороших (коротких) результатів посилюються, а весь феромон трохи випаровується. З плином багатьох ітерацій матриця феромонів зосереджується на ребрах, які зустрічаються в коротких маршрутах, і популяція сходиться до майже оптимальних рішень без обчислення точного рішення.

для кожного покоління: кожна віртуальна мураха будує повний маршрут, вибираючи наступне місто з ймовірністю ∝ феромон(ребро)^α · (1/відстань)^β випаровування: феромон *= (1 − ρ) для всіх ребер посилення: феромон(ребро) += Δ / довжина_маршруту для кожного використаного ребра (найбільший стимул для ребер, які зустрічаються в найкращих маршрутах, що були знайдені до цього) ОКМ та її родичі використовуються для маршрутизації транспортних засобів, маршрутизації мереж та планування роботи на виробництві (job-shop scheduling), загалом там, де простір пошуку занадто великий, щоб його перерахувати, але має достатньо структури, щоб посилювати частково хороші рішення було вигідно.

for each generation:
  each virtual ant builds a full tour, choosing next city
      with probability ∝ pheromone(edge)^α · (1/distance)^β
  evaporate: pheromone *= (1 − ρ)   for all edges
  reinforce: pheromone(edge) += Δ / tour_length   for every edge used
             (biggest boost to edges on the best tours found so far)

Чому це надійно

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

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

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

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