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

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образованияВ последние годы интенсивно разрабатывается научное направление с названием «Природные вычисления» (Natural Computing), объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений. Среди так называемых “Soft computing techniques”, разработанных за последние десять лет для трудно решаемых задач дискретной оптимизации, числятся • Муравьиные алгоритмы (Ant Colony Optimization - ACO, Ant Systems - AS)-моделируют поведение муравейника. В ходе выполнения дипломной работы был создан программный продукт реализации муравьиного алгоритма, который можно успешно применять в различных областях для решения сложных задач оптимизации. В работе излагаются результаты исследования возможности применения одного из таких алгоритмов - алгоритм моделирования поведения муравьиных колоний для решения задач оптимизации.Муравьи относятся к социальным насекомым, образующим коллективы. Коллективная система способна решать сложные динамические задачи по выполнению совместной работы, которая не могла бы выполняться каждым элементом системы в отдельности в разнообразных средах без внешнего управления, контроля или координации. Основу поведения муравьиной колонии составляет самоорганизация, обеспечивающая достижения общих целей колонии на основе низкоуровневого взаимодействия. Колония не имеет централизованного управления, и ее особенностями являются обмен локальной информацией только между отдельными особями (прямой обмен - пища, визуальные и химические контакты) и наличие непрямого обмена, который и используется в муравьиных алгоритмах.Эксперименты с Argentine ants, проводимые Госсом в 1989 и Денеборгом в 1990 году послужили отправной точкой для дальнейшего исследования роевого интеллекта. Исследования применения полученных знаний для дискретной математики начались в начале 90-х годов XX века, автором идеи является Марко Дориго из Университета Брюсселя, Бельгия. Позже при участии Гамбарделлы, Тайлларда и Ди Каро были разработаны и многие другие подходы к решению сложных оптимизационных задач при помощью муравьиных алгоритмов. На сегодняшний день эти методы являются весьма конкурентоспособными по сравнению с другими эвристиками и для некоторых задач дают наилучшие на сегодняшний день результаты. Муравьиные алгоритмы представляют собой вероятностную жадную эвристику, где вероятности устанавливаются, исходя из информации о качестве решения, полученной из предыдущих решений.Идея муравьиного алгоритма - моделирование поведения муравьев, связанного с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. При своем движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути. Рассмотрим случай, показанный на рисунке, когда на оптимальном доселе пути возникает преграда. Поскольку движение муравьев определяется концентрацией феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном до тех пор, пока этот путь по какой-либо причине не станет недоступен.Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде. Создаем муравьев Ищем решения Обновляем феромон Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи.Для того чтобы построить подходящий муравьиный алгоритм для решения какой-либо задачи, нужно Представить задачу в виде набора компонент и переходов или набором неориентированных взвешенных графов, на которых муравьи могут строить решения. Определить значение следа феромона. Определить эвристику поведения муравья, когда строим решение .· Для небольшого количества узлов TSP может быть решена полным перебором · Сравнение с GAS (Genetic Algorithms): · Опираются на память обо всей колонии вместо памяти только о предыдущем поколении· Теоретический анализ затруднен: 1. Распределение вероятностей меняется при итерацияхЗадача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с n вершинами. Муравьи обладают «зрением» - видимость есть эвристическое желание посетить город j, если муравей находится в городе i. Муравьи обладают «обонянием» - они могут улавливать след феромона, подтверждающий желание посетить город j из города i на основании опыта других муравьев. На этом основании мы можем сформулировать вероятностно-пропорциональное правило, определяющее вероятность перехода k-ого муравья из города i в город j: (1) Пусть Tk (t) есть маршрут, пройденный муравьем k к моменту времени t, Lk(t) - длина этого маршрута, а Q - параметр, имеющий значение порядка длины оптимального пути.

Содержание муравьиный алгоритм моделирование программирование

Введение

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

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

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

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

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

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

6.1 Достоинства

6.2 Недостатки

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

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

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

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

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

Заключение

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

Приложение