Теоретические основы и примеры практического применения муравьиных алгоритмов

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

Введение

В последние два десятилетия при оптимизации сложных систем исследователи все чаще применяют природные механизмы поиска наилучших решений. Это механизмы обеспечивают эффективную адаптацию флоры и фауны к окружающей среде на протяжении миллионов лет. Сегодня интенсивно разрабатывается научное направление Natural Computing -- «Природные вычисления», объединяющее методы с природными механизмами принятия решений, а именно:

· Genetic Algorithms -- генетические алгоритмы;

· Evolution Programming -- эволюционное программирование;

· Neural Network Computing -- нейро-сетевые вычисления;

· DNA Computing -- ДНК-вычисления;

· Cellular Automata -- клеточные автоматы;

· Ant Colony Algorithms -- муравьиные алгоритмы.

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

1. Анализ предметной области

1.1 История возникновения метода

Началось всё с изучения поведения реальных муравьёв. Эксперименты с Argentine ants, проводимые Госсом в 1989 и Денеборгом в 1990 году послужили отправной точкой для дальнейшего исследования роевого интеллекта. Исследования применения полученных знаний для дискретной математики начались в начале 90-х годов XX века, автором идеи является Марко Дориго из Университета Брюсселя, Бельгия. Именно он впервые сумел формализовать поведение муравьёв и применить стратегию их поведения для решения задачи о кратчайших путях. Позже при участии Гамбарделлы, Тайлларда и Ди Каро были разработаны и многие другие подходы к решению сложных оптимизационных задач с помощью муравьиных алгоритмов. На сегодняшний день эти методы являются весьма конкурентоспособными по сравнению с другими эвристиками и для некоторых задач дают наилучшие на сегодняшний день результаты.

1.2 Принципы поведения муравьиной колонии

Принципы поведения муравьев выдержали испытания далеко не в лабораторных условиях на протяжении 100 миллионов лет -- именно столько времени назад муравьи «колонизировали» Землю. Муравьи относятся к социальным насекомым, живущим внутри некоторого коллектива -- колонии. На Земле около двух процентов насекомых являются социальными, половину из них составляют муравьи -- небольшие существа массой от 1 до 5 мг. Число муравьев в одной колонии колеблется от 30 штук до нескольких миллионов. На Земле около 1016 муравьев с общей массой, приблизительно равной массе человечества. Поведение муравьев при транспортировании пищи, преодолении препятствий, строительстве муравейника и других действиях зачастую приближается к теоретически оптимальному. В качестве примера на рисунке 1 приведена структура взаимосвязанных гнезд суперколонии муравьев Formica lugubris в Швейцарии. Сеть муравейников близка к минимальному остовному дереву, соединяющему все гнезда колонии - вершины графа на рисунке 1.

Рисунок 1 - сеть гнезд суперколонии муравьев Formica lugubris в Швейцарии

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

· случайность;

· многократность;

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

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

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

2. Математическая модель алгоритма

2.1 Обобщенный алгоритм

Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде

* Пока (условия выхода не выполнены)

1. Создаем муравьев

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

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

2. Ищем решения

Вероятность перехода из вершины i в вершину j определяется по следующей формуле

Где фij(t) - уровень феромона, dij - эвристическое расстояние, а б, в - константные параметры.

При б = 0 выбор ближайшего города наиболее вероятен, то есть алгоритм становится жадным.

При в = 0 выбор происходит только на основании феромона, что приводит к субоптимальным решениям.

Поэтому необходим компромисс между этими величинами, который находится экспериментально.

3. Обновляем феромон

Уровень феромона обновляется в соответствии с приведённой формулой

Где с - интенсивность испарения, Lk(t) - цена текущего решения для k-ого муравья, а Q - параметр, имеющий значение порядка цены оптимального решения, то есть - феромон, откладываемый k-ым муравьём, использующим ребро (i,j).

4. Дополнительные действия {опционально}

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

2.2 Применение муравьиных алгоритмов для задачи коммивояжера

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

1. Задача наглядно интерпретируется в терминах поведения муравьев -- перемещения коммивояжера и муравьев интуитивно сопоставимы.

2. Это NP-сложная задача, которая на недетерминированной машине Тьюринга решается за полиномиальное время.

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

4. Это дидактическая задача, для которой можно легко, без злоупотребления техническими подробностями алгоритма объяснить процесс нахождения оптимального решения.

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

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

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

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

колонии и, следовательно, к некооперативному поведению муравьев. В поведении муравьев кооперативность является очень важной: множество идентичных муравьев одновременно исследуют разные точки пространства решений и передают свой опыт через изменения ячеек глобальной памяти муравейника. Для каждого муравья переход из города i в город j зависит от трех составляющих: памяти муравья (tabu list), видимости и виртуального следа феромона.

Tabu list (память муравья) -- это список посещенных муравьем городов, заходить в которые еще раз нельзя. Используя этот список, муравей гарантированно не попадет в один и тот же город дважды. Ясно, что tabu list возрастает при совершении маршрута и обнуляется в начале каждой итерации алгоритма. Обозначим через Ji,k список городов, которые еще необходимо посетить муравью k, находящемуся в городе i. Понятно, что Ji,k является дополнением к tabu list.

·Видимость -- величина, обратная расстоянию: зi,j = 1/Di,j где Di,j -- расстояние между городами i и j. Видимость -- это локальная статическая информация, выражающая эвристическое желание посетить город j из города i -- чем ближе город, тем больше желание посетить его. Использование только видимости, конечно, является недостаточным для нахождения оптимального маршрута.

Виртуальный след феромона на ребре (i, j) представляет подтвержденное муравьиным опытом желание посетить город j из города i. В отличие от видимости след феромона является более глобальной и динамичной информацией -- она изменяется после каждой итерации алгоритма, отражая приобретенный муравьями опыт. Количество виртуального феромона на ребре (i, j) на итерации t обозначим через фij(t).

Важную роль в муравьиных алгоритмах играет вероятностно-пропорциональное правило, определяющее вероятность перехода k-го муравья из города i в город j на t-й итерации:

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

Обратим внимание, что это правило определяет лишь вероятности выбора того или иного города. Собственно выбор города осуществляется по принципу «колеса рулетки»: каждый город на ней имеет свой сектор с площадью, пропорциональной вероятности Pij,k(t). Для выбора города нужно бросить шарик на рулетку -- сгенерировать случайное число, и определить сектор, на котором этот шарик остановится. Заметим, что хотя правило не изменяется на протяжении итерации, значения вероятностей, Pij,k(t) для двух муравьев в одном и том же городе могут отличаться, т. к. Pij,k(t) -- функция от Ji,k -- списка еще не посещенных городов муравьем k.

После завершения маршрута каждый муравей k откладывает на ребре (i, j) такое количество феромона:

где Tk(t) -- маршрут, пройденный муравьем k на итерации t; Lk(t) -- длина этого маршрута; Q -- регулируемый параметр, значение которого выбирают одного порядка с длиной оптимального маршрута.

Для исследования всего пространства решений необходимо обеспечить испарение феромона -- уменьшение во времени количества отложенного на предыдущих итерациях феромона. Обозначим коэффициент испарения феромона через p ? [0, 1]. Тогда правило обновления феромона примет вид:

где, , m -- количество муравьев в колонии.

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

Для улучшения временных характеристик муравьиного алгоритма вводят так называемых элитных муравьев. Элитный муравей усиливает ребра наилучшего маршрута, найденного с начала работы алгоритма. Количество феромона, откладываемого на ребрах наилучшего текущего маршрута T+, принимается равным Q/L+, где L+ -- длина маршрута T+. Этот феромон побуждает муравьев к исследованию решений, содержащих несколько ребер наилучшего на данный момент маршрута T+. Если в муравейнике есть e элитных муравьев, то ребра маршрута T+ будут получать общее усиление

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

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

<Инициализация параметров алгоритма б (alpha), в (beta), e, Q, ф0 (tau0)>

m=n % Количество муравьев равно числу городов

For i=1:n

For j=1:n % Для каждого ребра

If i-=j

eta(i,j)=1/D(i,j); % Видимость

tau(i,j)= tau0; % Феромон

Else tau(i,j)=0;

% Переход из одного города в тот же самый

% невозможен

End

End

End

For k=1:m

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

End

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

% Основной цикл

For t=1:tmax

% tmax - количество итераций алгоритма

For k=1:m % Для каждого муравья

<Построить маршрут Тk (t) и рассчитать длину Lk(t)>

End

If < “Лучшее решение найдено?” >

<Обновить Т+ и L+ >

End

For i=1:n

For j=1:n % Для каждого ребра

<Обновить следы феромона>

End

End

End

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

2.3 Области применения и возможные модификации

Для задачи с 29 населенными пунктами в Баварии «Bays-29» алгоритм без элитных муравьев после 100 итераций нашел оптимальный маршрут длиной 2020 только в одном случае из пяти. Решение можно улучшить простым увеличением количества итераций до 1-2 тысяч. Длины маршрутов муравьев на одной итерации отличаются незначительно, поэтому для ускорения нахождения оптимума необходимо искусственно усиливать наилучшие текущие решения с помощью элитных муравьев. На рисунке 2 показаны усредненные динамики решения задачи «Bays-29» алгоритмами с различным числом элитных муравьев.

Рисунок 2 - сравнение эффективности алгоритмов с разным числом элитных муравьев

Эксперименты для каждого алгоритма повторялись 5 раз. На первый взгляд кажется, что чем больше элитных муравьев, тем лучше работает алгоритм. Действительно, алгоритмы с большим количеством элитных муравьев очень быстро, за 30-40 итераций находят субоптимальные маршруты длиной 2033, 2028, 2026, однако после этого надолго застревают в локальных оптимумах, т. к. элитные муравьи очень сильно усиливают эти субоптимальные решения. В пяти экспериментах за 100 итераций алгоритм с тремя элитными муравьями трижды нашел оптимальный маршрут, с десятью элитными муравьями -- дважды, а с двадцатью -- только один раз. Несмотря на то, что алгоритм с тремя элитными муравьями медленнее приближается к хорошим маршрутам, он намного быстрее проходит субоптимальные решения ловушки.

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

Рисунок 3 - исследование процесса решения задачи коммивояжера муравьиным алгоритмом

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

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

Рисунок 4 - эволюция маршрутов коммивояжера

2.4 Достоинства и недостатки муравьиных алгоритмов

* Достоинства:

1. Для TSP (Traveling Salesman Problem) сравнительно эффективны

2. Для небольшого количества узлов TSP может быть решена полным перебором

3. Для большого количества узлов TSP вычислительно сложна (NP-трудная) - экспоненциальное время сходимости

4. Работают лучше, чем другие глобальные оптимизации для TSP (нейронные сети, генетические алгоритмы)

5. Сравнение с GAs (Genetic Algorithms):

- Опираются на память обо всей колонии вместо памяти только о предыдущем поколении

- Меньше подвержены неоптимальным начальным решениям (из-за случайного выбора пути и памяти колонии)

6. Могут использоваться в динамических приложениях (адаптируются к изменениям, скажем, расстояний)

7. Применялись к множеству различных задач

* Недостатки:

Теоретический анализ затруднён:

- В результате последовательности случайных (не независимых) решений

- Распределение вероятностей меняется при итерациях

- Исследование больше экспериментальное, нежели теоретическое

Сходимость гарантируется, но время сходимости не определено

Обычно необходимо применение дополнительных методов таких, как локальный поиск

Сильно зависят от настроечных параметров, которые подбираются только исходя из экспериментов

3. Реализация муравьиного алгоритма

3.1 Код программы, реализующей муравьиный алгоритм

Option Explicit

Public Sub mur()

`объявление переменных--------------------

Dim n, i, j, e, m, k, t As Integer

Dim cpp, kolvo, kol, zzz1, ch, pf, ii, Tplus As Integer

Dim alpha, beta, Q, tau0, Lplus, pp, max As Double

Dim flag As Boolean

Dim stroka As String

Dim tmax As Integer

`------------------------------------------------------

`ввод исходных данных----------------------

n = Worksheets(1).Cells(2, 1).Value`количество городов

alpha = Worksheets(1).Cells(2, 2).Value`б, в - константные параметры

beta = Worksheets(1).Cells(2, 3).Value

e = Worksheets(1).Cells(2, 4).Value

Q = Worksheets(1).Cells(2, 5).Value

tau0 = Worksheets(1).Cells(2, 6).Value`начальный уровень феромона на ребрах

tmax = Worksheets(1).Cells(2, 7).Value`количество итераций

pp = Worksheets(1).Cells(2, 8).Value` коэффициент испарения феромона

m = n`количество муравьев

'------------------------------------------------------

`объявление динамических массивов------

ReDim d(n, n) As Integer`расстояние между городами

ReDim eta(n, n) As Double

ReDim tau(n, n) As Double`кол-во феромона на ребрах

ReDim sum(n) As Double

ReDim P(n, n) As Double`вероятность посещения города

ReDim bllist(n, n) As Integer`список посещенных городов

ReDim marchrut(n, n + 1) As Integer`маршрут (i-муравей, j-город)

ReDim putt(n) As Double`путь маршрута(i-номер маршрута)

`----------------------------------------------------------

For i = 1 To n

Worksheets(1).Cells(6, i + 1).Value = i

Worksheets(1).Cells(6 + i, 1).Value = i

Next i

`ввод исходных данных

For i = 1 To n

d(i, i) = 0

tau(i, i) = 0

For j = 1 To n

If i <> j Then

d(i, j) = InputBox("Расстояние между городом " & i & " и городом " & j)

d(j, i) = d(i, j)

Lplus = Lplus + d(j, i)

Worksheets(1).Cells(6 + i, 1 + j).Value = d(i, j)

Worksheets(1).Cells(6 + j, 1 + i).Value = d(i, j)

eta(i, j) = 1 / d(i, j)

tau(i, j) = tau0

sum(i) = sum(i) + tau(i, j) ^ alpha * eta(i, j) ^ beta

End If

Next j

Next i

For t = 1 To tmax`основной цикл - количество итераций

cpp = cpp + 3

ch = 1

cpp = cpp + 1

For k = 1 To n`цикл перехода от одного муравья к другому

cpp = cpp + 3

pf = 1

cpp = cpp + 1

zzz1 = 1

cpp = cpp + 1

flag = True

cpp = cpp + 1

For i = zzz1 To m`цикл посещения городов от zzz1 до m

cpp = cpp + 3

kol = 1

cpp = cpp + 1

max = 0

cpp = cpp + 1

bllist(k, k) = 1

cpp = cpp + 2

While kol <= n

cpp = cpp + 1

If pf Then

cpp = cpp + 1

ii = k

cpp = cpp + 1

Else

cpp = cpp + 1

ii = i

cpp = cpp + 1

End If

P(ii, kol) = tau(ii, kol) ^ alpha * eta(ii, kol) ^ beta / sum(ii)`формула (3)

cpp = cpp + 8

If max <= P(ii, kol) And bllist(k, kol) <> 1 Then`проверка на условие

cpp = cpp + 4`максимума вероятности

max = P(ii, kol)

cpp = cpp + 2

zzz1 = kol

cpp = cpp + 1

End If

kol = kol + 1

cpp = cpp + 2

Wend

pf = 0

cpp = cpp + 1

bllist(k, zzz1) = 1`отмечаем, k-ому муравью, что город zzz1 был посещен

cpp = cpp + 2

If flag Then

cpp = cpp + 1

marchrut(k, i) = k`заносим первый город в путь k-ого муравья

cpp = cpp + 2

flag = False

cpp = cpp + 1

End If

If flag = False And i <> n Then

cpp = cpp + 2

marchrut(k, i + 1) = zzz1`заносим первый город в путь k-ого муравья

cpp = cpp + 3

Else

cpp = cpp + 1

marchrut(k, n + 1) = k`заносим первый город в путь k-ого муравья

cpp = cpp + 3

End If

ch = ch + 1

cpp = cpp + 2

cpp = cpp + 1

Next i

cpp = cpp + 1

Next k

For i = 1 To n

cpp = cpp + 3

For j = 1 To n

cpp = cpp + 3

Worksheets(2).Cells(i, j).Value = marchrut(i, j)

putt(i) = putt(i) + d(marchrut(i, j), marchrut(i, j + 1))

cpp = cpp + 6

tau(i, j) = (1 - pp) * tau(i, j)

cpp = cpp + 5

cpp = cpp + 1

Next j

Worksheets(2).Cells(i, j).Value = marchrut(i, j)

Worksheets(2).Cells(i, j + 3).Value = putt(i)

If Lplus > putt(i) Then`нахождение кротчайшего пути, из `найденных

cpp = cpp + 2

Tplus = i`отметка на самом коротком пути

cpp = cpp + 1

Lplus = putt(i)`длина самого короткого пути

cpp = cpp + 2

End If

sum(i) = 0

cpp = cpp + 1

Next i

For i = 1 To n

cpp = cpp + 3

For j = 1 To n

cpp = cpp + 3

If i <> j Then

cpp = cpp + 1

tau(i, j) = tau(i, j) + Q / putt(i)`формула (5)

cpp = cpp + 5

sum(i) = sum(i) + tau(i, j) ^ alpha * eta(i, j) ^ beta` формула (3)

cpp = cpp + 8

bllist(i, j) = 0

cpp = cpp + 2

End If

cpp = cpp + 1

Next j

putt(i) = 0

cpp = cpp + 1

cpp = cpp + 1

Next i

cpp = cpp + 1

Next t

`вывод результатов-----------------------------------

Worksheets(1).Cells(4, 12).Value = Lplus

For i = 1 To n + 1

stroka = stroka & marchrut(Tplus, i)

Worksheets(1).Cells(5, 12).Value = stroka

Next i

Worksheets(1).Cells(6, 12).Value = cpp

`--------------------------------------------------------------

End Sub

3.2 Разработка схемы программного модуля

4. Тестирование программы

4.1 Входные данные

Входные данные показаны на рисунке 5.

Рисунок 5 - входные данные

1.2 Выходные данные

Результат выполнения программы показан на рисунках 6, 7.

Рисунок 6 - выходные данные на листе 1

Рисунок 7 - выходные данные на листе 2

5. Экспериментальное исследование трудоемкости алгоритма

муравьиный алгоритм программа

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

В результате выполнения программы для четырех городов и десяти общих итераций экспериментальная трудоемкость программы составила Fэкспер(N) = 18525 (Fтеорит(N)= 58024). Результат отображен на рисунке 6.

6. Теоретическая оценка трудоемкости алгоритма оптимизации

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

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

1) операцию присваиванияab;

2) операцию индексации массиваa[i];

3) арифметические операции *,/,-,+;

4) операции сравнения a < b;

5) логические операции or,and,not.

Отметим, что неявно в операцию сравнения входит машинная команда перехода в конструкции if then else:

F «ветвление» = fthen * p + felse * (1-p).

Цикл не является элементарной операцией, т.к. может быть представлен в виде;

for i1 to N

тело

next i;

Таким образом конструкция цикла требует 2*N элементарных операций:

F «цикл» = 2*N+N*f«тело цикла».

Для цикла while выберем худший случай. Худший случай (Fa(N)) - наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N.

Таким образом, для нашей программы получим:

N - количество переменных в целевой функции;

F=1+3*N+17*((3+1+3*Fa1Fa1*0,5*3*3+1+0,5*4*2+1+4*14)+(3+1+(3+1+3*(0,5*2))++1)+(3+1+(3+1+3*(0,5*3))))

Fal -наибольшее количество операций совершаемый циклом while;

Fa1 =4

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

F(N)= 127+ 42*( 3,5*Fa1 4+4+1+5+1+56+12+11,5);

Исходя из начального значения, максимальное количество операций совершаемый циклом while в главной функции Fa1 =92.

В результате теоретического вычисления трудоемкость данной программы составила F(N)=58024 элементарных операций.

Заключение

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

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

Список использованных источников

1. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях, 2003, №4, с.70-75.

2. МакКоннелл Дж. Основы современных алгоритмов. -- М.: Техносфера, 2004. -- 368 с.

3. Thompson, Jonathan. Ant Colony Optimization.

4. www.orsoc.org.uk/region/regional/swords/swords.ppt

5. Barker T. and Von Haartman M. Ant Colony Optimization.

6. courses.washington.edu/inde510/510/Ant Colony Optimization3.ppt

7. www.cosc.brocku.ca/Offerings/3P71/Lectures/ACO.ppt

8. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization // Reader for CEU Summer

9. University Course «Complex System».-- Budapest, Central

10. Reimann M. Ant Based Optimization in Good

11. http://www.swarm.org.

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

...