Cybernetics Wiki
Advertisement

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

В основе алгоритма лежит поведение муравьиной колонии — маркировка более удачных путей большим количеством феромона. Работа начинается с размещения муравьёв в вершинах графа (городах), затем начинается движение муравьёв — направление определяется вероятностным методом, на основании формулы вида: , где: вероятность перехода по пути , величина, обратная весу (длине) -ого перехода, количество феромона на -ом переходе, величина, определяющая «жадность» алгоритма, величина, определяющая «стадность» алгоритма и

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

В литературе было предложено несколько метаэвристических моделей 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)

Ссылки[]





Advertisement