Метод муравьиной колонии (Ant colony optimization) Скачать в PDF

Синонимы: Муравьиный алгоритм

Разделы: Алгоритмы

Алгоритм для нахождения приближенных решений задач оптимизации на графах, таких как задача коммивояжера, транспортная задача и аналогичных задач поиска маршрутов на графах. Вычислительные затраты алгоритма полиномиально зависят от объема исходных данных.

Метод предложен бельгийским исследователем Марко Дориго в 1992 году. И хотя изначально был ориентирован на решение задач на графах, в настоящее время используется во многих приложениях анализа.

В основе метода лежит поведение муравьев некоторых видов, которые изначально перемещаются в поисках пищи случайным образом, но, найдя ее, возвращаются в свою колонию, помечая путь феромонами. Это избавляет других муравьев от необходимости случайного поиска пищи и делает его более целенаправленным: найдя путь, помеченный феромонами, муравьи движутся по нему, усиливая плотность феромонов.

Однако со временем плотность феромонов уменьшается. И происходит это тем быстрее, чем длиннее путь, поскольку интервал перемещения по нему муравьев велик. Напротив, чем путь короче и чем интенсивнее он используется, тем выше плотность феромона на нем. Таким образом, выбирая пути с наибольшей плотностью феромона, муравьи сокращают расстояние, проходимое в поисках пищи, что эквивалентно поиску кратчайшего пути на графе.

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

$P_i=(l_i^q\cdot f_i^p)/\sum _{n=0}^N(l_n^q\cdot f_n^p)$,

где $P_i$ — вероятность перехода по пути $i$-му пути, $l_i$ — длина $i$-го перехода, $f_i$ — количество феромона на $i$-ом переходе, $q$ — величина, определяющая «жадность» алгоритма, $p$ — величина, определяющая «стадность» алгоритма, при этом $q+p=1$.

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