РЕШЕНИЕ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ КОММИВОЯЖЕРА С ИСПОЛЬЗОВАНИЕМ ИНТЕЛЛЕКТУАЛЬНОГО МУРАВЬИНОГО АЛГОРИТМА

Егоров Денис Владимирович

студент 4 курса, кафедра математического и программного обеспечения информационных систем НИУ «БелГУ», г. Белгород

E-mail: student_belgu@mail.ru

Михелев Владимир Михайлович

научный руководитель, канд. тех. наук, доцент НИУ «БелГУ», г. Белгород

Аннотация

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

Введение

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

Концепция муравьиного алгоритма

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

Муравьи используют два способа передачи информации: прямой — обмен пищей, мандибулярный, визуальный и химический контакты, и непрямой — феромон (pheromone) — специальный секрет, откладываемый как след при перемещении муравья. Феромон — достаточно стойкое вещество, он может восприниматься муравьями несколько суток. Чем выше концентрация феромона на тропе, тем больше муравьев будет по ней двигаться. Со временем феромон испаряется, что позволяет муравьям адаптировать свое поведение под изменения внешней среды.

Принцип алгоритмов муравья (Ant algorithms), или оптимизации по принципу муравьиной колонии, был предложен Марко Доринго (Marco Doringo). Идея алгоритмов состоит в том, что хотя муравьи слепы, они умеют ориентироваться на сложной местности, находя оптимальный путь между муравейником и внешними точками. При этом в качестве маркера используется фермент, который тем концентрированней, чем больше муравьев прошли по данному пути.

Обобщенный муравьиный алгоритм

Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде:

Пока (условия выхода не выполнены)

1.  Создаём муравьёв

2.  Ищем решения

3.  Обновляем феромон

4.  Дополнительные действия {опционально}

Теперь рассмотрим каждый шаг в цикле более подробно:

1.  Создаём муравьёв

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

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

2.  Ищем решения

Вероятность перехода из вершины i в вершину j определяется по следующей формуле:

                                (1)

где  — уровень феромона,

 — эвристическое расстояние,

 — константные параметры.

При α = 0 выбор ближайшего города наиболее вероятен, то есть алгоритм становится жадным.

При β = 0 выбор происходит только на основании феромона, что приводит к субоптимальным решениям.

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

3.  Обновляем феромон

Уровень феромона обновляется в соответствии с приведённой формулой

                        (2)

где: ρ — интенсивность испарения,

L_k — цена текущего решения для k-ого муравья,

Q — параметр, имеющий значение порядка цены оптимального решения, то есть  — феромон, откладываемый k-ым муравьём, использующим ребро(i,j).

4.  Дополнительные действия

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

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

1.  Ввод матрицы расстояний D

2.  Инициализация параметров алгоритма — α,β,e,Q

3.  Инициализация рёбер — присвоение видимости η_i,j и начальной концентрации феромона

4.  Размещение муравьёв в случайно выбранные города без совпадений

5.  Выбор начального кратчайшего маршрута и определение L*

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

6.  Цикл по времени жизни колонии t=1, t_max

7.  Цикл по всем муравьям k=1,m

8.  Построить маршрут T_k(t) по правилу (1) и рассчитать длину

9.  конец цикла по муравьям

10.  Проверка всех L_k(t) на лучшее решение по сравнению с L*

11.  В случае L_k(t) если решение лучше, обновить L* и T*

12.  Цикл по всем рёбрам графа

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

14.  конец цикла по рёбрам

15.  конец цикла по времени

16.  Вывести кратчайший маршрут T* и его длину L*

Заключение

С ростом количества добавляемого при прохождении муравьем пути-феромона увеличивается и количество найденных сценариев (как оптимальных, так и α-оптимальных). Это связано с тем, что «испарение» феромона происходит медленнее и, следовательно, меньшее количество ребер удаляется во время исполнения алгоритма.

Список литературы:

1.Мак Коннелл Дж. «Основы современных алгоритмов». М: Техносфера, 2004 г. — 368 с.

2.Штовба С.Д. «Муравьиные алгоритмы» // Exponenta Pro. Математика в приложениях, 2003 г., № 4, с. 70—75.

3.Marco Dorigo and Thomas Stützle «Ant Colony Optimization», 2004 г.