Муравьиные алгоритмы. Задача коммивояжёра. Программное обеспечение

Два муравья из муравейника должны добраться до пищи, которая находится за препятствием. Во время перемещения каждый муравей выделяет немного феромона, используя его в качестве маркера.
При прочих равных каждый муравей выберет свой путь. Первый муравей выбирает верхний путь, а второй - нижний. Так как нижний путь в два раза короче верхнего, второй муравей достигнет цели за время t1.

Первый муравей в этот момент пройдет только половину пути (рисунок 2).
Когда один муравей достигает пищи, он берет один из объектов и возвращается к муравейнику по тому же пути. За время t2 второй муравей вернулся в муравейник с пищей, а первый муравей достиг пищи (рисунок 3).
При перемещении каждого муравья на пути остается немного феромона. Для первого муравья за время t0t2 путь был покрыт феромонами только один раз. В то же самое время второй муравей покрыл путь феромонами дважды. За время t4 первый муравей вернулся в муравейник, а второй муравей уже успел еще раз сходить к еде и вернуться. При этом концентрация феромона на нижнем пути будет в два раза выше, чем на верхнем. Поэтому первый муравей в следующий раз выберет нижний путь, поскольку там концентрация феромона выше.
Рис. 2. Рис. 3.
Рисунок 2
Рисунок 3

Рисунок 4 – Блок-схема работы генетического алгоритма.
Генетический алгоритм(ГА) и муравьиный алгоритм (Ant Colony System – ACS) считаются «фаворитами» поисковых алгоритмов.
Наиболее наилучшим из числа поисковых алгоритмов считается ГА. Правда, он также обладает минусами, связанными с преждевременной сходимостью. ГА предоставляет приближенное решение задачи, он так же может быть распараллелен, блок схема генетического алгоритма изображена на рисунке 4.

Таким образом, основой поведения муравьиной колонии предназначается низкоуровневая связь, вследствие которой, колония предполагает собой разумную систему, блок схема муравьиного алгоритма показана на рисунке 5.
Рисунок 5 – Блок-схема муравьиного алгоритма

С течением времени надобность, а значит и вероятность выбора самого короткого пути увеличивается, из-за того, что количество откладываемого феромона обратно пропорционально длине маршрута и задается формулой 1.
(1)
Рисунок 6 – Распределение вероятности

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

В начале движения из вершины 1 муравей имеет четыре возможных пути: в вершину 2, 3, 4 или 5. Вычислим вероятности перехода в эти вершины
Вычисляем границы четырех секторов
, j=2,3,4,5 вероятностей:
Таким образом, отрезок [0,100] разбился на четыре участка

Остается запустить генератор случайных чисел и узнать, куда попадает случайное число. В нашем случае генератор дает
=65, что указывает на третий участок 57,5<65<75,89. Следовательно, муравей должен направиться к вершине 4.
Из вершины 4 только три возможные пути: 4-2, 4-3, 4-5. Пройденная вершина 1 попадает в список запрещенных вершин.
Вероятности перехода в эти вершины
Вычисляем границы трех секторов
, j=2,3,5 вероятностей:
Таким образом, отрезок [0,100] разбился на три участка

Случайное число =61, полученное генератором случайных чисел попадает на второй участок. Этот участок указывает на вершину 3. Далее муравей будет выбирать маршрут из этой вершины.
При выходе из вершины 3 имеется только 2 возможности - направиться в вершину 2 или 5. Остальные вершины попадают в список запрещенных вершин. Оценим возможности перехода:
Таким образом, отрезок [0,100] разбился на два участка
“5”
“2”
Случайное число =35, полученное генератором случайных чисел указывает на вершину 2.
В вершине 2 выбор делать не приходиться. Все вершины, кроме 5 попали в список запрещенных вершин, поэтому дальнейший путь муравья очевиден. Сначала он идет в вершину 5, а затем завершает маршрут в 1, там, откуда он и вышел. Общая длина маршрута 1-4-3-2-5-1 равна

Программа составлена в среде Delphi
Зададим начальные значения: количество городов, интенсивность феромона и стоимость маршрута.

После подсчета программа выводит кратчайший путь 1-2-3-4-5, и длину пути равную 220. Интенсивность феромона на путях после прохождения по ним муравьев увеличилась.

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

Для исследования работы муравьиного алгоритма проведен вычислительный эксперимент. Предложенным алгоритмом и методом полного перебора решена задача распределения m файлов среди n узлов сети, m=5, n=3. Объемы файлов - случайные числа.