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

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

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

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

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

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

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

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

,

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

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

results matching ""

    No results matching ""