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

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

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

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

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

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

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

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

,

где — вероятность перехода по пути -му пути, — длина -го перехода, — количество феромона на -ом переходе, — величина, определяющая «жадность» алгоритма, — величина, определяющая «стадность» алгоритма, при этом .

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