Сравнительный анализ модификаций алгоритма муравья

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

УДК 004.032.026:004.3

Национальный исследовательский Иркутский государственный технический университет 664074, г Иркутск, ул. Лермонтова 83.

Сравнительный анализ модификаций алгоритма муравья

Т.В. Маланова Маланова Т.В., доцент кафедры автоматизированных систем , e-mail: malanova_tanya@mail.ru, Н.С. Серебрянская Серебрянская Н.С. студентка, , e-mail: argentum365@gmail.com

Аннотация

модификация муравей комбинаторный алгоритм

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

Ключевые слова: алгоритм муравья; задачи комбинаторной оптимизации; ACS; MMAS.

Annotation

Ant algorithm modifications for solving combinatorial optimization problems are studied. It is shown that the initial parameters of the algorithm (pheromone quantity, visibility, evaporation coefficient) significantly affect the output of the algorithm. It is found that the modification of ACS algorithm allows to find the optimal path for fewer steps than MMAS modification. 

Key words: ant algorithm, combinatorial optimization problems, ACS, MMAS.

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

В [3] представлены основные модификации алгоритма муравья: AS, ASrank, MaxMinAS, ACS, Ant-3-opt, Ant-Q, отличающиеся процедурой обновления феромона. В зависимости от начальных параметров (коэффициента испарения, количества феромона, отложенного муравьем, количества городов, расстояния между городами) указанные модификации дают различные результаты. При решении конкретных практических задач проблема заключается в выборе модификации алгоритма, при этом настройка параметров играет важную роль [4]. В статье приведен сравнительный анализ двух модификаций алгоритма муравья (MaxMinAS, ACS) в зависимости от начальных параметров (видимость города, количество феромона, коэффициент испарения феромона). Выбор модификаций обусловлен тем, что модификации AS, ASrank, MaxMinAS основаны на глобальном обновлении феромона, а ACS, Ant-3-opt, Ant-Q основаны на локальном обновлении феромона. Таким образом, из каждой выделенной группы выбрана одна модификация.

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

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

Алгоритм муравья (AS). Функциональная схема алгоритма решения задачи коммивояжера с использованием классического алгоритма муравья представлена на рис. 1, в которой - начальное значение феромона, m - число муравьев, - номер итерации.

Обновление феромона происходит по следующей схеме.

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

, (1)

где - коэффициент испарения (0 < < 1) ;

- количество феромона, положенного муравьями на дугу, соединяющую город и .

Рис. 1. Алгоритм муравья (AS)

рассчитывается по формуле:

, (2)

где - количество феромона, отложенного k-м муравьём на дугу, соединяющую город и , которое рассчитывается по формуле:

(3)

здесь - константа;

- общая длина маршрута, пройденного k-ым муравьём.

Вероятность перемещения муравья из города в город на -й итерации определяется по формуле

(4)

где - список городов, ещё не пройденных k-м муравьём;

- видимость - величина обратно пропорциональная расстоянию между городами

( = d_ij);

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

,

где - список пройденных муравьем городов;

- количество городов [3].

Параметры и определяют важность феромона и видимости города. Если , то феромон не играет никакой роли, и на вероятность выбора следующего города влияет только его видимость. Если , то для выбора города используется только феромон. [2].

Модификации алгоритма муравья. Рассмотрим следующие модификации алгорит-ма муравья: Max-Min Ant Systems (MaxMinAS, MMAS), Ant Colony Systems (ACS). Отличительные особенности модификаций приведены на рис. 2, 3.

Рис. 2. Модификация алгоритма муравья MMAS

Рис. 3. Модификация алгоритма муравья ACS

В модификации MMAS феромон может колебаться в интервале [Tmin, Tmax]. Начальное количество феромона при инициализации алгоритма принимается равным Tmax. В данной модификации обновление феромона производится по формуле (1) на пути, найденном либо муравьем с наилучшим результатом (s^gb), либо «наилучшим за итерацию» (s^ib) [3].

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

, (5)

здесь - показатель локального испарения, , а .

В данной модификации обновляется феромон муравья с наилучшим результатом (s^gb), в отличие от MMAS выбор муравья не происходит. Обновление феромона лучшего муравья производится по формуле

. (6)

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

, (7)

где - случайное число в интервале [0,1];

- параметр баланса между использованием накопленных знаний и исследованием новых решений ;

- случайный город, выбранный на основе вероятностей, рассчитанных по формуле (4) [3].

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

Таблица 1 Начальные параметры (набор 1)

Полученные графики скорости сходимости представлены на рис. 4.

Рис. 4. Графики скорости сходимости

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

Изменив начальные параметры инициализации алгоритма (табл. 2), получим другие графики скорости сходимости (рис. 5) для проведения сравнительного анализа.

Таблица 2. Начальные параметры (набор 2)

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

Рис. 5. Графики скорости сходимости при измененных начальных параметрах

Заключение

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

Библиографический список

1. М. Тим Джонс. Программирование искусственного интеллекта в приложениях; пер. с англ. А.И. Осипова. М. : ДМК Пресс, 2004.

2. Чураков М., Якушев А. Муравьиные алгоритмы [Электронный ресурс]. Режим доступа: http://rain.ifmo.ru/cat/data/theory/unsorted/ant-algo-2006/article.pdf

3. Чипига А.Ф., Зорин А.А. Исследование применения алгоритмов муравьев для решения задач комбинаторной оптимизации на примере задачи коммивояжера // Сб. науч. тр. / СевКавГТУ, 2006, № 2.

4. Светличная В.А., Червинская Н.В., Хаустова Д.А. Использование алгоритмов муравьиных колоний при решении задач оптимизации календарного планирования. Наукові праці ДонНТУ, Вып. 148, 2009.

5. Ant colony optimization / M. Dorigo, T. Stьtzle. A Bradford Book, 2004.

Размещено на Allbest.ru