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

V Гомельская научно-практическая конференция школьников по математике, ее приложениям и информационным технологиям "Поиск"

Учебно-исследовательская работа

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

Ученицы

Сердюковой Марины Михайловны,

Кучинской Татьяны Сергеевны

Научный руководитель -

Горский Сергей Михайлович, учитель математики Государственного учреждения образования «Гимназия №14 г. Гомеля»

Гомель, 2009

Оглавление

• Введение
• Принципы поведения муравьев
• Муравьиный подход к задаче коммивояжера
• Муравьиная оптимизация маршрута коммивояжера
• Заключение
• Литература
• Введение
• Муравьиные алгоритмы серьезно исследуются европейскими учеными с середины 90-х годов. На сегодня уже получены хорошие результаты муравьиной оптимизации таких сложных комбинаторных задач, как: задачи коммивояжера, задачи оптимизации маршрутов грузовиков, задачи раскраски графа, квадратичной задачи о назначениях, оптимизации сетевых графиков, задачи календарного планирования и других. Особенно эффективны муравьиные алгоритмы при on-line оптимизации процессов в распределенных нестационарных системах, например трафиков в телекоммуникационных сетях.
• В последние два десятилетия при оптимизации сложных систем исследователи все чаще применяют природные механизмы поиска наилучших решений. Это механизмы обеспечивают эффективную адаптацию флоры и фауны к окружающей среде на протяжении миллионов лет. Сегодня интенсивно разрабатывается научное направление Natural Computing - «Природные вычисления», объединяющее методы с природными механизмами принятия решений, а именно:
• Genetic Algorithms - генетические алгоритмы;
• Evolution Programming - эволюционное программирование;
• Neural Network Computing - нейро-сетевые вычисления;
• DNA Computing - ДНК-вычисления;
• Cellular Automata - клеточные автоматы;
• Ant Colony Algorithms - муравьиные алгоритмы.
• Целью настоящего исследования является изложение теоретических основ и примеров практического применения муравьиных алгоритмов - нового перспективного метода оптимизации, базирующегося на моделировании поведения колонии муравьев. Колония муравьев может рассматриваться как многоагентная система, в которой каждый агент (муравей) функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, поведение всей системы получается на удивление разумным.
• Принципы поведения муравьев
• Принципы поведения муравьев выдержали испытания далеко не в лабораторных условиях на протяжении 100 миллионов лет - именно столько времени назад муравьи «колонизировали» Землю. Муравьи относятся к социальным насекомым, живущим внутри некоторого коллектива-колонии. На Земле около двух процентов насекомых являются социальными, половину из них составляют муравьи - небольшие существа массой от 1 до 5 мг.
• Рис. 1. Сеть гнезд суперколонии муравьев Formica lugubris в Швейцарии [9].
• Число муравьев в одной колонии колеблется от 30 штук до нескольких миллионов. На Земле около 10¹⁶ муравьев с общей массой, приблизительно равной массе человечества. Поведение муравьев при транспортировании пищи, преодолении препятствий, строительстве муравейника и других действиях зачастую приближается к теоретически оптимальному. В качестве примера на рис. 1 приведена структура взаимосвязанных гнезд суперколонии муравьев Formica lugubris в Швейцарии. Сеть муравейников близка к минимальному остовному дереву, соединяющему все гнезда колонии - вершины графа на рис. 1.
• Какие же механизмы обеспечивают столь сложное поведение муравьев, и что можем мы позаимствовать у этих крошечных существ для решения своих глобальных задач? Основу «социального» поведения муравьев составляет самоорганизация - множество динамических механизмов, обеспечивающих достижение системой глобальной цели в результате низкоуровневого взаимодействия ее элементов. Принципиальной особенностью такого взаимодействия является использование элементами системы только локальной информации. При этом исключается любое централизованное управление и обращение к глобальному образу, репрезентирующему систему во внешнем мире. Самоорганизация является результатом взаимодействия следующих четырех компонентов:
• случайность;
• многократность;
• положительная обратная связь;
• отрицательная обратная связь.
• Муравьи используют два способа передачи информации: прямой - обмен пищей, мандибулярный, визуальный и химический контакты, и непрямой - стигмержи (stigmergy). Стигмержи - это разнесенный во времени тип взаимодействия, когда один субъект взаимодействия изменяет некоторую часть окружающей среды, а остальные используют информацию об ее состоянии позже, когда находятся в ее окрестности. Биологически стигмержи осуществляется через феромон (pheromone) - специальный секрет, откладываемый как след при перемещении муравья. Феромон - достаточно стойкое вещество, он может восприниматься муравьями несколько суток. Чем выше концентрация феромона на тропе, тем больше муравьев будет по ней двигаться. Со временем феромон испаряется, что позволяет муравьям адаптировать свое поведение под изменения внешней среды. Распределение феромона по пространству передвижения муравьев является своего рода динамически изменяемой глобальной памятью муравейника. Любой муравей в фиксированный момент времени может воспринимать и изменять лишь одну локальную ячейку этой глобальной памяти.
• Муравьиные алгоритмы основаны на имитации природных механизмов самоорганизации муравьев, использование которых иллюстрируется в следующих разделах на примере оптимизации маршрута коммивояжера.
• Муравьиный подход к задаче коммивояжера
• Задача коммивояжера состоит в поиске кратчайшего замкнутого маршрута, проходящего через все города ровно один раз. Выбор задачи коммивояжера для иллюстрации идей муравьиных алгоритмов обусловлен следующим.
• 1. Задача наглядно интерпретируется в терминах поведения муравьев - перемещения коммивояжера и муравьев интуитивно сопоставимы.
• 2. Это NP-сложная задача, которая на недетерминированной машине Тьюринга решается за полиномиальное время.
• 3. Это традиционный тестовый полигон (benchmark problem) для методов комбинаторной оптимизации. Существует обширная база тестовых задач о коммивояжере и методов их решения, что позволяет сравнить эффективность муравьиных алгоритмов оптимизации с другими подходами.
• 4. Это дидактическая задача, для которой можно легко, без злоупотребления техническими подробностями алгоритма объяснить процесс нахождения оптимального решения.
• 5. Это первая комбинаторная задача, решенная муравьиными алгоритмами.
• Рассмотрим, как реализовать четыре составляющие самоорганизации муравьев при оптимизации маршрута коммивояжера. Многократность взаимодействия реализуется итерационным поиском маршрута коммивояжера одновременно несколькими муравьями. При этом каждый муравей рассматривается как отдельный, независимый коммивояжер, решающий свою задачу. За одну итерацию алгоритма каждый муравей совершает полный маршрут коммивояжера.
• Положительная обратная связь реализуется как имитация поведения муравьев типа «оставление следов-перемещение по следам». Чем больше следов оставлено на тропе - ребре графа в задаче коммивояжера, тем больше муравьев будет передвигаться по ней. При этом на тропе появляются новые следы, привлекающие дополнительных муравьев. Для задачи коммивояжера положительная обратная связь реализуется следующим стохастическим правилом: вероятность включения ребра графа в маршрут муравья пропорциональна количеству феромона на нем.
• Применение такого вероятностного правила обеспечивает реализацию и другой составляющей самоорганизации - случайности. Количество откладываемого муравьем феромона на ребре графа обратно пропорционально длине маршрута. Чем короче маршрут, тем больше феромона будет отложено на соответствующих ребрах графа и тем больше муравьев будет использовать их при синтезе своих маршрутов. Отложенный на ребрах феромен выступает как усилитель, он позволяет хорошим маршрутам сохраняться в глобальной памяти муравейника. Эти маршруты могут быть улучшены на последующих итерациях алгоритма.
• Использование только положительной обратной связи приводит к преждевременной сходимости решений - к случаю, когда все муравьи двигаются одним и тем же субоптимальным маршрутом. Для избегания этого используется отрицательная обратная связь - испарение феромона. Время испарения не должно быть слишком большим, так как при этом возникает опасность сходимости популяции маршрутов к одному субоптимальному решению. С другой стороны, время испарения не должно быть и слишком малым, так как это приводит к быстрому «забыванию», потере памяти колонии и, следовательно, к некооперативному поведению муравьев. В поведении муравьев кооперативность является очень важной: множество идентичных муравьев одновременно исследуют разные точки пространства решений и передают свой опыт через изменения ячеек глобальной памяти муравейника.
• Для каждого муравья переход из города i в город j зависит от трех составляющих: памяти муравья (tabu list), видимости и виртуального следа феромона.
• Tabu list (память муравья) - это список посещенных муравьем городов, заходить в которые еще раз нельзя. Используя этот список, муравей гарантированно не попадет в один и тот же город дважды. Ясно, что tabu list возрастает при совершении маршрута и обнуляется в начале каждой итерации алгоритма. Обозначим через J_{t k} список городов, которые еще необходимо посетить муравью k, находящемуся в городе i. Понятно, что J_{t k} является дополнением к tabu list.
• Видимость - величина, обратная расстоянию:
• x\j = 1/ D j,
• где D j - расстояние между городами и j.
• Видимость - это локальная статическая информация, выражающая эвристическое желание посетить город j из города - чем ближе город, тем больше желание посетить его. Использование только видимости, конечно, является недостаточным для нахождения оптимального маршрута.
• Виртуальный след феромона на ребре (i, j) представляет подтвержденное муравьиным опытом желание посетить город j из города. В отличие от видимости след феромона является более глобальной и динамичной информацией - она изменяется после каждой итерации алгоритма, отражая приобретенный муравьями опыт. Количество виртуального феромона на ребре (i, j) на итерации t обозначим через Z j (t).
• Важную роль в муравьиных алгоритмах играет вероятностно-пропорциональное правило, определяющее вероятность перехода k -го муравья из города в город j на t -й итерации:
• где a и в - два регулируемых параметра, задающие веса следа феромона и видимости при выборе маршрута.
• При a = 0 будет выбран ближайший город, что соответствует жадному алгоритму в классической теории оптимизации. Если в = 0, тогда работает лишь феромонное усиление, что влечет за собой быстрое вырождение маршрутов к одному субоптимальному решению.
• Обратим внимание, что правило (1) определяет лишь вероятности выбора того или иного города. Собственно выбор города осуществляется по принципу «колеса рулетки»: каждый город на ней имеет свой сектор с площадью, пропорциональной вероятности (1). Для выбора города нужно бросить шарик на рулетку - сгенерировать случайное число, и определить сектор, на котором этот шарик остановится.
• Заметим, что хотя правило (1) не изменяется на протяжении итерации, значения вероятностей P _j,k (t) для двух муравьев в одном и том же городе могут отличаться, т. к. P _j,k (t) - функция от Ji _k - списка еще не посещенных городов муравьем k.
• После завершения маршрута каждый муравей k откладывает на ребре (i j) такое количество феромона:

• где T_k (t) - маршрут, пройденный муравьем k на итерации t;
• L_k (t) - длина этого маршрута;
• Q - регулируемый параметр, значение которого выбирают одного порядка с длиной оптимального маршрута.
• Для исследования всего пространства решений необходимо обеспечить испарение феромона - уменьшение во времени количества отложенного на предыдущих итерациях феромона. Обозначим коэффициент испарения феромона через p из [0, 1]. Тогда правило обновления феромона примет вид:
• где, m - количество муравьев в колонии.
• В начале оптимизации количество феромона принимается равным небольшому положительному числу Z₀. Общее количество муравьев в колонии остается постоянным на протяжении выполнения алгоритма. Многочисленная колония приводит к быстрому усилению субоптимальных маршрутов, а когда муравьев мало, возникает опасность потери кооперативности поведения через ограниченное взаимодействие и быстрое испарения феромона. Обычно число муравьев назначают равным количеству городов - каждый муравей начинает маршрут со своего города.
• Для улучшения временных характеристик муравьиного алгоритма вводят так называемых элитных муравьев. Элитный муравей усиливает ребра наилучшего маршрута, найденного с начала работы алгоритма. Количество феромона, откладываемого на ребрах наилучшего текущего маршрута T⁺, принимается равным QJL+ , где LL - длина маршрута T+. Этот феромон побуждает муравьев к исследованию решений, содержащих несколько ребер наилучшего на данный момент маршрута T +. Если в муравейнике есть e элитных муравьев, то ребра маршрута T + будут получать общее усиление
• Муравьиная оптимизация маршрута коммивояжера
• Ниже приводится муравьиный алгоритм оптимизации маршрута коммивояжера, реализующий все идеи предыдущего раздела (в угловых скобках содержится словесное описание соответствующего кода).
• <Ввод матрицы расстояний D>
• <Инициализация параметров алгоритма a (alpha), в (beta), e, Q, Т₀ (tau0)>
• m=n % Количество муравьев равно числу городов For i=1:n
• For j=1:n % Для каждого ребра If i~=j
• eta(i,j)=1/D(i,j); % Видимость
• tau(i,j)= tauO; % Феромон
• Else tau(i,j)=0; % Переход из одного города в тот же самый % невозможен
• End
• End
• End
• For k=1:m
• <Разместить муравья k в случайно выбранный город>
• End
• <Выбрать условно-кратчайший маршрут Т+ и рассчитать его длину L⁺> % Основной цикл For t=1:tmax
• % tmax - количество итераций алгоритма For k=1:m % Для каждого муравья
• <Построить маршрут Тк^) по правилу (1) и рассчитать длину Lk(t)> End
• If < "Лучшее решение найдено?" >
• <Обновить Т+ и L+ >
• End
• For i=1:n
• For j=1:n % Для каждого ребра
• <Обновить следы феромона по правилам (2) и (3).> End End End
• <Вывести кратчайший маршрут Т+ и его длину L+>
• Муравьиный алгоритм был запрограммирован в системе MATLAB и протестирован на серии задач из библиотеки [5]. Для задачи с 29 населенными пунктами в Баварии «Bays-29» алгоритм без элитных муравьев после 100 итераций нашел оптимальный маршрут длиной 2020 только в одном случае из пяти. Решение можно улучшить простым увеличением количества итераций до 1-2 тысяч. Длины маршрутов муравьев на одной итерации отличаются незначительно, поэтому для ускорения нахождения оптимума необходимо искусственно усиливать наилучшие текущие решения с помощью элитных муравьев. На рис. 2 показаны усредненные динамики решения задачи «Bays-29» алгоритмами с различным числом элитных муравьев.

• Рис. 2
• Эксперименты для каждого алгоритма повторялись 5 раз. На первый взгляд кажется, что чем больше элитных муравьев, тем лучше работает алгоритм. Действительно, алгоритмы с большим количеством элитных муравьев очень быстро, за 30-40 итераций находят субоптимальные маршруты длиной 2033, 2028, 2026, однако после этого надолго застревают в локальных оптимумах, т. к. элитные муравьи очень сильно усиливают эти субоптимальные решения. В пяти экспериментах за 100 итераций алгоритм с тремя элитными муравьями трижды нашел оптимальный маршрут, с десятью элитными муравьями - дважды, а с двадцатью - только один раз. Несмотря на то, что алгоритм с тремя элитными муравьями медленнее приближается к хорошим маршрутам, он намного быстрее проходит субоптимальные решения-ловушки.
• Проведенные нами эксперименты свидетельствуют, что популяция решений никогда не вырождается к одному, общему для всех муравьев маршруту. Наоборот, алгоритм продолжает синтезировать новые, возможно лучшие решения. На рис. 3, а синей линией показаны наилучшие решения, найденные на каждой итерации алгоритма с тремя элитными муравьями. Красной линией показаны наилучшие решения, найденные с начала работы алгоритма. Как видно, линии не совпадают, следовательно, муравьиный алгоритм генерирует новые решения на каждой итерации. Об этом свидетельствует и рис. 3, б, на котором показано среднеквадратическое отклонение длин маршрутов, найденных муравьями на текущей итерации алгоритма.
• Даже если оптимальный маршрут уже найден, алгоритм продолжает поддерживать разнообразность популяции решений. На рис. 3, в показано среднее по городам число разветвлений следов феромона на текущей итерации алгоритма. Оно получено подсчетом ребер, инцидентных вершине графа, след феромона на которых превышает некоторый порог. Это число колеблется около 4-5 на протяжении всей работы алгоритма, следовательно, в любом городе для муравья существует несколько перспективных альтернатив продолжения маршрута.
• По сравнению с точными методами, например динамическим программированием или методом ветвей и границ, муравьиный алгоритм находит близкие к оптимуму решения за значительно меньшее время даже для задач небольшой размерности (n > 20). Время оптимизации муравьиным алгоритмом является полиномиальной функцией от размерности O(t, -n², -m), тогда как для точных методов зависимость экспоненциальная.
• Рис. 3. Исследование процесса решения задачи коммивояжера муравьиным алгоритмом.
• Заключение
• Муравьиные алгоритмы основаны на имитации самоорганизации социальных насекомых посредством использования динамических механизмов, с помощью которых система достигает глобальной цели в результате локального низкоуровневого взаимодействия элементов. В статье на примере задачи коммивояжера показано, как в алгоритмы решения дискретных задач оптимизации внедрить составляющие самоорганизации муравьев: случайность, многократность взаимодействия, отрицательную и положительную обратные связи. Проведенные компьютерные эксперименты показывают, что муравьиные алгоритмы находят хорошие маршруты коммивояжера значительно быстрее, чем точные методы комбинаторной оптимизации. Эффективность муравьиных алгоритмов увеличивается с ростом размерности задачи оптимизации.
• Муравьиные алгоритмы обеспечивают решения и других комбинаторных задач не хуже общих метаэвристические технологий оптимизации и некоторых проблемно-ориентированных методов. Особенно хорошие результаты муравьиной оптимизации получаются для нестационарных систем, параметры которых изменяются во времени, например телекоммуникационных и компьютерных сетей.
• Важным свойством муравьиных алгоритмов является неконвергентность: даже после большого числа итераций одновременно исследуется множество вариантов решения, вследствие чего не происходит длительных временных задержек в локальных экстремумах. Все это позволяет рекомендовать применение муравьиных алгоритмов для решения сложных комбинаторных задач оптимизации. Перспективными путями улучшения муравьиных алгоритмов являются on-line адаптация параметров с помощью базы нечетких правил, а также их гибридизация с другими методами природных вычислений, например генетическими алгоритмами. Гибридизация может осуществляться по островной схеме, когда различные алгоритмы решают задачу параллельно и автономно (каждый на отдельном «острове») с обменом наилучшими решениями через определенное время, или по принципу «мастер-подмастерье», когда основной алгоритм - «мастер» передает решение типовых подзадач «подмастерью» - специализированному, быстрому алгоритму.
• Литература
• Bonavear E., Dorigo M. Swarm Intelligence: from Natural to Artificial Systems.- Oxford University Press, 1999.- 307 p.
• Corne D., Dorigo M., Glover F. New Ideas in Optimization.- McGrav-Hill, 1999.
• Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization// Reader for CEU Summer University Course «Complex System».- Budapest, Central European University, 2001.- P. 1-38.
• http://irida.ulb.ac.de/ACO/ACO.html.
• http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.

Reimann M. Ant Based Optimization in Good Transportation. PhD Thesis. University of Vienna.- Vienna, Austria, 2002.- 149 p.

Caro G. D., Dorigo M. Anet: a Mobile Agents Approach to Adaptive Routing. Technical Report IRIDA 97-12. IRIDA - Universite Libre de Brusseles.- Brussels, Belgium, 1997.- 27 p.

http://www.swarm.org.

Cherix D. Note preliminaire sur la structure, la phenologie et le regime alimentaire d'une super-colonie de Formica lugubris Zett. // Insects Sociaux 27, 1980.- P. 226-236