О сравнении эффективности муравьиного и генетического алгоритмов при решении задач комбинаторной оптимизации

Актуальные проблемы авиации и космонавтики. Информационные технологии

УДК 519.68

О. Е. Семенкина Научный руководитель - Е. С. Семенкин Сибирский федеральный университет, Красноярск

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

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

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

Для разработки и исследования эффективности алгоритмов была использована широко известная задача коммивояжера [1]. Если имеется заданное множество из п городов, то задача коммивояжера - это задача нахождения замкнутого обхода минимальной длины, причем каждый город должен быть посещен единственный раз. В качестве тестовых задач были взяты решетки 4 на 4 и 5 на 5 городов.

Муравьиный алгоритм основан на имитации поведения муравьев в природе [2]. Почти слепые животные, такие как муравьи, справляются с задачей оты-

б

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

После прохождения полного обхода каждый муравей оставляет вещество, называемое след, на каждом пройденном ребре (1, ] между 1-м и ]-м городами.

Пусть т^) это интенсивность следа на ребре (1, ] в момент времени 1. Интенсивность следа обновляется в соответствии с формулой т^ + п) = р-т^) + Дт^, где р является коэффициентом таким, что (1-р) пред-

т к

ставляет собой испарение следа. Дт] = ^ Дт ,, где

к=1

к

Дт ,, есть количество вещества следа, оставленного на

и

единице длины ребра (1, ] к-м; оно задается формулой

д к = ; если к-й муравей использует ребро (1,]) в своем обходе,

0,

если не использует,

где Р является постоянной; Ьк - длина обхода к-го муравья.

Коэффициент р должен иметь значение меньше 1 для того, чтобы исключить неограниченное накопление следа.

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

к

Ра = 1

[ с )Пк Г

с )Пл, Г

если к - й муравей еще не посещал ] - й город,

если к - й муравей уже посещал ] - й город.

а и р являются параметрами, которые управляют относительной важностью следа и видимости.

Была разработана программа, реализующая алгоритм муравьиных колоний, и с ее помощью исследована на тестовых задачах зависимость надежности этого алгоритма от различных настроек параметров. А именно: выявлены лучшие настройки: а = 1, р = 10, р = 0.5-0.7, и установлено, что значение параметра Р существенного влияния не оказывает, а количество муравьев должно быть близко к количеству городов.

Генетический алгоритм основан на имитации естественной эволюции [3]. Каждое решение задачи является индивидом популяции, т. е. множества решений, который представлен хромосомой - списком номеров городов в порядке их посещения. В своей

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

к

0

Секция «Математические методы моделирования, управления и анализа данных»

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

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

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

У обоих алгоритмов возникли трудности с решением данной задачи. Лучший обход, найденный муравьиным алгоритмом, имеет длину 5420.57 км, а ге-

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

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

1. Мудров В. И. Задача о коммивояжере. М. : Знание, 1969. С. 62.

2. Dorigo М. & Gambardella L. M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation, 1997. 1 (1). Р. 53-66.

3. Рутковская Д., Пилиньский M., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы ; пер. с польск. И. Д. Рудинского. М. : Горячая линия - Телеком, 2006.

© Семенкина О. Е., Семенкин Е. С., 2011

УДК 519.68

И. Ф. Синяев Научный руководитель - С. С. Бежитский Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск

ОПРЕДЕЛЕНИЕ НАИЛУЧШЕГО РАСПРЕДЕЛЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ РЕСУРСОВ В АЛГОРИТМЕ PARTICLE SWARM OPTIMIZATION

Определяется наилучшее процентное соотношение параметров (частиц и итераций) в алгоритме PSO при решении задачи оптимизации на ряде тестовых многоэкстремальных функций.

Алгоритм particle swarm optimization (PSO) впервые был предложен в работе [http://www.engr.iupui. edu/~shi/Coference/psopap4.html]. Разработанный ими алгоритм довольно прост и может быть реализован буквально в нескольких десятках строчек кода на любом высокоуровневом языке программирования. Он моделирует многоагентную систему, где агенты-частицы двигаются к оптимальным решениям, обмениваясь при этом информацией с соседями.

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

На каждой итерации алгоритма направление и длина вектора скорости каждой из частиц изменяются в соответствие со сведениями о найденных оптиму-мах:

К, = Vt + * гяУ * (pierff - xt) +

,

где V* - вектор скорости частицы (V' - его У-я компонента); оа: - постоянные ускорения, р^езГ-лучшая найденная частицей точка; - лучшая

точка из пройденных всеми частицами системы; х -текущее положение частицы, а функция ^воз-

вращает случайное число от 0 до 1 включительно. После вычисления направления вектора К, частица

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

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

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