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

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

Введение

Эффективность созданных человечеством алгоритмов в главном своем предначертании проверяется практической их реализацией, а решение задач прикладного характера сопровождается детализацией используемых при этом алгоритмов [1].

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

Общая задача коммивояжера (traveling salesmen problem, TSP) [4,5] состоит в следующем: используя заданную систему транспортных соединений (дорог и т.п.) между пунктами (городами, фирмами и т.п.) в конкретной зоне обслуживания, посетить все пункты в такой последовательности, чтобы пройденный путь был минимальным [1,5]. В терминах теории графов задачу можно сформулировать следующим образом: в конечном взвешенном графе G= (V,E) найти гамильтонов цикл наименьшего веса. То есть для каждого ребра известна его стоимость . Необходимо построить цикл А, проходящий по всем вершинам ровно один раз, причем . В случае задача называется асимметричной (ATSP). Симметрия и выполнение неравенства треугольника в значительной мере облегчают решение задачи, однако они не всегда применимы.

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

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

Проиллюстрируем вышесказанное.

Обозначим муравья, идущего по верхней грани, - первым, а по нижней - вторым. Пусть верхняя грань вдвое длиннее нижней. Первоначально путь от муравейника к цели неизвестен. К тому времени как второй муравей достигнет цели, первый пройдет только пол пути. На пути в муравейник второй муравей пойдет по нижней грани, так как только она помечена ферментом. К тому моменту как первый муравей достигнет цели, верхняя грань будет помечена ферментом 1 раз, а нижняя уже 2. А значит, муравей выберет нижнюю, более короткую грань.

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

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

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

Популяция. Перед началом движения муравьев случайным образом распределяют по узлам графа. Этим самым повышается вероятность быстрого нахождения оптимального маршрута. Оптимизация количества муравьев в популяции будет рассмотрена ниже, наряду со значениями остальных параметров. Движение муравья (state transition rule) Направление движения муравья задается вероятностным уравнением. Формула 1 устанавливает вероятность, с которой k-й муравей системы, находящийся в городе r, отправится в город s:

(1)

В уравнении (1) s понимается как случайная величина. Для повышения эффективности при дальнейшем развитии алгоритма для выбора пункта назначения была введена формула (2):

(2)

где S - результат, полученный при использовании формулы (1);

- интенсивность фермента на грани между узлами i и j;

- функция, обратная длине соответствующей грани;

J_k (r) - множество узлов, еще не посещенных муравьем k, находящимся в узле r;

- параметр, контролирующий относительный приоритет фермента на пути над видимостью следующего города;

q - случайное число в диапазоне [0...1], выбираемое каждый раз при пересчете формулы;

0<q₀<1- параметр, показывает относительную важность поиска новых маршрутов, над использованием старых.

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

, (3)

где 0<р<1 - параметр. В зависимости от применяемых эвристик величина формулы (3) может находиться по следующим формулам: (I) , (II) или (III) . В первом случае алгоритм носит название Ant-Q, второй - используется для повышения производительности и называется ACS. Первый и второй алгоритмы дают аналогичные результаты. Третий случай может быть использован в случае симметричной задачи коммивояжера, хотя и резко снижает производительность алгоритма и потому редко используется на практике [2,4].

Испарение фермента (global updating rule). После завершения всеми муравьями их путешествий выделяется наиболее оптимальный путь. Для повышения эффективности поиска пути на следующей итерации ко всем граням применяется формула (4):

, (4)

где

L_gb - длина лучшего маршрута, найденного на данный момент, 0<б<1 - параметр. Вместо L_gb может быть использована длина лучшего маршрута текущей итерации. Согласно практическим наблюдениям разница между этими двумя вариантами незначительна.

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

В целом алгоритм применительно к задаче коммивояжера можно сформулировать следующим образом:

Инициализация переменных

Loop /* итерация поиска решения*/

Разметить всех муравьев

Loop /* шаги поиска*/

Для каждого муравья выбрать следующий узел, используя (2)

переместить муравья

обновить уровень фермента, используя (3)

Until все муравьи закончат построение пути

Применить испарение фермента ко всей сети, используя (4)

Until выполнено нужное число итераций

Между алгоритмами муравья и генетическими алгоритмами можно провести некую параллель. Аналог наследственной информации о лучшем решении в данном случае сохраняется в виде фермента на гранях. Величина q вносит элемент случайности в действие популяции.

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

Параметр определяет важность выбора более короткой грани. Кроме того, этот параметр позволяет проследить ценность функции з для нахождения эффективных решений за приемлемое время. На практике часто используется = 2. Параметр q₀ отвечает за нахождение новых путей, б и - за испарение фермента. Для задач небольшой размерности (n>100) используют значения q₀=0,9, б==0,1. Для определения значения ф₀ используют эвристику , где L_{nn -} оценка длины маршрута; n - количество узлов. Отдельным вопросом является также численность популяции. Зависимость величины найденного решения от количества муравьев при фиксированном числе итераций можно представить графиком, приведенном на рис.2.

Рисунок 2 - Зависимость длины найденного пути от количества муравьев

График был получен при тестировании алгоритма по следующей методике. Исходные данные: набор из 50, случайно сгенерированных городов, расстояние между которыми не превышает 500. Полученная таблица инцидентности является симметричной. Алгоритм в каждом случае производил 20 итераций поиска. Результат был усреднен между 50 запусками с одинаковым количеством муравьев.

Из графика видно, что с увеличением количества муравьев растет и качество решения. Однако не следует забывать, что время работы алгоритма линейно зависит от числа агентов. Практические исследования показывают, что оптимальное соотношение качества решения и времени работы алгоритм дает при соотношении , где m - численность муравьев; n - количество узлов [2].

Вывод