Лекции: Лекции в различных форматах

Распознанный текст из изображения:

ИРОГРАММИРОВАИИЕ, 2005, Ч вЂ” 4, с. 1 — 1б

У7К бядя.об

МЪРРАВЬИНЫЕ АЛГОРИТМЫ: ТЕОРИЯ И БРИМЕБЕБИЕ

!с! 2ООб г. С. Д. Штовбв

Винницкий национальныа технический университет

21021 Украина, Винница, Хмельницкое изоссе, 95

Е-та!1: яЫойайкяи.ия1и.и1пп1са.иа, яИоиьаОяи11оп1иче.сот

Поступила в редакцию

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

онных сетях.

ВВЕДЕНИЕ

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

Цель настоящей статьи состоит в изложении теоретических основ и примеров практического применения муравьиных алгоритмов — нового перспективного подхода к оптимизации, базирующегося на имитации поведения колонии муравьев. Колония муравьев может рассматриваться как многоагентная система, в которой каждыИ агент — муравей функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, функционирование системы получается на удивление разумным: "... гнезда многих видов [муравьев] поражают своими размерами, сложной и рациональноИ архитектоникой. Дороги, тоннели, разбросанные по территории убежища для тлей и червецов, грибные сады... Разнообразные способы запасания и хранения пищи, фактическое приручение ряда видов насекомых..." [1].

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

тирующие такое поведение муравьев, предложены в начале девяностых в Италии [2]. В международном журнале первая статья по муравьиным алгоритмам [3] была опубликована в 199бг., и уже через несколько лет сформировалось отдельное научное направление 'РоевоИ интеллект и муравьиные алгоритмы', в котором интенсивно работают европейские ученые. Раз в дна года в Бельгии проводится международный научный семинар по муравьиным алгоритмам и роевому интеллекту — 1пьегпа11опа! 'яяог!гяЬор оп Ап1 Со1опу Орсппьта1юп ап<1 Якагш !п1е11!иепсе. Организовываются специальные "муравьиные" секции и семинары на конгрессах н крупных конференциях; издаются спецвыпуски международных научных журналов.

Распознанный текст из изображения:

10

ШТОВБА

-. б

г. б

о

х

о4

Ю

Р 2

а

яры ММАб АСб Абп+ргв Абц Абн+р1э Абн Аб

Рис. 5. Сравнение муравьиных алгоритмов по относительной точности по данным таблицы 1.

где

оргг — длина оптимального маршрута для

1-оИ тестовоИ задачи из таблицы 1;

Е, — усредненная длина маршрутов, найден-

ных муравьиным алгоритмом для 1-оИ те-

стовоИ задачи.

тб[г+ 1) = [1 — р) . ты[г), [4, 1) б Т (г) и [1,7) ~ Тт;

ПРОГРАММИРОВАНИЕ Хв 4 2ПОЗ

гласно которому откладываемое количество феромонов Ьти [1) на ребре [1 — Я пропорционально [~ аат ти [~)).

Компьютерные эксперименты с задачами коммивояжера [14] показывают, что среднее время оптимизации удается значительно сократить, если феромоны обновлять не на маршруте Т4, а на ребрах лучшего на текущеИ итерации маршрута. Для задач большой размерности время оптимизации сокращается при смешан- ноИ стратегии, когда на некоторых итерациях феромоны откладываются по маршруту Т+, а на некоторых — по лучшему текущему маршруту. Прн этом частота обновления феромонов по маршруту Тэ должна увеличиваться во время выполнения алгоритма [14].

В таблице 1 сравниваются результаты решения задач коммивояжера из библиотеки [10] следующими алгоритмами: АБ — базовый муравьи- ныИ алгоритм; АЯŠ— базовыИ муравьиныИ алгоритм с элитными муравьями; АЗК вЂ” ранго- выИ муравьиный алгоритм; АСЬ вЂ” алгоритм му- равьиноИ колонии; ММАЯ вЂ” макс-минный му- равьиныИ алгоритм. Символы црргз" означают применение механизма сглаживания следов. Все алгоритмы синтезировали одно н то же количество маршрутов; !0000 и для симметричных задач Е1151, КгоА100, Х)198 и 20000 и для асимметричных задач Ну48р, Р170, Кго124р и Ргч170. Числа в названии задач указывают количество городов [п). Числа в ячейках таблиц— длины найденных кратчайших маршрутов коммивояжера, усредненные за 25 прогонов. Полужирным шрифтом выделены лучшие решения.

На рис. 5 сравниваются муравьиные алгорит-

мы по критерию средней относительноИ точно-

сти:

1 Ь, — орд

уг = — ) ' ' 100%,

7,, ор1,

Из рис. 5 видно, что лучшую эффективность демонстрируют макс-минные алгоритмы, затем идут алгоритмы муравьиноИ колонии. Заметим, что по данным [14] для двух симметричных задач большой размерности АСС532 и Иа1783 [10] усредненные длины маршрутов, найденных ММА8, были короче, чем длины даже наилучших маршрутов, найденных АС8.

3.5, Пучший-худгиий муравьиный алгоритм

Лучший-худший алгоритм отличается от базового муравьиного алгоритма следующими тремя правилами:

Ц феромоны добавляются на ребра наилучшего маршрута Т4 по правилу [5);

2) на данной итерации г феромоны испаряются только с наихудшего текущего маршрута

Распознанный текст из изображения:

МУРАВЬИНЫЕ АЛГОРИТМЫ: ТЕОРИЯ И ПРИМЕНЕНИЕ

Таблица 2. Сравнение метаэвристических методов оптимизации

маршрута коммивояжера [6]

Е1150 Е1175 КгоА100

Тестовая задача

580 нет данных

443

Имитированный отжиг

(81щп!а1ед Аппеа!1п8)

545

22761

428

Генетические алгоритмы

(Сепе11с А18оН1Итз)

426

542 нет данных

Эволюционное программирование

(Ечо1н11опагу РгоЕгашш1п8)

Алгоритмы муравьиной колонии 425

(Ап1 Со!опу Вув1еш)

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

Для задачи коммивояжера в список кандидатов включают города, расположенные по соседству. Например, для задачи с 2392 городами Рг2392 [10] оптимум можно найти, если исследовать продолжения маршрутов в 8 ближайших городов [17]. Список кандидатов может использоваться со всеми рассмотренными модификациями муравьиных алгоритмов. Впервые список кандидатов был внедрен в муравьиные алгоритмы в работе [18].

т, (г)+Ат если а = О, т; (1) — гьт если а~О,

т,з(й+ Ц =

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

З,б. Список кандидатов

3) феромонныИ след на ребре (1 — 7) с вероятностью р „, подвергается мутации:

где 1, г' = 1,..., и, 1 ~ з, 1Хт „, — случайное число из диапазона, зависящего от номера итерации и среднего количества феромонов на ребрах маршрута Тт; а 6 (О, 1) — случайное число.

Первое правило усиливает вклад наилучшего решения. Второе правило ослабляет вклад наихудшего текущего решения. Третье правяло является аналогом операции мутации в генетических алгоритмах. Оно введено для диверсификации решений через расширение области поиска. При приближении стагнации, когда текущие лучшее и худшее решения отличаются лишь несколькими дугами, происходит "перезагрузка" — количество феромонов на всех ребрах принимается равным т,. = то, 1,7' = 1,, и. В работе [16] экспериментально установлено, что среди рассмотренных выше алгоритмов при решении квадратичных задач о назначениях наилучшую производительность демонстрирует лучшиИ-худшиИ муравьиный алгоритм.

Для задач большой размерности целесообразно использовать список кандидатов. Он представляет собой неболыпоИ список предпочти-

ПРОГРАММИРОВАНИЕ М вЂ” ' и 2005

3.7. Гибридизация муравьиных алгвришмвв

Распознанный текст из изображения:

ШТОВВА

Таблица 3. Сравнение метаэврнстических методов решения квадратичной задачи о на-

значениях !6]

Тестовая задача

Е!яЬа1е!

!19)

!4пйеп! Ыпйеп!

Ыпйеп!

(20)

Ыпйеп1

Кгагпр

(12) !15)

!30)

!30)

Имитированный отжиг

!8!шп1а1еб Аппеа!!пй)

578 1150 2570 578 1150 2570

6128

17937024

17212548

89800

Табу-поиск !ТаЪп БеагсЬ)

90090

Генетические алгоритмы

(Пепе!!с А18ог!1Ьтя)

588 1160 2688 598 1168 2654

17640584 19600212

6748

108830

Эволюционны стратегии

(Ехо!п!!оп 81гаФе8!ея)

6308

97880

Муравьиные алгоритмы

(Апг Зуягещ)

578 1150 2598

6232

18122850

92490

Муравьиные алгоритмы 578 1150 2570

с локальным поиском

(Ап! Зуя!ещ вчПЬ 1оса1 яеагсЬ)

6!28

17212548

изменяется посредством мутации.

ПРОГРАММИРОВАНИЕ Г! — ' Ч 000Я

цедуры локального поиска 2-орц 3-ор! н Лин-

Кернигхана (Ь!и-Кегп!8Ьап), которые улучшают

маршрут заменой двух, трех и переменного ко-

личества дуг, соответственно.

В последнее время исследуются возмохсности

гибридизации муравьиных алгоритмов с дру-

гимн метаэвристическими методами оптимиза-

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

островная схема и использование генетических операций в муравьиных алгоритмах. Островная схема представляет собой параллельное решение задачи генетическим и муравьиным алгоритмамн с обменом решениями через определенное время. На сегодня предприняты попытки решения задачи коммявояжера и задачи маршрутизации транспорта (УеЫс!е Вопбпй РгоЫет) по островной муравьнно-генетической схеме !19 — 2!), однако делать какие-либо обобщения еще рано. Второе направление муравьнно- генетическоИ гибридизации реализовано лучшим-худшим муравьиным алгоритмом 115, 16), в котором количество феромонов на ребрах графа

Интересным является использование нечетких <если-то> правил при выборе маршрутов виртуальными муравьямн. Такая гибридизация

муравьиных алгоритмов обеспечивает составле-

ние хороших транспортных расписаний при не-

четких исходных данных [22).

4. ОБЗОР ПРИМЕНЕНИЯ МУРАВЬИНЫХ АЛГОРИТМОВ ОПТИМИЗАЦИИ

Приведенный в статье муравьиный алгоритм оптимизации маршрута коммивояжера после незначительных модификациИ может использоваться для решения различных комбинаторных задач: квадратичноИ задачи о назначениях !1япас1гаг!с Аяя!8пгпеп! РгоЫет); задачи маршрутизации транспорта (УеЫс!е Нов!!пй РгоЫеш), задачи календарного планирования (10Ъ-БЬор ЗсЬес1п1е Р!ап1п8), задачи раскраски графа (СгарЬ Со1обп8 РгоЫегп), задачи о кратчайшеИ общей суперпоследовательности !8Ьог!ея1 Сопппоп Бпрегяес!пепсе), многомерной задачи о рюкзаке !Мп11!р1е Кпаряасй) и др. Для решения этих задач муравьиными алгоритмами необходимо: !1) свести их к поиску кратчайшего пути на некотором графе; (2) определить механизмы инициализации и обновления феромонов; (3) назначить эвристические правила выбора маршрута.

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

Распознанный текст из изображения:

МУРАВЬИНЫЕ АЛГОРИТМЫ: ТЕОРИЯ И ПРИМЕНЕНИЕ

Таблица 4. Сравнение метаэвристических методов маршрутизации транспорта [23)

Генетический

алгоритм

(Сепебс А18огИЪгп1

Гранулированный

табу-поиск (Огапи1аг

ТаЪи ЗеагсЪ)

Ранговый муравьиный алгоритм с декомпозицией задачи и локальным поиском (В-Апг)

Число

заказчиков

Время

решения,

мин

С еднее Л чшее В

Найденное

решение

Найденное

решение

Время

решения,

мин

р решение

за 10 прогонов

у рема

решение решения,

мнн

200 255 300 399 420 480

6460. 98 7. 13

586.87 139.27

6460.98 596.89

1018.74 933.74

1846.55

13728.8

1.04

14.32

39.33

78.50

210.42

187.6

6697.53

593.35

1016.83

936.04

1915.83

14910. 62

2.38 11.67 2145 33.12 43.05 15.13

6460. 98 589.28

1007.81 932.58

1836.87

13958.68

32.55 158.93 239.47 240.00

1007.07

927.27

1834.79

13816.98

ПРОГРАММИРОВАНИЕ 1Че 4 зепз

ния и временем оптимизации. В качестве примера сравниваются различные метаэвристические методы оптимизации маршрута коммивояжера (таблица 2) и решения квадратичноИ задачи о назначениях (таблица 3). Числа в ячейках таблиц — значения критерия оптимальности для решений, найденных соответствующими методами. В таблице 4 сравниваются три метода маршрутизации транспорта для задач боль- шоИ размерности. Время оптимизации пересчитано под производительность процессора Реп1- га--900Мн. Полужирным шрифтом выделены наилучшие на сегодня решения.

Муравьиные алгоритмы применимы и для стохастическоИ комбинаторной оптимизации. Теоретическая сходимасть к глобальному оптимуму стохастнческих муравьиных алгоритмов продемонстрирована в [24].

Среди прикладных работ выделим исследования по применению муравьиных алгоритмов;

е в инженерии: многокритериальное проектирование водных ирригационных сетей [25], оптимизация водоснабжения [26), оптимизация структуры съемочных геодезических сетеИ [27), оптимизации надежности с помощью резервирования [28], эргономическое проектирование компьютерных клавиатур «29], размещение данных в памяти суперкомпьютера [30], динамическая оптимизация химических процессов [31);

е в менеджменте: составление университетских расписаний [32), оптимизация размещения автобусных остановок [33], согласование транспортных расписаний [22);

е в биологии: предсказание структуры проте-

ина по его аминокислотным цепочкам [34);

е в искусстве: составление музыкальных

произведениИ [35) и написание картин [361.

Хорошие результаты получены прп использовании муравьиных алгоритмов для обучения Байесовских сетей [37), классических логических правил [38] и нечетких баз знаний [39), а также для экстракцин нечетких правил из экспериментальных данных [40). Корпорация 'о1егпепв на основе муравьиной оптимизации, нечеткой логики и роевоИ кластеризации разработала гибридный метод управления логистикой. Пилотное использование этого метода на мюн-

хенских складах корпорации снизило задержки по доставке товаров на 44% [4!].

Высокую эффективность демонстрируют муравьиные алгоритмы при оптимизации распределенных нестационарных систем. Примером может служить нахождение муравьиными алгоритмами оптимальных трафиков в телекоммуникационных сетях [6, 42), В таблице 5 приведены результаты маршрутизации в американской сети Г45г ь1ВТ, содержашеИ 14 узлов с 21 дву- направленноИ линией связи. Сравнивались следующие алгоритмы: Ап114ег — муравьиныИ алгоритм; ОЪНР— официальный интернетовский алгоритм маршрутизации; ВЙР— алгоритм, использующий динамическую метрику при рас ~ете стоимости соединениИ; Ваешоп — аппроксимация идеального алгоритма маршрутизации;

Распознанный текст из изображения:

ШТОВЕА

Таблица 5. Сравнение алгоритмов маршрутизации для сети (4ЯРЬ!ЕТ (42]

14

(6, 45].

5. ВЫВОДЫ

СПИСОК ЛИТЕРАТУРЫ

ПРОГРАММИРОВАНИЕ !Чв 4 20ОЗ

В! — алгоритм Беллмана-Форда. В таблице 5 приведены средние значения времени задержки и пропускной способности при интенсивной загрузке сети. Числа в скобках — значения среднеквадратических отклонений при 10-кратном прогоне алгоритмов. Информацию о других применениях муравьиных алгоритмов можно найти в обзорных статьях [43, 44] и в книгах

В последнее время биологические науки оказывают значительное влияние на математику и компьютерные технологии — зарождается техно- биология — наука, использующая биологические принципы для совершенствования техники и информационных процессов (8]. К технобиологии можно отнести и муравьиные алгоритмы, которые основаны на механизмах самоорганизации социальных насекомых. Муравьиные алгоритмы предложены в начале девяностых годов и за 10 лет из "игрушечных" демонстрациИ переросли в важное направление в оптимизации.

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

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

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

1. Захаров А.А. Муравей, семья, колония..Мс Наука, 1978.

2. Рокада М. Орбппга!юп, Ьеагп!пй ап6 Ха!ига! А1- йог!1Ьшз. РЬР ТЬввш. Р!Рагг>шел!о 6! Е1емгошса, Ро1йесЬп!со Р! М>1апо. 1!а1у, 1992. 140 р.

3. Рот>до М., Ыап>еххо И, Со1отп> А. ТЬв Апг Еувгет: Оргии>гацоп Ьу з Со!опу о1 Соорегабпя Айепзв // 1ЕЕЕ Тгапз. оп 8увзешз, Мап ап6 СуЬегпевюз. Ра>1 В. 1996. У. 26. Х вЂ” ' 1. Р 29 — 41.

4. Левопова Т.В., Лвреш М.А. Алгоритм муравьиной колонии и имитации отжига для задаче о р-медиане // Автоматика и Телемеханика.

2004. !д — ' 3. С. 80 — 88.

5. Штовба Сый Муравьиные алгоритмы />> Ехропеп1а Рго Математика в приложениях 2003. На 4. С. 70-75.

6. Вопазепт Е., Рот>до М. 8жапп 1пзе!Ьйепсе: бот Г>агпга! 1о Агз>йс!а! 8увгетв. Ох1ог6 11шзегшву Ргеш, 1999 307 р.

Распознанный текст из изображения:

МУРАВЬИНЫЕ АЛГОРИТМЫ: ТЕОРИЯ И ПРИМЕНЕНИЕ

15

19.

20.

22.

23.

7. ОаХда М. Бгчагт 1пбейгйепсе, Апб А)йопбйтя апб Апб Со!опу Орсшизайоп // Кеаг)ег 1ог СЕ!) Яипипег Пшчегвйу Соигяе "Сотр1ех Яувсет". Виг)аревь, Сепгга! Еигореап Пп)чегягу. 2001. Р. 1 — 38.

8. Шведова Н. Эволюционная биология и высокие технологии: симбиоз будущего. СХеччв.ги.

ЬССр.//вггччг.спечгв ги/печгсот/)пбех.вЬСт)72002/ 09/27/136108.

9 Сагм Я., Атал Б., Оелеибоигд 1.1, Раягеей 1.М. Яе)1-Огйап!яег) ЯЬогбсибв га СЬе Агйепйпе Апг // Хагигчггяяепвбайеп. 1989. Х вЂ” ' 76. Р. 579 — 581.

10. ТЯ!'ЫВ. ЬССр://нггчггч )нгг.ип)-Ье)бе)Ьегй.г)е/ 8гоиря/соторС/войгчаге/ТБРЫВ95/.

11. Сел М., Сбелд Н. СепеНс А)йопСЬтв апс1 Епй)- пееппй Веяйп. ЗоЬп СУ!)еу бс Яопв, 1997. 352 р.

12. Вайлбегтес В., Нагй Н.Р., Я)гааза С. А Хегч

Вапй-Вязей Уегв)оп о1 СЬе Ап) ЯувСепг: А Сотригабопа1 ЯСибу // Сепвга! Еигореап доигпа! Гог Орегайопв Кеяеагсб апг) Есопоппсв. 1999. Ч. 7.

Хв 1 Р. 25 — 38

13. Юаггда М., Сатбагдейа И.М. Апг Со)опу Бувбет:

А Соорегайче 1.еагшпй АрргоасЬ Со СЬе Тгаче!шй Яа1еяпап РгоЪ)ет /,1 1ЕЕЕ Тгапя, оп Ечо1ибюпагу Сотригайоп. 1997. У. 1. Хе 1. Р. 53 — 66.

!4 5)ига)е Т., Ноаз Н.Н. МАХ-М1Х Апг Буябет // Рисиге Сеиегасюп Сопгрисег Яувсетв. 2000. У !6. Хк 8. Р. 889-9!4.

15. Сал)ол О., Реглалаез г)е Угала 1., Могело 1. А

Хегч АСС Мос1е1 1пгейгайпй Ечо1ийопагу Соисергя ТЬе Вез!-СУогзС Апг Яуягегп. Ргос. о1 АХТБ2000 — Ргопг Ап) Со1опгея Со Агйбсга1 Ап)в: А Белея о!1пбег. СУог)гвборв оп Апг А)йопСЬтя.

Вгияяе)в, Ве)8)ит 2000. Р. 22-29.

!6. Оал)ал О., Реглалг)ез г)е )Ггала 1., Неггега Р.

Апа)увы о1 СЬе Вевг-ЪУогвС Апг Яуягетя апс) 1Св Чапан!в оп СЬе ч)АР. Ргос. о1 СЬе ТЬггс) 1пСегпабопа! СЧог)сяЬор оп Апг А!ЯогйЬтв "АХТЯ 2002' // бес!иге Хо!ее гп Сотрибег Ясгепсе 2463.

Ярппйег-Чег)ай, 2002. Р. 228 — 234.

17. Нетей С ТЬе Тгаче)гпй Яа)еягпап: Согприбагюпа! Яо)и!юля 1ог ТЯР Арр)гсагюпя // Пес!иге Хеген т Сотригег Ясгепсе. У. 840. Вег1ш: Ярпп81егЧег1ай, 1994.

18. Саябалуе))а 1..М., Роггдо М. Яо1щпй Бупипебпс

апг) Аяугпгпегпс ТЯРв Ьу Апб Со)ошев. Ргос, о1 СЬе 1ЕЕЕ Соп)егепсе оп Ечо1ибюпагу Согпригайоп "!СЕС'96". !)БА, Рысаганау. 1996.

Р. 622-627.

ПРОГРАММИРОВАНИЕ Х вЂ” ' 4 2005

Кегталл М., ЗМачба Я., Асеротисело Е А НубгЫ Апб Со)опу Орбгппяайоп апг) Сепейс А)йопСЬт АрргоасЬ 1ог ЧеЫс1е йоиС!ий РгоЫепы Яойпп8 // Бсийепс Рарегв о1 Сопгр1ех Яуясетв Яипгтег ЯсЬоо1-2001. Нипйагу, Вис)врез!. Р. 134 — 141.

Рг1аг М., Игбгге Т. )/з)пй Сепесгс А18огйЬпг Со ОрСипые АСЯ-ТЯР. Ргос. о1 СЬе ТЫгб 1лсегпайопа! СУог)сзЬор оп Апг А)8опСЬтя "АХТЯ 2002" // Ьесгиге Хогез )п Сопгригег Ясгепсе 2463. Ярг!ийегЧег)ай, 2002. Р 282-287.

Асан А. СААСО: А СА -)- АСС НуЬггб )ог Разбег апс) Веббег БеагсЬ Сарабг1гбу. Ргос, о) СЬе ТЫгб 1пгегпайопа) СЧог)габор оп Ап) А!йопСЬгпя "АХТБ 2002" // 1ессиге Хо!ее ш Сопгригег Ясгепсе 2463. Ярггпйег-Уег)а8, 2002, Р. 300 — 301,

1,исш Р. Мос)е)шй Тгапяроггабоп РгоЫегпя Езт8 Сопсер)в оГБгчагт 1п)ейгйепсе апг) Яой Согпри)- !пй. РЬО ТЬеяв. С!ч)1 Епбрпееппй Перагбтепг. Уггйбпга Ро!угесЬпю 1пзбйиге апб ЯСаге Пп)четв)- Су. У)г8)п)а, !1БА. 2002. 141 р.

Вегталл М. Ап) Вавег) Орянпгайоп гп Соос1

Тгапярог)абюп. РЬГг ТЬевы. Пп!чегвгсу о1 Чгегг-

па. Угеппа, Аивгг!а. 2002. 149 р.

Сапабс )ч71. А Сопчегй)пй АСС А18опСЬпг 1ог БСосЬвз)гс СопгЬгпа)опа1 Оргипыабюп. Ргос. о1 БАРА-2003 — БгосЬазггс А18опСЬпы: Роипба)сопя апг) Арр!гсагюпя // бес!иге Хо!ее ш Согпригег Бсгепсе 2827. Ярппйег-Чег)аеч, 2003. Р. 10-25.

25. Маггало С.Е., Мага1ез Е. МОАС2: Ап Апг-С! А1

йопСЬт 1ог Миййр1е ОЪ3есгг хе Орйпизайов РгоЬ1етв. Ргос. о1 Сепейс апс1 Ечо)ийопагу Сопгригагюп Сопсегепсе )СЕССО-99). ПЯА, ЯапРгапс!все. 1999 У. !. Р. 894 — 901.

26. Магег Н.Н., гйтрзал А.Н, Яессбгл А.С

)даг Киал Раолд, Киалд Уеаы Рбалд, Нял !еаы Яеаб, СИал Иггл Тал. Апг Со1олу ОрттпгаСюп Гог Веяйп о1 СУагег Оийггбийоп Яузгепгз // долгие! оГСУабег Кезоигсев Р)апп)пй апб Мапайелгепс. Ч. 129. 1ззие 3 Р. 200 — 209.

27. Низяал Аях Яа)еИ. Поведение муравьев моиз

но успешно использовать длз разработки съе-

мочных сетей СРЯ оптимальной структуры

Русский перевод на ЬССрг//чг з и.айр.ги/рго) есгз/

апбя/.

28. Игалд Уил-СМа, Ятггб А.Е. Ап Ап) Бувбет Ар

ргоасЬ Со Нег)ипс)апсу Айосапоп. Ргос. о) СЬе Сопбгеяз оп Ечо1иПопагу Сотригайоп )СЕС *99) 1999. Ч. 2.

29. Еддегз 1., Рег))ес З., ТбеИ) Б., гч)садлег М.О., галлаи В Оргипыаеюп оЕ СЬе КеуЪоагб АггапйепгепС РгоЫет ившй ап Апб Со)опу А)йог!СЬт //

Распознанный текст из изображения:

16

ШТОВВА

37.

38.

39.

40

43

Еигореап )оигпа! оЬ Орегасюпа! ВезеагсЬ. 2003.

На 148. Р. 672-686.

30 Ват1гтдиев А. Арр!ссавюп оГАпс Со1опу ОрйпигаСюп Со Паса ВБвсяЪиНоп сп Мешогу !и Сошрыег Яуясегпя. АЬвсгасся о1 7СЬ Аппиа! Бвапп НевеагсЬегя Меес!08 "БвагшРеяс 2003". ЫЯА, Хосте Паше. 2003. Ри11 рарег ас Ыср:// ввв.цсс.еби/ агоссгс86/.

31. Ва/евй д., Сирга К,, Аивитайат Н.5., чауататал ИН., Ни1Ьагиг В.ГС. Оупапнс ОрНгпгваНоп о1 СЬеписа! Ргосеяяез Нв!08 Апс Со!опу Ргашевог!с // Сошрисегв апс! СЬепиясгу. 2001. Ч. 25.

1яяие 6. Р. 583 — 595.

32. 5осЬа Н., Ниошсея ч'., 5тр!ев М. А МАХ-М!Х

Апс Бузсегп Гог СЬе \!гичегйсу Соигяе ТгтпесаЫш8 РгоЫепг. Ргос, оГ СЬе ТЫС6 1псегпаНопа1 чЧог14- яЬор оп Апс А18опсЬгпя "А14ТБ 2002" // Ьессиге !4осев Сп Сошрцсег Бссепсе 2463. БрПп8ег-Чег!а8, 2002. Р 1-13.

33. Юе /апд ч'. Ми1сгр!е Апв Со1опу Бузвешв 1ог СЬе

Виысор А11осаяоп РгоЫегп. Мввсег ТЬевии Перагсшепс о1 РЫ1о!о8у. Ншчегясу о1 НсгесЬС.

ЫсгесЬС, Но!!аитЬ 2001. 59 р.

34. 55туде1зса А., Нооя Н. Ап 1гпргочей Апс Со!опу

ОрНпьНаНоп А18огйЬтп Гог СЬе 2О НР Ргосеш Ро!61п8 РгоЫепс. Ргос. о1 СЬе БС!хСеепСЬ Саиа61- ап Соп1егепсе оп Агссбсга! !псе!!18епсе (АГ2003).

Сапас!а. 2003.

35. Сиегес С., МоптагсЛе Ат., 5йтапе М. Апся Сап

Р!ау Мияс. Ргос. оГ РоигсЬ 1псегпасгопа! СЧог14- яЬор оп АпС Со1опу ОрСишкаНоп ап6 Бвагш !псе!118епсе (АНТЯ 2004) // Ьессцге ХоСев сп Согприсег Бсгепсе 3172. Брггп8ег-Чег1а8, 2004.

Р. 310-3!7.

36. Аиресгг 5., Воггсеаи И, МаататсЬе Аг., 5йтале М., СгепСитспт С. 1ЫегасНче Ечо1иНоп о1 Апс Рагпяп8я Ргос о! 1ЕЕЕ Соп8гевя оп Ечо-

!исюпагу Сошрисасгоп. СашЬегга: 1ЕЕЕ Ргезв,

2003. Р. 1376-1383.

Юе Сатраз Ь.М., Сагаев ХА., Риет1а ХМ. Ьеагп-

1п8 Вауеяап 14егвогйз Ьу Апс Со!опу ОрНпцяа-

Сюп; ЯеагсЬгп8 сп Тво О!СГегепС Ярасея // МасЬ-

ваге Й Яой СошриНп8. 2002. ЫЯ 9

Наврспе1Й а.М., Ьорев Н.5., РгеНав А.А. Паса Мспсп8 вйЬ ап Апс Со!опу ОрВпцгавюп А18огйЬгп //!ЕЕЕ Тгапя. оп Ечо1иНопагу СопгриСасюп. Бресгас гыце оп Апс Со1опу А18огйЬшя.

2002. Ч. 6. Хп 4. Р. 321-332.

Савяс11ав а., Сопйоп О., Неттега Р. Ьеагпсп8 Ригку Рл1ез Ьзш8 Апс Со!опу ОрНпикаНоп А18огйЬшв. Ргос. о1 АХТЯ2000 — Ргош Апс Со!ошев Со Агро йсга1 Апсв: А Яепез о1 1псег. гЧогЬзЬорз оп Апг А18оПСЬшз. Вгизяе1я, Ве!81цш. 2000. Р. 13-21

Савяйав ч'., Сои!оп О., Региапгсез гсе Сггаиа 1, Нетгега Р. Ьеагп!п8 Гоорега6че Ып8швСю Рексу Ни!ее Ыяи8 СЬе Везк-Чдогзг Апс Буксет А!8оНСЬш // 1псегпаНопа1 Лоцгпа! о1 !псе!1!Бепс Буксете.

2005. Ч. 20. Р. 433-452.

41. Сошропепс Тгапврогс Ро1!овв СЬе Апс Тгас1.

ЬССр://ввв.ягегпепя.согп. ЯерсепгЬег 23, 2004.

Сага С.17., Гсоггдо М. Апес: а МоЬ11е А8епся АрргоасЬ Со АС1арНче ВоиНп8. ТесЬшса1 Нерогс 1ШОА 97-12. 1Н1ОА — Ншчегяйе ЫЬге 6е Вгияве1ез. Вгивве!я, Ве181цш. !997. 27 р.

Юотгдо М., 51истсе Т. ТЬе Апс Со1опу ОрсипяаНоп МеваЬецг!яссе: А18огйЬпи, Арр!гсаНопя, ап6 Абчапсев / С1очег Р., КосЬепЪег8ег О. (ебв.) Нап<СЪооСС о!МегаЬеигсвс!ся НогвеП, МА: К1ивег Асайепис РиЫ!вЬегв, 2002.

Сои1оп О., Нетгета Р., 5сисз1е Т. А ВечАев оп СЬе Апс Со1опу ОрНпикасгоп МеСаЬеипвССс Вази, Массе!я ап6 Хев Тгепбз // МасЬваге 3С Бой Сошрийп8. 2002. ЫЯ 9.

Х)оггдо М., 51игз1е Т. Апс Со!опу ОрНпикасюп

ВгаЖог6 Воосс, 2004.

ПРОГРАММИРОВАНИЕ С!Я 4 2006

Распознанный текст из изображения:

НГГОВВА

бытием в признании перспективности исследований по муравьиной оптимизации можно считать решение Европейской комиссии о присуждении в 2003 г. Мапе Сппе Ехсе!1епсе Ашагс1 [Премии Фонда Марии Кюри за выдающиеся научные достижения) в размере 50000 евро доктору Марко Дориго, изобретателю муравьиных алгоритмов. Несмотря на стремительные успехи муравьиных алгоритмов, большинство русскоязычных специалистов по математическому программированию не знакомо с этим научным направлением. Первая статья по мура- вьиноИ оптимизации в международном журнале опубликована российскими учеными только в 2004 г. [4].

Предлагаемая вниманию читателя статья состоит из четырех разделов: в первом разделе излагаются принципы самоорганизации социальных насекомых н объясняется, как муравьи находят кратчайший маршрут, во втором — на примере задачи коммивояжера показывается, как внедрить кооперативное поведение муравьев в алгоритмы комбинаторной оптимизации, в третьем - анализируются методы улучшения муравьиных алгоритмов, в четвертом — дается обзор применения муравьиных алгоритмов. При написании первого и второго разделов использовались источники [5 — 7].

1. ПРИНЦИПЫ ПОВЕДЕНИЯ МУРАВЬЕВ

Муравьи относятся к социальным насекомым, живущим внутри некоторого коллектива — семьи илн колонии. Около двух процентов насекомых являются социальными, половину из них составляют муравьи. Число муравьев в одном социуме колеблется от 30 штук до десятков миллионов. Муравьи занимают доминирующее положение в бассейне Амазонки, в лесах которого на них приходится более 30% биомассы фауны. Поведение муравьев при транспортировании пищи, преодолении препятствиИ, строительстве муравейника и других действиях зачастую приближается к теоретически оптимальному. Принципы поведения муравьев выдержали испытания на протяжении 100 миллионов лет — именно столько времени назад муравьи 'колонизировали" Землю. Живучесть му-

равьиных колониИ удивительная — удаление до 40% насекомых практически не сказывается на функционировании всего социума [8]. При массовой гибели муравьев, например, после химической обработки территории, насекомые из соседних муравейников объединяются в одну семью для сохранения социума [1].

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

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

е многократности повторения;

е случайности;

е положительной обратной связи;

е отрицательноИ обратной связи.

Муравьи используют два способа передачи информации: прямой — обмен пищей, мандибу- лярныИ, визуальный и химический контакты, и непрямой — стигмержи [з11рпегйу]. Спгигмерлси — это разнесенный во времени тип взаимодействия, когда один субъект взаимодействия изменяет некоторую часть окружающей среды, а остальные используют эту информацию позже, когда находятся в ее окрестности. Биологически, стигмержи осуществляется через феромоны [рйегошопе] — специальный секрет, откладываемый как след при перемещении муравья. Чем выше концентрация феромонов на тропе, тем больше муравьев будет по ней двигаться. Со временем феромоны испаряются, что позволяет муравьям адаптировать поведение под изменения внешнеИ среды. Распределение феромонов является своего рода динамически изменяемоИ глобальной памятью муравейника. Любой му- равеИ в фиксированныИ момент времени может воспринять и изменить лишь одну локальную ячейку этой глобальной памяти.

ПРОГРАММИРОВАНИЕ Нь 4 2000

Распознанный текст из изображения:

МУРАВЬИНЫЕ АЛГОРИТМЫ: ТЕОРИЯ И ПРИМЕНЕНИЕ

2) это 14Р-сложная задача;

На примере экспериментов с асимметричным мостом разберем, как кооперативное поведение муравьев позволяет найти кратчайший маршрут к источнику пищи. Асимметричный мост (рис. Ц соединяет гнездо муравьев с источником пищи двумя ветками разной длины. Эксперименты Я проводились с лабораторноИ колониеИ аргентинских муравьев (1гМотугтех Ъит111в), которые откладывают феромоны по дороге, как от гнезда, так и к гнезду. Эксперименты проводилнсь по следующеИ схеме:

Ц строился мост А-В-С-?);

2) открывались ворота в точке А;

3) фиксировалось количество муравьев, выбравших длинную (А-С-П) и короткую (А-В-П) ветки моста.

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

2. МУРАВЬИНЫЙ ПОДХОД

К ЗАДАс1Е КОММИВОЯЖЕРА

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

ПРОГРАММИРОВАНИЕ На 4 2005

Рис. 1. Асимметричный мост (по материалам [9)).

3) это традиционный тестовый полигон (Ъепсйтагк ргоЫегп) для методов комбинаторной оптимизации. Существует обширная библиотека тестовых задач коммивояжера и методов их решения, что позволяет сравнить эффективность муравьиных алгоритмов оптимизации с другими подходами;

4) это дидактпческая задача, для которой

можно без злоупотребления технпческими деталями алгоритма объяснить процесс поиска оптимума;

5) это первая комбинаторная задача, решенная муравьиными алгоритмами.

Рассмотрим, как реализовать четыре составляющие самоорганизации муравьев при оптимизации маршрута коммивояжера.

Многвиратность взаимодействия ре лизуется итерационным поиском маршрута 'коммивояжера несколькими муравьями одновременно. КаждыИ муравеИ рассматривается как отдельный, независимый коммивояжер, решающий свою задачу. За одну итерацию алгоритма муравей совершает полный маршрут коммивояжера.

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

Распознанный текст из изображения:

ШТОВБА

[г, [1)) [т~б)Д

[тп [») )" [Оп)

ге 'н

если ~' Б,У;»,

О,

если 1' ~ д;»,

Р;,»[1) =

нительных муравьев. Для задачи коммивояжера положительная обратная связь реализуется следующим стохастическим правилом: вероятность включения ребра графа в маршрут муравья пропорциональна количеству феромонов на нем. Такое вероятностное правило реализует н другую составляющую самоорганизации — случайность. Чем короче путь "источник пищи — муравейник", тем чаще биологический муравей может пройти его за фиксированный промежуток времени, откладывая при каждом проходе некоторое количество феромонов. Для имитации такого поведения муравьев объем виртуальных феромонов, откладываемых на ребре графа, принимают обратно пропорциональным длине маршрута. с1ем короче маршрут, тем больше феромонов будет отложено на соответствующих ребрах графа, н тем чаще муравьи будут использовать нх при синтезе новых маршрутов.

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

Для каждого муравья переход из города г в город у зависит от трех составляющих: табу- списка [»абп 11з»), видимости и следа виртуальных феромонов.

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

Видимость — это величина, обратная расстоянию: и, = !~Пи, где Т1, — расстояние между городами» н 1. Видимость — это локальная ста-

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

След виртуальных феромоное на ребре [г — у) представляет подтвержденное опытом колонии желание посетить город у из города г. В отличие от видимости, распределение феромонов меняется после каждой итерации алгоритма, отражая приобретенный муравьями опыт. Количество виртуальных феромонов на ребре [г — 1) на итерации 1 обозначим через т, [1).

Вероятность перехода й-го муравья из города 1 в город 1 на»-ой итерации рассчитывается следующим вероятностно-пропорциональным пра. нилом;

где о > О н»1 > Π— два регулируемых параметра, задающие важность следа феромонов н видимости при выборе маршрута. При а = О выбирается ближайший город, что соответствует жадному алгоритму в классической теории оптимизации. Если В = О, то работает лишь феромонное усиление, что приводит к быстрому вырождению маршрутов к одному субоптимальному решению. Для обеспечения хорошей динамики оптимизации в [3] рекомендуется установить В > о.

Обратим внимание, что правило [1) определяет вероятности выбора того или иного города. Собственно выбор города осуществляется по принципу "колеса рулетки" — каждый город на ней имеет свой сектор с площадью, пропорциональной вероятности [1). Для выбора города нужно бросить шарик на рулетку — сгенерировать случайное число и определить сектор, на котором он остановится.

После завершения маршрута й-ый муравей откладывает на ребре [г, Я такое количество феромонов:

если [г,у') Е Т»[1),

с»гб,»[Г) = ь» [Г)

О, если [г,)) ф Т»[»),

ПРОГРАММИРОБА~ИЕ н — ' 4 2005

Распознанный текст из изображения:

МУРАВЬИНЫЕ АЛГОРИТМЫ: ТЕОРИЯ И ПРИМЕНЕНИЕ

'/Базовый муравьиный алгоритм решения задачи коннивояжера:

<Ввод матрицы расстояний О>

<Инициализация параметров алгоритма а, )3, О, р, т0>

ш=п '/Количество нуравьев равно числу городов

Рог 1=1;и '/Пля кажцого ребра

Рог )=1:и

11 1-=)

п(1,))=1/О(1,)) видимость

т(1,))= т0 '/Феронон

Е1зе т(1,))=0

Елб

Епе(

Епб

Рог К=1:ш

<Разместить муравья К в случайно выбранный город>

ЕШ$

<Выбрать условно-кратчайший маршрут Те и рассчитать его длину ь+>

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

Рог с=1 тимах Хтшах — количество итераций алгоритма

Рог К=1:ш /Пля каждого муравья:

<Построить маршрут ТК(т) по правилу (1)>

<Рассчитать ЬК(З) — длину иаршрута ТК(т)>

Епб

11 "Лучшее решение найдено?" <Обновить Т+ и ь+> Елб

Рог 1=1:и

Рог )=1:и '/Пля каждого ребра

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

Епб

Епб

Епб

<Вывести кратчайший иаршрут Т+ и его длину ь~>

Рис. 2. Базовый муравьиный алгоритм оптимизации маршрута коммивояжера.

где

ПРОГРАММИРОВАНИЕ На 4 2005

7'е(/) — маршрут муравья К на итерации И

Ее (Г) — длина маршрута Ть (Г);

(/ > 0 — регулируемыИ параметр.

Для исследования всего пространства решений необходимо обеспечить испарение феромонов. Обозначим коэффициент испарения через р б '(О, 1), тогда правило обновления феромонов примет вид:

и

то(С+ Ц = (1 — р) . т/(1) + ~~ /зт,.ь(1), (2)

в=1

где тл — количество муравьев в колонии. В начале оптимизации количество феромонов на ребрах принимается равным небольшому положительному числу то.

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

Распознанный текст из изображения:

ШТОВБА

'к, 2500

О.

н

Я 2400

й 2200

5

2000

50

100

4ОО

Зба

3 Зпп

й

250

200

50

1оо

б

м

Ф

и 5

Ф

Ф

и

"4

о

50

иемеригирации

25

400

Рис. 3. Исследование процесса решения задачи коммивояжера Вауз29 базовым

муравьиным алгоритмом 1при о = 0.5, ~9 = 0.5, Я = 2000, р = 0.5).

ПРОГРАЫЫИРОВАНИЕ Мв 4 2005

В отличие от биологических муравьев виртуальные агенты помнят список посещенных городов и живут в пространстве с дискретным временем. Кроме того, они не полностью "слепы", так как выбирают маршрут не только по концентрации феромонов, но и используют эвристики ~3~. Эти отличия обусловлены тем, что виртуальные муравьи используются для решения задач оптимизации, а не для моделирования колонии насекомых. На рис. 2 приводится базовый муравьиныИ алгоритм оптимизации маршрута коммивояжера, реализующий рассмотренные принципы самоорганизации.

В наших экспериментах на тестовоИ задаче с 29 населенными пунктами в Баварии Вауз29 ~101 базовый муравьиный алгоритм после 100 итераций нашел оптимальный маршрут длиной 2020 в двух экспериментах из 10. Для гарантированного нахождения оптимума число итераций алгоритма необходимо увеличить до 1 — 2 тысяч. При выполнении алгоритма популяция решений

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

По сравнению с точными методами, например, динамическим программированием или методом ветвей и границ, муравьиный алгорптм

Распознанный текст из изображения:

МУРАВЬИНЫЕ АЛГОРИТМЫ: ТЕОРИЯ И ПРИМЕНЕНИЕ

2150

Ъ

в

и

2050

2020

0

40 50 итерация аигаритиа

Во

100

Рис. 4. Сравнение динамик алгоритмов с разным числом элитных муравьев для задачи Вауа29

3. МЕТОДЫ УЛУЧШЕНИЯ БАЗОВОГО МУРАВЬИНОГО АЛГОРИТМА

ПРОГРАММИРОВАНИЕ Н вЂ” ' 4 2005

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

Базовый муравьиный алгоритм [Апь Вуз1еш) решает задачи коммивояжера неболыпой размерности [с числом городов до 75) с точностью па уровне других неспециализированных эвристических методов, таких, как генетические алгоритмы [СепеВс А!йоп111шв) и имитированный отжиг [31шп1аве3 Аппеа!103) [3]. Для задач большой размерности простейший муравьиный алгоритм — не конкурент современным специализированным методам оптимизации маршрута коммивояжера. Недостаточная эффективность базового муравьиного алгоритма связава с:

1) воэможностью потери наилучшего найденного решения через вероятностное правило выбора маршрута;

2) низкой сходимостью вблизи оптимума через приблизительно равный вклад как лу"1- ших, так и худших решениИ в обновление феромонов;

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

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

Распознанный текст из изображения:

ШТОВБА

3.1. Элитные муравьи

где

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

В окрестности оптимума длины маршрутов муравьев отличаются незначительно, поэтому, в соответствии с (2), вклад как лучших, так и худших решений в обновление феромонов будет почти одинаковым. Это обуславливает медленное приближение к оптимуму в его окрестности. Первое улучшение муравьиных алгоритмов состояло в усилении наилучшего решения через элитных муравьев [3]. Элитные муравьи откладывают феромоны только на ребрах наилучшего маршрута Т+, найденного с начала работы алгоритма.

Для задачи коммивояжера количество феромонов, откладываемое элитным муравьем на каждом ребре маршрута Т+, принимается равным Я>>1,+, где Л+ — длина маршрута Т+. Идея элитизма состоит в том, что увеличенное количество феромонов будет притягивать больше муравьев, подталкивая их к исследованию ре- шениИ, содержащих несколько ребер наилучшего на данныИ момент маршрута Т+. Если в муравейнике есть е элитных муравьев, то ребра маршрута Т ь получат дополнительное усиление:

с>т,>, = е Я/Г,", >>'(1,у') б Т . (3)

На рис. 4 приведены усредненные за!О прогонов динамики решения задачи Вауя29 алгоритмами с различным числом элитных муравьев. При болыпом числе элитных муравьев алгоритмы очень быстро, за 30-40 итераций, находят субоптимальные маршруты длиноИ 2033, 2028, 2026. Однако после этого надолго застревают в локальных оптимумах, так как элитные муравьи сильно их усиливают. В проведенных нами 10 экспериментах за 100 итерациИ алгоритмы с тремя и с пятью элитными муравьями нашли оптимальный маршрут по 3 раза, с десятью элитными муравьями — б раз, а с тридцатью— только дважды.

Идеи элитизма развиваются в ранговых муравьиных алгоритмах (Капй-Ваяег! Апс Яуягешя) [12], алгоритмах муравьиноИ колонии (Апь Со!опу Яуя1ешя) [13], макс-минных муравьиных алгоритмах (МАХ-М!Р! Апь Яуягешя) [14] и лучших-худших муравьиных алгоритмах (Вези %огяг Апг Буя1етя) [15]. Эти алгоритмы оптимизируют быстрее за счет увеличения вероят- ностеИ выбора хороших фрагментов маршрутов.

3.2. Ранговый муравъиныи алгоритвм

В ранговых муравьиных алгоритмах найденные на каждой итерации решения ранжируют, и только (ю — Ц лучших муравьев и один элитныИ муравей откладывают феромоны. Таким образом, плохие маршруты не запоминаются. Количество феромонов зависит от ранга муравья.

Для задачи коммивояжера правило обновления феромонов (2) принимает вид:

т3(Г Ф Ц = (1 р) ' тг>'К+

+ ~ (ю — т) Ьт» „(!)+

г=и...,и — >

+и> Ьт,й.(Г),

Я>'АЬ, если (1,Я б Т~, О, если (>,Я й Т"

П А

— феромоны элитного муравья;

Я/Е" (!), если (!,у) б Т"!'!, О, если (1, >) к Т'(т)

— феромоны муравья с рангом т;

Т" (Г) — маршрут муравья с рангом т на ите-

рации 1;

Л" (!) — длина маршрута Т" (!).

Правило (4) в терминах базового муравьиного алгоритма интерпретируется так: ю муравьев двигаются наилучшим маршрутом Т~, (ю — Ц муравьев двигаются лучшим текущим маршрутом Т' (Г), (и — 2) муравьев двигаются вторым по рангу маршрутом Т~(!) и т.д. Количество феромонов, откладываемых на ребрах двух маршрутов с почти одннаковоИ длиноИ, отличается су-

100

щественно, как минимум на %. Поэтому, в

ю 1

ПРОГРАММИРОВАНИЕ Н вЂ” ' 4 2005

Распознанный текст из изображения:

МУРАВЬИНЫЕ АЛГОРИТМЫ: ТЕОРИЯ И ПРИМЕНЕНИЕ

Таблица 1. Решения задач коммивояжера различными муравьиными алгоритма-

ми (14)

11!98

Е!!51 Кгоа100

Задача

Ну48р

Р$70 Кго124р

Ргч170

Оптимум

426 21282

15780

14422

38673 36230

2755

ММАБ+р1з

ММАВ

14523 4 14553 2

427Л 21291.6 427.6 21320.3

15956.8 15972 5

39040.2 36773.5

2828.8

36857

2826.5

АС8

428. 1 21420

16054

14565.4

39099

21746

39410.1 36973.5

2854.2

16199.1

14511.4

434.5

АВН+ргз

428.8 21394.9 428.3 21522.8

16025. 2

14644.6 14685.2

39199.2 37218

39261.8 37510.2

2915.6

АВЕ

16205

2952.4

АБЕ+р1в 427.4 21431.9

16140.8

14657.9

39161 37417.7

2908.!

АВ 437.3 22471.4

16702. 1

15296.4

39596.3 38733.1

3154.5

г = агй тах((тб(Г))" . (т~, ) ).

ПРОГРАММИРОВАНИЕ гг — ' 4 200з

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

3.3..4лгоритм муравьинод колонии

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

Для задачи коммивояжера правило обновления феромонов (2) принимает вид;

то(1+ 1) = (1 — р) т„(!) + р Ггт„,,(г), (5)

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

Правило выбора продолжения маршрута (1) изменено так: Й-ый муравеИ с вероятностью до переходит нз города г в наиболее привлекатель- ныИ город з 6,7,Ы а с вероятностью (1 — ао) выбирает город у по правилу (1). Чем больше до, тем сильнее эксплуатируется опыт муравьиноИ колонии при синтезе новых маршрутов. Наиболее привлекательный город определяется так;

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

в алгоритмы муравьиноИ колонии введено следующее правило локального обновления феромонов. На каждоИ итерации алгоритма муравей при переходе из города ! в город г асъедает" некоторое количество феромонов с ребра (! — Я. Это ребро теряет привлекательность для других муравьев, которые на этой итерации будут исследовать другие маршруты нз городов г н ~. Решения становятся разнообразнее, так как на протяжении каждой итерации распределение феромонов динамически обновляется, отражая выполненные муравьями перемещения.

3.4. Макс-минный гнуравьиныд алгоритм

Макс-минныИ алгоритм отличается от базового муравьиного алгоритма следующими тремя правилами:

1) на каждоИ итерации феромоны добавляются только на ребра наилучшего маршрута по правилу (5);

2) количество феромонов на ребре графа ограничено диапазоном (т ьо т

3) в начале работы алгоритма количество феромонов на каждом ребре графа принимается равным тт„,

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

Файл скачан с сайта StudIzba.com

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