Біологічне натхнення

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

Приклад: процес оновлення феромонів

# Pseudocode for updating pheromone trails in a simple graph

# Assume pheromone is a dictionary: pheromone[(i, j)] gives the pheromone value on edge (i, j)
# delta_pheromone is a dictionary: delta_pheromone[(i, j)] accumulates pheromone deposited by all ants

rho = 0.5  # Evaporation rate (0 < rho < 1)
for (i, j) in pheromone:
    # Evaporation: reduce existing pheromone
    pheromone[(i, j)] *= (1 - rho)
    # Deposit: add new pheromone from this iteration
    pheromone[(i, j)] += delta_pheromone.get((i, j), 0.0)

Застосування ACO: Задача комівояжера

Алгоритм оптимізації на основі поведінки мурах (Ant Colony Optimization, ACO) особливо ефективний для вирішення комбінаторних задач оптимізації, де метою є знаходження найкращого порядку або вибору з кінцевої множини. Класичним прикладом є задача комівояжера (TSP), у якій необхідно знайти найкоротший можливий маршрут, що проходить через заданий набір міст рівно один раз і повертається до початкового міста. У ACO кожна штучна мураха будує тур, ймовірнісно обираючи наступне місто для відвідування, під впливом як інтенсивності феромону, так і відстані до кожного ще не відвіданого міста. Після завершення турів усіма мурахами феромонні сліди оновлюються для підсилення коротших, ефективніших маршрутів, тоді як менш оптимальні шляхи втрачають феромон через випаровування. Цей ітеративний процес дозволяє ACO ефективно досліджувати великий простір пошуку та зближуватися до високоякісних рішень для складних задач маршрутизації та планування.