Применение муравьиных алгоритмов при решении задач оптимизации

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

Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с n вершинами. Содержательно вершины графа являются.

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

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

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

1. Муравьи имеют собственную «память». Поскольку каждый город может быть посещён только один раз, то у каждого муравья есть список уже посещённых городов — список запретов. Обозначим через J i, k список городов, которые необходимо посетить муравью k, находящемуся в городе i. 2. Муравьи обладают «зрением» — видимость есть эвристическое желание посетить город j, если муравей находится в городе i. Будем считать, что видимость обратно пропорциональна расстоянию между городами.

3. Муравьи обладают «обонянием» — они могут улавливать след феромона, подтверждающий желание посетить город j из города i на основании опыта других муравьёв. Количество феромона на ребре (i, j) в момент времени t обозначим через.

На этом основании мы можем сформулировать вероятностно-пропорциональное правило, определяющее вероятность перехода k-ого муравья из города i в город j:

(1).

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

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

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

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

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

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

(3).

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

Постановка задачи. Задан взвешенный граф G1 (рис.1). Найти длину пути муравья в задаче коммивояжера. Начальная вершина 1. Дана последовательность Р = 65,61,35 случайных чисел, выпавших при выборе очередной вершины. Расстояния, между вершинами k, j и интенсивность феромона на ребре [k, j] заданы таблицы.

Ребро.
1−2 1−3 1−4 1−5 2−3 2−4 2−5 3−4 3−5 4−5	38 74 59 45 46 61 72 49 85 42	3 2 2 2 1 1 1 2 2 1

Решение Секторы вероятности перехода сортировать по возрастанию номеров вершин. использовать формулу вероятности перехода из вершины k в j.

где б=1, в=1, =1/.

Рис. 1. Представим решение в виде:

1. В начале движения из вершины 1 муравей имеет четыре возможных пути: в вершину 2, 3, 4 или 5. Вычислим вероятности перехода в эти вершины.

Вычисляем границы четырех секторов, j=2,3,4,5 вероятностей:

Таким образом, отрезок [0,100] разбился на четыре участка.

Остается запустить генератор случайных чисел и узнать, куда попадает случайное число. В нашем случае генератор дает =65, что указывает на третий участок 57,5<65<75,89. Следовательно, муравей должен направиться к вершине 4.

2. Из вершины 4 только три возможные пути: 4−2, 4−3, 4−5. Пройденная вершина 1 попадает в список запрещенных вершин.

Вероятности перехода в эти вершины.

Вычисляем границы трех секторов, j=2,3,5 вероятностей:

Таким образом, отрезок [0,100] разбился на три участка.

Случайное число =61, полученное генератором случайных чисел попадает на второй участок. Этот участок указывает на вершину 3. Далее муравей будет выбирать маршрут из этой вершины.

3. При выходе из вершины 3 имеется только 2 возможности — направиться в вершину 2 или 5. Остальные вершины попадают в список запрещенных вершин. Оценим возможности перехода:

Таким образом, отрезок [0,100] разбился на два участка.

Случайное число =35, полученное генератором случайных чисел указывает на вершину 2.

4. В вершине 2 выбор делать не приходиться. Все вершины, кроме 5 попали в список запрещенных вершин, поэтому дальнейший путь муравья очевиден. Сначала он идет в вершину 5, а затем завершает маршрут в 1, там, откуда он и вышел. Общая длина маршрута 1−4-3−2-5−1 равна.