Использование алгоритма муравья для решения задачи коммивояжера

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Специальная часть

1.1 Постановка задачи и анализ исходных данных

1.2 Обзор известных алгоритмов для решения поставленной задачи

1.2.1 Алгоритм А*

1.2.2 Метод ветвей и границ

1.2.3 Метод ближайшего соседа

1.2.4 Алгоритм поиска в глубину (ширину)

1.2.5 Алгоритм Дейкстры

1.2.6 Алгоритм Джонсона

1.2.7 Алгоритм муравья.

1.3 Алгоритм муравья, основные понятия.

1.3.1 Биологические основы

1.3.2 Начальная популяция

1.3.3 Движение муравья

1.3.4 Пример итерации

1.3.5 Разновидности алгоритма муравья

1.4 Построение алгоритма движения муравья и моделирование этого алгоритма на ЭВМ

1.4.1 Ограничения, накладываемые на агента в стандартной постановке задачи коммивояжера

1.4.2 Алгоритм обхода препятствий

1.4.3 Пример работы алгоритма обхода препятствий

1.4.4 Структура данных алгоритма муравья

1.4.5 Использование графа видимости в алгоритме муравья

1.4.6 Моделирование алгоритма муравья на ЭВМ

1.5 Анализ полученных результатов

2. Экономическая часть

2.1 Определение целесообразности разработки алгоритма

2.2 Определение трудоемкости разработки алгоритма и ПП.

2.3 Календарное планирование

2.4 Расчет заработной платы основного персонала

2.5 Определение затрат на создание алгоритмов и ПП

2.6 Расчет экономической эффективности

2.7 Выводы

3. Охрана труда и окружающей среды

3.1 Введение

3.2 Санитарно-гигиенические факторы

3.2.1 Микроклимат

3.2.2 Освещение

3.2.3 Электробезопасность

3.2.4 Шум

3.2.5 Вибрация

3.2.6 Электромагнитные излучения (ЭМИ)

3.2 Эргономика рабочего места

3.3 Психофизиологические факторы

3.4 Расчет освещенности

Выводы

Заключение

Список использованной литературы

Приложение 1

Приложение 2

Приложение 3

Приложение 4

Введение

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

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

Задача коммивояжера - traveling salesman problem (TSP) - является NP-сложной задачей дискретной оптимизации. Для нее еще не найдено и возможно не существует быстрых полиномиальных алгоритмов. В общем виде на графах задача формулируется следующим образом: необходимо найти минимальный маршрут, проходящий через указанные узлы графа хотя бы по одному разу с последующим возвратом в исходный узел.

В настоящее время задача коммивояжера находит много практических применений в таких областях как:

- Оптимизация в сетях

- Оптимизация маршрутов

- Приложения в кристаллографии

- Управление роботами

- Обработка печатных плат

- Исследование ДНК

Городами в различных задачах могут выступать как физические объекты, так и процессы, и другие сущности.

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

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

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

Научная новизна

Для достижения поставленных целей решены следующие задачи:

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

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

1. Специальная часть

1.1 Постановка задачи и анализ исходных данных

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

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

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

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

Координаты вершин препятствий и точек маршрута (в дальнейшем - городов) заданы дипломным руководителем. Количество городов меняется от 5 до 25 с шагом 5.

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

1.2 Обзор известных алгоритмов для решения поставленной задачи

1.2.1 Алгоритм А*

Поиск A* -- алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x). Эта функция -- сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценки расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).

Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.

Описание алгоритма

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) -- это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме).

В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.

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

Свойства

Алгоритм А* всегда находит решение, если таковое существует.

Если эвристическая функция h допустима, то есть никогда не переоценивает действительную минимальную стоимость достижения цели, то A* сам является допустимым (или оптимальным), также при условии, что мы не отсекаем пройденные вершины. Если же мы это делаем, то для оптимальности алгоритма требуется, чтобы h(x) была ещё и монотонной, или преемственной эвристикой. Свойство монотонности означает, что если существуют пути A--B--C и A--C (не обязательно через B), то оценка стоимости пути от A до C должна быть меньше, либо равна сумме оценок путей A--B и B--C. (Монотонность также известна как неравенство треугольника: одна сторона треугольника не может быть длиннее, чем сумма двух других сторон.) Математически, для всех путей x, y (где y -- потомок x) выполняется:

(1)

A* также оптимально эффективен для заданной эвристики h. Это значит, что любой другой алгоритм исследует не меньше узлов, чем A* (за исключением случаев, когда существует несколько частных решений с одинаковой эвристикой, точно соответствующей стоимости оптимального пути).

Частные случаи

В общем случае, поиск в глубину и поиск в ширину являются двумя частными случаями алгоритма A*. Для поиска в глубину возьмём глобальную переменную-счётчик, инициализировав её неким большим значением. Всякий раз при раскрытии вершины будем присваивать значение счётчика смежным вершинам, уменьшая его на единицу после каждого присваивания. Таким образом, чем раньше будет открыта вершина, тем большее значение h(x) она получит, а значит, будет просмотрена в последнюю очередь. Если положить h(x) = 0 для всех вершин, то мы получим ещё один специальный случай -- алгоритм Дейкстры.

Особенности реализации

Существует несколько особенностей реализации и приёмов, которые могут значительно повлиять на эффективность алгоритма. Первое, на что не мешает обратить внимание -- это то, как очередь с приоритетом обрабатывает связи между вершинами. Если вершины добавляются в неё так, что очередь работает по принципу «первый пришел - последний ушел», то в случае вершин с одинаковой оценкой A* «пойдёт» в глубину. Если же при добавлении вершин реализуется принцип «первый пришел - первый ушел», то для вершин с одинаковой оценкой алгоритм, напротив, будет реализовывать поиск в ширину. В некоторых случаях это обстоятельство может оказывать существенное значение на производительность.

В случае если по окончании работы от алгоритма требуется маршрут, вместе с каждой вершиной обычно хранят ссылку на родительский узел. Эти ссылки позволяют реконструировать оптимальный маршрут. Если так, тогда важно, чтобы одна и та же вершина не встречалась в очереди дважды (имея при этом свой маршрут и свою оценку стоимости). Обычно для решения этой проблемы при добавлении вершины проверяют, нет ли записи о ней в очереди. Если она есть, то запись обновляют так, чтобы она соответствовала минимальной стоимости из двух. Для поиска вершины в сортирующем дереве многие стандартные алгоритмы требуют времени O(n). Если усовершенствовать дерево с помощью хеш-таблицы, то можно уменьшить это время.

Оценка сложности

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

(2)

передвижение муравей задача коммивояжер

где h* -- оптимальная эвристика, то есть точная оценка расстояния из вершины x к цели. Другими словами, ошибка h(x) не должна расти быстрее, чем логарифм от оптимальной эвристики.

Но ещё большую проблему, чем временная сложность, представляют собой потребляемые алгоритмом ресурсы памяти. В худшем случае ему приходится помнить экспоненциальное количество узлов. Для борьбы с этим было предложено несколько вариаций алгоритма, таких как алгоритм A* с итеративным углублением (iterative deeping A*, IDA*), A* с ограничением памяти (memory-bounded A*, MA*), упрощённый MA* (simplified MA*, SMA*) и рекурсивный поиск по первому наилучшему совпадению (recursive best-first search, RBFS). /1/

1.2.2 Метод ветвей и границ

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

Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

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

В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно минимальную из полученных верхних оценок записывают в глобальную переменную m. Любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.

Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти. /2/

1.2.3 Метод ближайшего соседа

Алгоритм ближайшего соседа -- один из простейших эвристических методов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов.

Формулируется следующим образом:

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

Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма нижней граничной оценки (lower bound algorithm).

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

1.2.4 Алгоритм поиска в глубину (ширину)

Поиск в глубину (DFS) -- один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все непройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки. Пример порядка обхода дерева в глубину представлен на рисунке 1.



Рисунок 1. Порядок обхода дерева в глубину

Описание

Пусть задан граф G = (V,E), где V -- множество вершин графа, E -- множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. Из множества всех белых вершин выберем любую вершину, обозначим её v₁.

2. Выполняем для нее процедуру DFS(v₁).

3. Перекрашиваем ее в черный цвет.

4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр -- вершина )

1. Перекрашиваем вершину u в серый цвет.

2. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:

1. Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).

2. Окрашиваем w в черный цвет.

Поиск в ширину (BFS) -- другой метод обхода и разметки вершин графа. Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам -- метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д. Пример порядка обхода дерева в глубину представлен на рисунке 2.

Рисунок 2. Порядок обхода дерева в ширину

Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный ориентированный граф, содержащий в качестве своей части остовное ориентированное дерево, называемое поисковым деревом.

Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т. д.

Двунаправленный поиск в ширину

Алгоритм часто улучшает простой поиск в ширину тем, что запускаются два одновременных поиска в ширину из стартового и конечного узлов и останавливается, когда узел из одного фронта поиска находит соседний узел из другого фронта. Подобный поиск может улучшить простой поиск в ширину (обычно в 2 раза).

Наиболее сложным случаем для двунаправленного поиска является такая задача, в которой для проверки цели дано только неявное описание некоторого (возможно очень большого) множества целевых состояний, например всех состояний, соответствующих проверки цели "Мат" в шахматах. При обратном поиске потребовалось бы создать компактные описания всех состояний, которые позволяют поставить мат с помощью ходов q1,q2,q3... и т.д.; и эти описания нужно было бы сверять с состояниями, формируемыми при прямом поиске. Общего способа эффективного решения такой проблемы не существует, и в этом недостаток данного алгоритма.

1.2.5 Алгоритм Дейкстры

Алгоритм Дейкстры -- алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях. Например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием кратчайший путь -- первый (Shortest Path First).

Формулировка задачи

Дан простой взвешенный граф G(V,E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

Инициализация

Каждой вершине из V сопоставим метку -- минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово -- на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены. Метка самой вершины a полагается равной 0, метки остальных вершин -- бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как не посещенные.

Шаг алгоритма

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

Алгоритм

Обозначения:

· V -- множество вершин графа

· E -- множество ребер графа

· w[ij] -- вес (длина) ребра ij

· a -- вершина, расстояния от которой ищутся

· U -- множество посещенных вершин

· d[u] -- по окончанию работы алгоритма равно длине кратчайшего пути из a до вершины u

· p[u] -- по окончании работы алгоритма содержит кратчайший путь из a в u

Псевдокод

Присвоим

Для всех отличных от a

присвоим

Пока

Пусть -- вершина с минимальным d[v] (3)

Добавим вершину v к U

Для всех таких, что

если d[u] > d[v] + w[vu] то

изменим

изменим

Описание.

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U -- массив булевских переменных.

В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (больше максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.

На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин с флагом 0 . Последний случай возможен, если граф G несвязан.

Подводя короткий итог, можно сказать, что достоинством данного алгоритма является не только учет длины пути от исходной i-той вершины к следующей j-той вершине (как это было в алгоритме ближайшего соседа), а сумма этой длины и минимально известного расстояния до начального пункта a , указанного в метке вершины j.

1.2.6 Алгоритм Джонсона

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

Алгоритм

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

· Для всех ребер новый вес .

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

Сохранение кратчайших путей

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

(4)

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

Изменение веса

1. Для данного графа создадим новый граф , где , для некоторой новой вершины , а .

2. Расширим весовую функцию таким образом, чтобы для всех вершин выполнялось равенство .

3. Далее определим для всех вершин величину и новые веса для всех ребер .

Недостатком этого алгоритма является то, что в общем случае работа алгоритма может занять значительное время. /3/

1.2.7 Алгоритм муравья

Главная идея алгоритма муравья (метода муравьиных колоний) состоит в моделировании поведения колонии муравьев, которые способны находить кратчайший путь от муравейника до источника пищи и приспосабливаться к изменяющимся условиям внешней среды, находя новый кратчайший путь, если старый в силу каких-либо обстоятельств оказывается недоступным. При движении муравей откладывает феромон, отмечая свой путь, и эту информацию используют другие муравьи. Таким образом, взаимодействие между агентами (муравьями) происходит посредством непрямой коммуникации. /22/

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

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

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

1.3 Алгоритм муравья, основные понятия

1.3.1 Биологические основы

Известно, что насекомые, включая муравьев различных видов, термитов и некоторые виды пчел и ос, живут в колониях, составленных из большого количества взаимодействующих индивидуумов. Колонии насекомых способны к решению различных задач оптимизации, которые ни одно насекомое не было бы способно решить отдельно (например, нахождение кратчайших путей в процессе добывания корма, решения задачи при назначении рабочей силы и кластеризация при организации гнезд).

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

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

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

Принцип изменения окружающей среды как средство связи для изменения поведения называют stigmergy. Он является основным в организации в муравьиных колониях. Хотя муравьи имеют королеву, специализированного муравья, она является ответственным только за кладку яиц и не имеет никакой управляющей функции. Вместо этого, муравьиные колонии самоорганизуются.

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

Чтобы лучше понять механизм и способность муравьиных колоний сходиться к хорошим решениям при поиске кратчайшего пути от гнезда к источнику продовольствия были проведены некоторые эксперименты. /22/ При проведении экспериментов колонии муравьёв Аргентины Linep-ithema humile давали два пути идентичной длины, и после того, как прошло некоторое время, было замечено, что муравьи сходились к одной из дорожек, после чего фактически была исключена альтернатива. Чтобы проверить, сходился ли бы этот вид муравьёв к наиболее короткому из множества путей, был проведен двойной эксперимент моста, где муравьи должны были выбирать дважды между коротким и длинным путями (рис. 1.1).



Рисунок 3. Двойной эксперимент моста

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

Первоначально, все муравьи расположены на участке гнезда. Множество муравьев отправляется от гнезда в поиске продовольствия, каждый муравей оставляет феромон на своём пути, и достигает первой вилки в точке A. Так как муравьи не имеют никакой информации о том, какой путь выбрать, то есть никакой другой муравей не проходил тут ранее и не оставлял за собой след феромона, каждый муравей будет выбирать идти или вправо или влево с равной вероятностью.

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

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

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

Поведение муравьев на втором мосту в пересечениях между C и D фактически идентично поведению, показанному прежде на первом мосту между пересечениями A и B. В конечном счете, множество муравьев достигнет продовольствия и соберет некоторое количество продовольствия, чтобы принести назад к гнезду.

Достигая пересечения D, муравьи предпочтут короткий участок по тем же самым причинам, что и муравьи, начинающие перемещение из гнезда, и то же самое происходит снова в пересечении B.

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

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

Заметим, что феромон, используемый муравьями, медленно испаряется через какое-то время, что не оставляет сомнений при объяснении двойного эксперимента моста. Действительно, длины путей, которые не были выбраны в течение некоторого времени, неизменно большие, и эти пути не будут содержать почти никаких следов феромона из-за их испарения после определённого промежутка времени, далее увеличивается вероятность выбора муравьями коротких путей. Следует обратить внимание, что количество феромона на самом коротком пути имеет максимальную ценность, которая достигнута большим количеством феромона, оставленным муравьями. Укрупненная схема работы алгоритму муравья представлена на рисунке 4.

Рисунок 4. Укрупненная схема работы алгоритма муравья

Первой задачей, к которой был применён метод муравьиных колоний (алгоритм муравья), была задача коммивояжёра (Traveling Salesman Problem, TSP). Основной причиной, по которой была выбрана данная задача, является то, что в ней необходимо находить кратчайший путь, поэтому аналогия метода муравьиных колоний легко приспосабливается для решения данной задачи.

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

Первым методом был метод муравьиных систем (Ant System - AS). /23/ /24/ В дальнейшем этот метод послужил основой для многих других методов, работающих на принципе муравьиных колоний.

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

Первоначально Марком Дориго было предложено три метода муравьиных систем, различных между собой способом обновления путей - рёбер. Эти методы назывались: плотностный (ant-density), количественный (ant-quantity) и циклический (ant-cycle) методы муравьиных систем. В плотностном и количественном методах агенты оставляли феромоны в процессе составления решения, в то время как в циклическом методе агенты оставляли феромоны после окончания перемещения, т.е. после составления решения.

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

1.3.2 Начальная популяция

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

Для каждого муравья переход из города в город зависит от трех составляющих: памяти муравья списка TabuList , видимости и виртуального следа феромона.

TabuList (память муравья) -- это список, в котором хранится битовый массив, с помощью которого определяются посещённые и не посещённые узлы. Таким образом, агент должен проходить через каждый узел только один раз. Узлы в списке “текущего путешествия” Path располагаются в том порядке, в котором агент посещал их. Позже список используется для определения протяженности пути между узлами. Ясно, что список tabu возрастает при совершении маршрута и обнуляется в начале каждой итерации алгоритма. Обозначим через список городов, которые еще необходимо посетить муравью , находящемуся в городе .

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

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

В отличие от видимости след феромона является более глобальной и динамичной информацией -- она изменяется после каждой итерации алгоритма, отражая приобретенный муравьями опыт. Количество виртуального феромона на ребре на итерации обозначим через . /6/

1.3.3 Движение муравья

Движение муравья основывается на одном вероятностно-пропорциональном правиле, которое определяет вероятность перехода k-го муравья из города в город , если муравей еще не закончил путь (path), то есть не посетил все узлы сети:

(5)

где:

- - вероятность того, что муравей переместиться в узел из узла.

- - случайное число в интервале (0; 1);

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

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

Обратим внимание, что правило (5) определяет лишь вероятности выбора того или иного города. Собственно выбор города осуществляется по принципу «колеса рулетки»: каждый город на ней имеет свой сектор с площадью, пропорциональной вероятности (5). Для выбора города нужно бросить шарик на рулетку -- сгенерировать случайное число, и определить сектор, на котором этот шарик остановится.

Заметим, что хотя правило (5) не изменяется на протяжении итерации, значения вероятностей для двух муравьев в одном и том же городе могут отличаться, т. к. -- функция от -- списка еще не посещенных городов муравьем .

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

(6)

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

Результат уравнения является средством измерения пути, - короткий путь характеризуется высокой концентрацией фермента, а более длинный путь - более низкой. Затем полученный результат используется в уравнении (7), чтобы увеличить количество фермента вдоль каждой грани пройденного муравьем пути.

(7)

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

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

В начале пути у каждой грани есть шанс быть выбранной. Чтобы постепенно удалить грани, которые входят в худшие пути в сети, ко всем граням применяется процедура испарения фермента (Pheromone evaporation). Используя константу из уравнения (7), мы получаем формулу (8).

(8)

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

После того как путь муравья завершен, грани обновлены в соответствии с длиной пути и произошло испарение фермента на всех гранях, алгоритм запускается повторно. Список табу очищается, и длина пути обнуляется. Муравьям разрешается перемещаться по сети, основывая выбор грани на уравнении (5).

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

1.3.4 Пример итерации

Разберем функционирование алгоритма на простом примере, чтобы увидеть, как работают уравнения. Рассмотрим простой сценарий с двумя муравьями, которые выбирают два разных пути для достижения одной цели. На рисунке 6 показан этот пример с двумя гранями между двумя узлами ( и ).

Рисунок 6. Начальная конфигурация проблемы

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

- вес следа феромона, ;

- вес видимости, ;

- коэффициент испарения феромона,

- регулируемый параметр ;

- начальное значение феромона .

Два муравья находятся в узле и помечаются как и . Так как вероятность выбора любого пути одинакова, в этом цикле мы проигнорируем уравнение выбора пути. На рисунке 7 каждый муравей выбирает свой путь (муравей идет по верхнему пути, а муравей - по нижнему).

Рисунок 7. Путь муравья завершен

По уравнению (6) рассчитывается количество фермента, которое должно быть "нанесено".

Далее по уравнению (7) рассчитывается количество фермента, которое будет применено. Для муравьев и результат соответственно составляет:

.

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

.

Эти значения представляют новое количество фермента для каждого пути (верхнего и нижнего, соответственно). Теперь переместим Муравьев обратно в узел V₀ воспользуемся вероятностным уравнением выбора пути (5), чтобы определить, какой путь должны выбрать муравьи.

Вероятность того, что муравей выберет верхний путь (представленный количеством фермента 0.16), составляет:

Вероятность того, что муравей выберет нижний путь (представленный количеством фермента 0.28), составляет

При сопоставлении двух вероятностей оба муравья выберут нижний путь, который является наиболее оптимальным. /8/

В таблице 1 указаны основные параметры алгоритма, характеризующие данный пример.

Пройденное расстояние,	20	10
Уровень фермента/пройденное расстояние,	0.5	1.0
Количество фермента, которое было применено,	0.4	0.7
Количество фермента, которое испарилось,	0.16	0.28
Вероятность выбора верхнего/нижнего пути	0.085/0.915	0.085/0.915

Таблица 1. Характеристики пройденного пути



1.3.5 Разновидности алгоритма муравья

В связи с возможностью различного математического описания поведения муравьёв были разработаны расширения алгоритма муравья (также называемого методом муравьиных систем). К ним относятся: метод муравьиных систем, основанный на элитной стратегии; метод муравьиных систем, основанный на ранжировании (AS_rank); метод системы муравьиных колоний; макси-минный метод муравьиных систем (MAX-MIN AS - MMAS).

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

Далее был предложен метод муравьиных систем, основанный на ранжировании (AS_rank). Данный метод по своей сути является расширением элитной стратегии и заключается в следующем: агенты сортируются по длине составленных ими путей, после чего на глобально лучшем пути феромоны увеличиваются с весом w, а также увеличение феромонов производится также только для дуг, вошедших в пути (w-1) лучших агентов; при этом k-ый лучший агент будет добавлять феромон с весом (w-k) в соответствии с (9):

(9)

где - длина лучшего глобального пути.

Метод системы муравьиных колоний (Ant Colony System - ACS) улучшает алгоритм муравья путём использования информации, полученной предыдущими агентами, для изучения пространства поиска. Это достигается с помощью двух механизмов. Во-первых, используется строгая элитная стратегия при обновлении феромонов на гранях. Во-вторых, агенты выбирают следующий город для перемещения, используя так называемое, псевдослучайное пропорциональное правило: с вероятностью агент перемещается в пункт , для которого произведение количества феромонов и эвристической информации является максимальным: , в то время как с вероятностью будет применён базовый подход при определении следующего пункта для перехода, описанный в методе муравьиных систем. Значение является константой. При этом если стремится к , то используется только псевдослучайное пропорциональное правило, когда же , тогда метод муравьиных колоний работает по принципу метода муравьиных систем.

При обновлении путей, как было сказано выше, применяется строгая элитная стратегия, в соответствии с которой только агент, составивший лучшее решение, вырабатывает феромон на пути своего перемещения. Тогда количество феромонов на гранях изменяется в соответствии с формулой (10):

(10)

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

Последним отличием метода системы муравьиных колоний является то, что агенты обновляют количество феромонов в процессе составления решения (подобно плотностному и количественному методам муравьиных систем). Такой подход приводит к уменьшению вероятности выбора одинаковых путей всеми агентами. За счёт этого понижается вероятность зацикливания в локальном оптимуме.

Макси-минный метод муравьиных систем (MAX-MIN AS - MMAS) вводит нижнюю и верхнюю границу для возможных значений феромонов на грани, а также данный метод отличается подходом к определению их значения при инициализации. Практически в MMAS используется интервал значений феромонов, ограниченный и , т.е. . Количество феромонов граней при инициализации задаётся равным нижней границе интервала, что обеспечивает лучшее исследование пространства решений. В MMAS, также как и в ACS, только лучший агент (глобально лучший или локально) выполняет добавление феромонов после каждой итерации метода. Результаты вычислений /26/ показали, что лучшие результаты получаются, когда обновление феромонов выполняется с использованием глобально лучшего решения. В MMAS также часто применяется локальный поиск для улучшения его свойств. /9/

В общем виде различия между разновидностями метода муравьиных колоний можно отобразить в таблице 2.

Критерий	AS	ASrank	ACS	MMAS
Добавление феромона	После получения решения	После получения решения	В процессе получения решения	В процессе получения решения
Динамическое изменение коэффициента	Отсутствует	Отсутствует	Отсутствует	Отсутствует
Правило выбора следующего пункта	Традиционный подход	Псевдослучайное пропорциональное правило	Традиционный подход	Традиционный подход
Применение элитной стратегии	Все агенты участвуют в обновлении путей	Обновление выполняют локально лучших агентов и глобально лучший агент	Обновление выполняет только лучший (глобально или локально) агент
Использование ограничений для различных параметров	Отсутствуют	Ограничение на количество агентов, участвующих в обновлении путей	Отсутствует	Используется интервал значений феромонов
Применение локальной оптимизации	Отсутствуют	Отсутствуют	Используются традиционные методы локальной оптимизации	Отсутствует
Решаемые задачи	Задача коммивояжёра, квадратичная задача о назначениях, задача календарного планирования, транспортная задача	Задача коммивояжёра	Задача коммивояжёра, задача календарного планирования	Задача коммивояжёра, квадратичная задача о назначениях
Влияние количества агентов на нахождение результата	Сильное	Среднее	Слабое	Слабое

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

1.4 Построение алгоритма движения муравья и моделирование этого алгоритма на ЭВМ

1.4.1 Ограничения, накладываемые на агента в стандартной постановке задачи коммивояжера

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

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

Остановимся подробнее на работе со списком TabuList , потому что по аналогии с этим списком был реализован список, описывающий ограничения, накладываемые препятствиями. Для иллюстрации работы со списком TabuList рассмотрим следующий пример, представленный на рисунке 7.

Рисунок 7. Иллюстрация работы со списком TabuList

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

агент город	1	2	3	4	5
	1	0	0	1	1
	1	1	1	0	0

Таблица 3. Содержание списка TabuList на третьем шагу.

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



1.4.2 Алгоритм обхода препятствий

В данной дипломной работе необходимо решить задачу коммивояжера, на которую наложено дополнительное ограничение в виде препятствий. Препятствия представлены в виде прямоугольной, треугольной и восьмиугольной фигур (в общем случае, найдено решение для препятствий любой выпуклой формы). Координаты вершин препятствий являются узлами графа. Агент не должен пересекать границы препятствий, но может посещать их узлы. Данное дополнительное ограничение описывается списком obstacles, в котором хранится битовый массив возможных перемещений агента. В некоторых источниках граф, описываемый данным массивом также называется графом видимости (visibility graph). /27/ В данном списке между двумя узлами ( соответствует видимой грани, соответствует не видимой грани. Очевидно, что при отсутствии препятствий, данный массив должен быть заполнен нулями.