Решение оптимизационной задачи коммивояжера с использованием интеллектуального муравьиного алгоритма
Авторы: Егоров Д.В., Михелев В.М.
Источник: V студенческая международная заочная научно–практическая конференция Научное сообщество студентов XXI столетия
Аннотация
Егоров Д.В., Михелев В.М. Решение оптимизационной задачи коммивояжера с использованием интеллектуального муравьиного алгоритма. Данная статья рассматривает применимость муравьиного алгоритма к задаче коммивояжера. В данном алгоритме используется интеллектуальная многоагентная система, в которой каждый агент (муравей) действует автономно по несложным правилам, для нахождения решений указанной задачи. Для решения задачи агенты используют «феромон», оставляемый на гранях транспортной сети, в процессе поиска оптимального решения. Алгоритм показывает хорошую производительность, для задачи коммивояжера.
Введение
В последние несколько лет не малый интерес возрос к природным алгоритмам, в которых объедены математические методы, в которые заложен принцип принятия решения. Целью данной статьи является изложение теоретических основ и примеров практического применения муравьиных алгоритмов – нового перспективного метода оптимизации, базирующегося на моделировании поведения колонии муравьев. Муравьиные алгоритмы серьезно исследуются европейскими учеными с середины 90–х годов. На сегодня уже получены хорошие результаты муравьиной оптимизации таких сложных комбинаторных задач, как: задачи коммивояжера, задачи оптимизации маршрутов грузовиков, задачи раскраски графа, квадратичной задачи о назначениях, оптимизации сетевых графиков, задачи календарного планирования и других.
Концепция муравьиного алгоритма
Муравьи относятся к социальным насекомым, живущим внутри некоторого коллектива–колонии. Основу «социального» поведения муравьев составляет самоорганизация – множество динамических механизмов, обеспечивающих достижение системой глобальной цели в результате низкоуровневого взаимодействия ее элементов. Принципиальной особенностью такого взаимодействия является использование элементами системы только локальной информации. При этом исключается любое централизованное управление и обращение к глобальному образу, репрезентирующему систему во внешнем мире.
Муравьи используют два способа передачи информации: прямой – обмен пищей, мандибулярный, визуальный и химический контакты, и непрямой – феромон (pheromone) – специальный секрет, откладываемый как след при перемещении муравья. Феромон – достаточно стойкое вещество, он может восприниматься муравьями несколько суток. Чем выше концентрация феромона на тропе, тем больше муравьев будет по ней двигаться. Со временем феромон испаряется, что позволяет муравьям адаптировать свое поведение под изменения внешней среды.
Принцип алгоритмов муравья (Ant algorithms), или оптимизации по принципу муравьиной колонии, был предложен Марко Доринго (Marco Doringo). Идея алгоритмов состоит в том, что хотя муравьи слепы, они умеют ориентироваться на сложной местности, находя оптимальный путь между муравейником и внешними точками. При этом в качестве маркера используется фермент, который тем концентрированней, чем больше муравьев прошли по данному пути.
Обобщенный муравьиный алгоритм
Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде:
- Проверка условия выхода. Если проверка не пройдена, переход на шаг 2.
- Создаём муравьёв.
- Ищем решения.
- Обновляем феромон.
- Дополнительные действия (опционально).
- Создаём муравьёв.
- Ищем решения.
- Обновляем феромон.
- Дополнительные действия (опционально).
Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи. Потому что для каждой задачи способ размещение муравьёв является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.
На этом же этапе задаётся начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.
Вероятность перехода из вершины i в вершину j определяется по следующей формуле:
где τij(t) – уровень феромона, dij – эвристическое расстоние, α,β – константные параметры.
При α = 0 выбор ближайшего города наиболее вероятен, то есть алгоритм становится жадным.
При β = 0 выбор происходит только на основании феромона, что приводит к субоптимальным решениям.
Поэтому необходим компромисс между этими величинами, который находится экспериментально.
Уровень феромона обновляется в соответствии с приведённой формулой
где p – интенсивность испарения, Lk – цена текущего решения для k-ого муравья, Q – параметр, имеющий значение порядка цены оптимального решения.
Обычно здесь используется алгоритм локального поиска, однако, он может также появиться и после поиска всех решений.
Пошаговое описание муравьиного алгоритма для решения задачи Коммивояжера
- Ввод матрицы расстояний D.
- Инициализация параметров алгоритма – α, β, Q.
- Инициализация рёбер – присвоение видимости ηi,j и начальной концентрации феромона.
- Размещение муравьёв в случайно выбранные города без совпадений.
- Выбор начального кратчайшего маршрута и определение L.
- Цикл по времени жизни колонии t=1, tmax.
- Цикл по всем муравьям k=1,m.
- Построить маршрут Tk(t) по правилу (1) и рассчитать длину.
- Конец цикла по муравьям.
- Проверка всех Lk(t) на лучшее решение по сравнению с L.
- В случае Lk(t) если решение лучше, обновить L и T.
- Цикл по всем рёбрам графа/.
- Обновить следы феромона на ребре по правилам (2).
- Конец цикла по рёбрам.
- Конец цикла по времени.
- Вывести кратчайший маршрут T и его длину L.
Основной цикл
Заключение
С ростом количества добавляемого при прохождении муравьем пути-феромона увеличивается и количество найденных сценариев (как оптимальных, так и ?-оптимальных). Это связано с тем, что «испарение» феромона происходит медленнее и, следовательно, меньшее количество ребер удаляется во время исполнения алгоритма.