Муравьиные алгоритмы

Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии, англ. ant colony optimization, ACO) — один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также аналогичных задач поиска маршрутов на графах. Подход предложен бельгийским исследователем Марко Дориго (Marco Dorigo). Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии к пище.

В основе алгоритма лежит поведение муравьиной колонии — маркировка более удачных путей большим количеством феромона. Работа начинается с размещения муравьёв в вершинах графа (городах), затем начинается движение муравьёв — направление определяется вероятностным методом, на основании формулы вида: $P_i=\frac{{l_i}^{q}\cdot {f_i}^{p}}{\sum_{k=0}^{N}{{l_k}^{q}\cdot {f_k}^{p}}}$, где: P_i вероятность перехода по пути i, l_i величина, обратная весу (длине) i-ого перехода, f_i количество феромона на i-ом переходе, q величина, определяющая «жадность» алгоритма, p величина, определяющая «стадность» алгоритма и q + p = 1

Решение не является точным и даже может быть одним из худших, однако, в силу вероятностности решения, повторение алгоритма может выдавать (достаточно) точный результат.

В литературе было предложено несколько метаэвристических моделей ACO. Среди них три наиболее успешные:

• 1) ant system (Dorigo 1992, Dorigo et al. 1991, 1996)
• 2) ant colony system (ACS) (Dorigo & Gambardella 1997)
• 3) MAX-MIN ant system (MMAS) (Stutzle & Hoos 2000)

Ссылки

• Оптимизация муравьиной колонии(англ.)
• Муравьиный алгоритм. Библиография