Идея муравьиного алгоритма

Идея муравьиного алгоритма - моделирование поведения муравьев, связанное с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, определяя новый кратчайший путь. При своем движении муравей метит свой путь феромоном, и эта информация используется другими муравьями для выбора пути. Это элементарное правило поведения и определяет способность муравьев находить новый путь, если старый оказывается недоступным. Дойдя до преграды, муравьи с равной вероятностью будут обходить ее справа и слева. То же самое будет происходить и на обратной стороне преграды. Однако те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько передвижений он будет более обогащен феромоном. Поскольку движение муравьев определяется концентрацией феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном, до тех пор, пока этот путь по какой-либо причине не станет доступен. Очевидная положительная обратная связь быстро приведет к тому, что кратчайший путь станет единственным маршрутом движения большинства муравьев. Моделирование испарения феромона - отрицательной обратной связи - гарантирует нам, что найденное локально оптимальное решение не будет единственным - муравьи будут искать и другие пути. Если мы моделируем процесс такого поведения на некотором графе, ребра которого представляют собой возможные пути перемещения муравьев в течение определенного времени, то наиболее обогащенный феромоном путь по ребрам этого графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма. Рассмотрим конкретный пример.

Формализация задачи коммивояжера в терминах муравьиного подхода

в терминах муравьиного подхода

Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с п вершинами. Содержательно вершины графа являются городами, которые должен посетить коммивояжер, а веса ребер отражают расстояния (длины) или стоимости проезда. Эта задача является TVP-трудной, и точный переборный алгоритм ее решения имеет факториальную сложность. Приводимое здесь описание муравьиного алгоритма для задачи коммивояжера является кратким изложением статьи С. Д. Штовбы.

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

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

• 1. Муравьи имеют собственную «память». Поскольку каждый город может быть посещен только один раз, у каждого муравья есть список уже посещенных городов - список запретов. Обозначим через У, * список городов, которые необходимо посетить муравью L находящемуся в городе /.
• 2. Муравьи обладают «зрением» - видимость есть эвристическое желание посетить город у, если муравей находится в городе /. Будем считать, что видимость обратно пропорциональна расстоянию между городами

• 3. Муравьи обладают «обонянием» - они могут улавливать след феромона, подтверждающий желание посетить городу из города /, на основании опыта других муравьев. Количество феромона на ребре (у, у) в момент времени t обозначим через т,//)•
• 4. На этом основании можно сформулировать вероятностнопропорциональное правило, определяющее вероятность перехода А>го муравья из города / в город у:

где а, р - параметры, задающие веса следа феромона, при а = 0 алгоритм вырождается до жадного алгоритма (будет выбран ближайший город). Заметим, что выбор города является вероятностным, правило (8.1) лишь определяет ширину зоны города у; в общую зону всех городов У, * бросается случайное число, которое и определяет выбор муравья. Правило (8.1) не изменяется в ходе алгоритма, но у двух разных муравьев значения вероятности перехода будут отличаться, так как они имеют разный список разрешенных городов.

5. Пройдя ребро (/,у) муравей откладывает на нем некоторое количество феромона, которое должно быть связано с оптимальностью сделанного выбора. Пусть Tk(t) есть маршрут, пройденный муравьем к к моменту времени /, Lk(t) - длина этого маршрута, a Q — параметр, имеющий значение порядка длины оптимального пути. Тогда откладываемое количество феромона может быть задано в виде

Правила внешней среды определяют в первую очередь испарение феромона. Пусть р е [0, 1 ] есть коэффициент испарения, тогда правило испарения имеет вид

где т - количество муравьев в колонии.

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

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

Муравьиный алгоритм для задачи коммивояжера

• 1. Ввод матрицы расстояний D.
• 2. Инициализация параметров алгоритма - а, р, е, Q.
• 3. Инициализация ребер - присвоение видимости ц,, и начальной концентрации феромона.
• 4. Размещение муравьев в случайно выбранные города без совпадений.
• 5. Выбор начального кратчайшего маршрута и определение Т*

// основной цикл.

• 6. Цикл по времени жизни колонии t= 1, Цпах.
• 7. Цикл по всем муравьям к = 1, т.
• 8. Построить маршрут T_k{t) по правилу (8.1) и рассчитать

длину L_k(t).

• 9. Конец цикла по муравьям.
• 10. Проверка всех L_k(t) на лучшее решение по сравнению с Т*.
• 11. Если да, то обновить L * и Г*.
• 12. Цикл по всем ребрам графа.

13. Обновить следы феромона на ребре по правилам (8.2)

и (8.3).

• 14. Конец цикла по ребрам.
• 15. Конец цикла по времени.
• 16. Вывести кратчайший маршрут Г* и его длину L*.

Сложность данного алгоритма определяется непосредственно из приведенного выше текста - <9(/тах, п , т), таким образом, сложность алгоритма зависит от времени жизни колонии (/max), количества городов (п) и количества муравьев в колонии (т).