Федеральное агентство по образованию

Государственное образовательное  учреждение

высшего профессионального  образования 

Факультет физико-математический

Кафедра математического моделирования 
 
 

Курсовая работа

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

            при решении задач оптимизации 
 
 
 
 
 
 
 

2009г.

 

Содержание         Введение..................................................................................................................3

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

     1. Биологические принципы поведения муравьиной колонии.................5

     2. Истории создания муравьиных алгоритмов...........................................7

     3. Концепция муравьиных алгоритмов.................................. …………....9

     4. Обобщённый алгоритм............................................... ...........................11

     5. Этапы решения задачи при помощи муравьиных алгоритмов...........13

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

     6.1. Достоинства:.........................................................................................14

     6.2. Недостатки:...........................................................................................14

Глава 2. Применение муравьиных алгоритмов при решении  задач оптимизации.

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

     коммивояжёра..............................................................................................16

     1.2. Муравьиный алгоритм для задачи коммивояжёра в псевдокоде..............................................................................................................25

     2.1.  Задача оптимального распределения файлов      в    компьютерной сети……………………………………………………………………….…...28

     2.2  Муравьиный алгоритм для задачи  распределения файлов 

     в компьютерной сети  в псевдокоде…………………………..…………29

Заключение………………...................................................................................32

Список  использованной литературы...................................................................33

Приложение……………………………………………………………………....35 
 

 

         Введение

 

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

     Среди так называемых “Soft computing techniques”, разработанных  за последние десять лет для трудно решаемых задач дискретной оптимизации, числятся

     • Генетические алгоритмы  - основываются на естественном отборе и генетике.

     • Муравьиные алгоритмы (Ant Colony Optimization – ACO, Ant Systems – AS) –моделируют поведение муравейника.

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

          Задачи работы.

• Изучить теоретические основы  муравьиных алгоритмов.
• Описать решение муравьиными алгоритмами задач оптимизации.
• Проанализировать применения муравьиных алгоритмов.

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

 

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

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

Содержание работы.

     Дипломная работа состоит из введения, двух глав, заключения,

списка литературы и приложений.

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

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

     В приложении приведены листинги программ реализации задач оптимизации на языке программирования Delphi. 

 

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

     1. Биологические принципы поведения муравьиной колонии.

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

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

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

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

         Непрямой обмен – стигмержи (stigmergy), представляет собой разнесённое во времени взаимодействие, при котором одна особь изменяет

некоторую область окружающей среды, а другие используют эту информацию позже, когда в неё попадают. Биологи установили, что такое отложенное взаимодействие происходит через специальное химическое вещество – феромон (pheromone), секрет специальных желёз, откладываемый при перемещении муравья. Концентрация феромона на пути определяет предпочтительность движения по нему. [2]

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

окружающем  колонию пространстве, и «глобальной» памятью муравейника, носящей динамический характер.  

 

     

     2.История создания муравьиных алгоритмов

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

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

        Имитация самоорганизации муравьиной  колонии составляет основу муравьиных  алгоритмов оптимизации. Колония муравьев может рассматриваться как многоагентная система, в которой каждый агент (муравей) функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, поведение всей системы получается на удивление разумным. [14]

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

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

 

     

     3. Концепция муравьиных алгоритмов

        Идея муравьиного алгоритма – моделирование поведения муравьёв, связанного с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям,

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

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

                                          

        Очевидная положительная обратная связь быстро приведёт к тому, что кратчайший путь станет единственным маршрутом движения большинства муравьёв. Моделирование испарения феромона – отрицательной обратной связи – гарантирует нам, что найденное локально оптимальное решение не будет единственным – муравьи будут искать и другие пути. Если мы моделируем процесс такого поведения на некотором графе, рёбра которого представляют собой возможные пути перемещения муравьёв, в течение определённого времени, то наиболее обогащённый феромоном путь по рёбрам этого графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма. [15]