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

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

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

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

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

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

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

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

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

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

2009г.

Содержание

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

Введение

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

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

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

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

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

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

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

6.2 Недостатки

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

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

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

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

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

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

Заключение

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

Приложение

 Введение

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

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

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

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

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

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

· Изучить теоретические основы муравьиных алгоритмов.

· Описать решение муравьиными алгоритмами задач оптимизации.

· Проанализировать применения муравьиных алгоритмов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теперь рассмотрим каждый шаг в цикле более подробно

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Определить значение следа феромона.

3. Определить эвристику поведения муравья, когда строим решение .

4. Если возможно, то реализовать эффективный локальный поиск.

5. Выбрать специфический ACO алгоритм и применить для решения задачи.

6. Настроить параметр ACO алгоритма.

Также определяющими являются

* Количество муравьёв

* Баланс между изучением и использованием

* Сочетание с жадными эвристиками или локальным поиском

* Момент, когда обновляется феромон [4]

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

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

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

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

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

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

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

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

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

6.2 Недостатки

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

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

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

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

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

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

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

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

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

Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с n вершинами. Содержательно вершины графа являются

городами, которые должен посетить коммивояжёр, а веса рёбер отражают расстояния (длины) или стоимости проезда. Эта задача является NP-трудной, и точный переборный алгоритм её решения имеет факториальную сложность.

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

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

1. Муравьи имеют собственную «память». Поскольку каждый город может быть посещён только один раз, то у каждого муравья есть список уже посещённых городов - список запретов. Обозначим через J i,k список городов, которые необходимо посетить муравью k, находящемуся в городе i. 2. Муравьи обладают «зрением» - видимость есть эвристическое желание посетить город j, если муравей находится в городе i. Будем считать, что видимость обратно пропорциональна расстоянию между городами

3. Муравьи обладают «обонянием» - они могут улавливать след феромона, подтверждающий желание посетить город j из города i на основании опыта других муравьёв. Количество феромона на ребре (i,j) в момент времени t обозначим через

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

(1)

Где б, в - параметры, задающие веса следа феромона. При б =0 алгоритм вырождается до жадного алгоритма (будет выбран ближайший город). Заметим, что выбор города является вероятностным, правило (1) лишь определяет ширину зоны города j; в общую зону всех городов бросается случайное число, которое и определяет выбор муравья. Правило (1) не изменяется в ходе алгоритма, но у двух разных муравьёв значение вероятности перехода будут отличаться, т.к. они имеют разный список разрешённых городов.

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

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

(2)

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

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

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

(3)

Реализация муравьиного алгоритма на примере задачи коммивояжера.

Постановка задачи. Задан взвешенный граф G1 (рис.1). Найти длину пути муравья в задаче коммивояжера. Начальная вершина 1. Дана последовательность Р = 65,61,35 случайных чисел, выпавших при выборе очередной вершины. Расстояния , между вершинами k,j и интенсивность феромона на ребре [k,j] заданы таблицы

Ребро
1-2 1-3 1-4 1-5 2-3 2-4 2-5 3-4 3-5 4-5	38 74 59 45 46 61 72 49 85 42	3 2 2 2 1 1 1 2 2 1

Решение

Секторы вероятности перехода сортировать по возрастанию номеров вершин . использовать формулу вероятности перехода из вершины k в j.



где б=1, в=1, =1/

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

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

Рис.1. Представим решение в виде:

1. В начале движения из вершины 1 муравей имеет четыре возможных пути: в вершину 2, 3, 4 или 5. Вычислим вероятности перехода в эти вершины

Вычисляем границы четырех секторов , j=2,3,4,5 вероятностей:



Таким образом, отрезок [0,100] разбился на четыре участка

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

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

Остается запустить генератор случайных чисел и узнать , куда попадает случайное число . В нашем случае генератор дает =65, что указывает на третий участок 57,5<65<75,89. Следовательно, муравей должен направиться к вершине 4.

2. Из вершины 4 только три возможные пути: 4-2, 4-3, 4-5. Пройденная вершина 1 попадает в список запрещенных вершин.

Вероятности перехода в эти вершины

Вычисляем границы трех секторов , j=2,3,5 вероятностей:



Таким образом, отрезок [0,100] разбился на три участка

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

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

Случайное число =61, полученное генератором случайных чисел попадает на второй участок. Этот участок указывает на вершину 3. Далее муравей будет выбирать маршрут из этой вершины.

3. При выходе из вершины 3 имеется только 2 возможности - направиться в вершину 2 или 5. Остальные вершины попадают в список запрещенных вершин. Оценим возможности перехода:

Таким образом, отрезок [0,100] разбился на два участка

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

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

Случайное число =35, полученное генератором случайных чисел указывает на вершину 2.

4. В вершине 2 выбор делать не приходиться. Все вершины, кроме 5 попали в список запрещенных вершин, поэтому дальнейший путь муравья очевиден. Сначала он идет в вершину 5, а затем завершает маршрут в 1, там, откуда он и вышел. Общая длина маршрута 1-4-3-2-5-1 равна

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

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

2. Инициализация параметров алгоритма - б,в,e,Q

3. Инициализация рёбер - присвоение видимости и начальной концентрации феромона

4. Размещение муравьёв в случайно выбранные города без совпадений

5. Выбор начального кратчайшего маршрута и определение L*

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

6. Цикл по времени жизни колонии t=1, tmax

7. Цикл по всем муравьям k=1,m

8. Построить маршрут по правилу (1) и рассчитать длину

9. конец цикла по муравьям

10. Проверка всех на лучшее решение по сравнению с L*

11. В случае если решение лучше, обновить L* и T*

12. Цикл по всем рёбрам графа

13. Обновить следы феромона на ребре по правилам (2) и (3)

14. конец цикла по рёбрам

15. конец цикла по времени

16. Вывести кратчайший маршрут T* и его длину L*

Сложность данного алгоритма, как несложно заметить, зависит от времени жизни колонии (tmax), количества городов (n) и количества муравьёв в колонии (m).

Для исследования работы муравьиного алгоритма проведен вычислительный эксперимент. Предложенным алгоритмом решена задача коммивояжера. Количество городов и количество муравьев совпадают. Программа составлена в среде Delphi (Приложение 1).

Зададим начальные значения: количество городов, интенсивность феромона и стоимость маршрута.

После подсчета программа выводит кратчайший путь 1-2-3-4-5, и длину пути равную 220. Интенсивность феромона на путях после прохождения по ним муравьев увеличилась.



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

	Опыт 1	Опыт 2	Опыт 3
Муравьиный алгоритм	1,600мс	1,550мс	1,750мс
Генетический алгоритм	4,300мс	3,100мс	4,700мс

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

В данной главе решается задача уменьшения времени отклика компьютерной сети за счет оптимизации размещения файлов распределенной системы. Для решения задачи предлагается алгоритм, относящийся к классу алгоритмов муравьиной колонии. [16]

Обозначим: - количество запросов к файлу i из узла j в единицу времени; , если файл i расположен в узле j, иначе ; - объем файла i; - объем узла j, i=1...m, j=1…n.

В задаче (1)-(3) необходимо найти матрицу размещений файлов X. В задаче максимизируется суммарный поток локальных запросов. Задача размещения файлов по узлам компьютерной сети имеет вид:

Целевая функция

(1)

Ограничения:

(2) (3)

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

1.Присвоить переменной record первоначальное (небольшое) значение;

2.Присвоить переменной t значение 1;

3. While Do

Begin

For i:=1 to m do

Begin

а). Сформировать вектор P(n) вероятностей размещения i-го файла в j-й узел.

б). Сгенерировать случайную величину g, распределенную по закону P(n);

в). Если и условие (3) выполняется,

то назначить i-й файл в j-й узел,

иначе - сгенерировать новое значение случайной величины g.

End;

г).Вычислить значение целевой функции по формуле (1) и присвоить его

переменной c_f;

д) Если c_f > record,

е) то

Begin

ж) Присвоить переменной record значение переменной c_f и сохранить рекордное решение;

End;

з) Присвоить переменной t значение t+1;

End;

4. Вывести наилучшее решение и завершить алгоритм.

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

(4)

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

.

Для исследования работы муравьиного алгоритма проведен вычислительный эксперимент. Предложенным алгоритмом и методом полного перебора решена задача распределения m файлов среди n узлов сети, m=5, n=3. Объемы файлов - случайные числа. Программа составлена в среде Delphi (Приложение 2).

 Заключение

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

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

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

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

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

3. Столлингс В. Современные компьютерные сети. 2-е изд. - СПб: Питер, 2003. - 783с.

4. Муравьиный алгоритм. Статья Чуракова Михаила, Якушева Андрея, 2006

5. Планирование и оптимизация. Статья Ильи Маляренко Источник: Корпоративные системы PC WEEK/RE №27 25 июля, 2006

6. Кузьменко В.М., Таран С.В. Анализ современных методов искусственного интеллекта . Источник: ВІСНИК Донбаської державної машинобудівної академії № 1Е(6), 2006

7. Thompson, Jonathan. Ant Colony Optimization.

8. Delphi 5.0, учебный курс, Фараонов В.В., ISBN 5-8952-020-4, 400 с.

9. Delphi 4.0, Дарахвелидзе П.Г., Марков Е. П. 1998, 816 с.

10. Модификация муравьиного алгоритма и его применение к задаче коммивояжера. Статья Кажарова А.А.

11. Кирсанов М.Н. Графы в Maple. Задачи, алгоритмы, программы.- М.: Издательство ФИЗМАТЛИТ, 2007

12. Отбор информативных признаков на основе модифицированного метода муравьиных колоний. Статья Субботина С.А., Олейник А.А.

13. Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах. Статья Игнатьева А.Л.

14. Об одном муравьином алгоритме. Статья Курейчик В.М.

15. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы. - Ростов-на-Дону: ООО «Ростиздат», 2004г.

16. Гладков Л.А., Курейчик В.М., Курейчик В.В. Основы теории алгоритмов: Учебное пособие по курсу «Математическая логика и теория алгоритмов». - Таганрог: изд-во ТРТУ, 2002г.

Ресурсы в интернете

17. Сборник научных трудов СевКавГТУ. Серия «Естественнонаучная». 2006. № 2.

18. Marco Dorigo, Vittorio Maniezzo, Alberto Colorni. The Ant System: Optimization by a colony of cooperating agents

19. Marco Dorigo, Luca Maria Gambardella. Ant colonies for the traveling salesman problem

20. Thompson, Jonathan. Ant Colony Optimization.

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

22. www.construction-technology.ru

Приложения

1.Листинг программы решения задачи коммивояжера в среде Delphi.

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ComCtrls, StdCtrls, ExtCtrls, Grids;

type

TForm1 = class(TForm)

UpDown1: TUpDown;

Edit1: TEdit;

Label1: TLabel;

Panel1: TPanel;

GroupBox1: TGroupBox;

GroupBox2: TGroupBox;

StringGrid1: TStringGrid;

StringGrid2: TStringGrid;

Button1: TButton;

Memo1: TMemo;

procedure UpDown1Click(Sender: TObject; Button: TUDBtnType);

procedure FormShow(Sender: TObject);

procedure StringGrid1SetEditText(Sender: TObject; ACol, ARow: Integer;

const Value: String);

procedure StringGrid2SetEditText(Sender: TObject; ACol, ARow: Integer;

const Value: String);

procedure StringGrid1KeyPress(Sender: TObject; var Key: Char);

procedure StringGrid2KeyPress(Sender: TObject; var Key: Char);

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Init( nomer:integer);

procedure muravei(o:integer);

private

{ Private declarations }

public

{ Public declarations }

end;

const

max_count = 100; //максимальное колличество вершин

t_max=100; // время жизни колонии

var

Form1 : TForm1;

count : integer;

tau,p : array[1..max_count, 1..max_count] of double;

// матрица , указывает какие точки еще не прошел муравей

q : array[1..max_count, 1..max_count] of boolean;

// матрица указывает , последовательность прохождения точек

t,l : array[1..max_count, 1..max_count] of integer;

tm,dt : array[1..max_count] of integer;

dtm : integer; //

implementation

{$R *.dfm}

procedure TForm1.UpDown1Click(Sender: TObject; Button: TUDBtnType);

var

i:integer;

begin

//количество вершин

count := form1.UpDown1.Position;

form1.StringGrid1.ColCount := count + 1;

form1.StringGrid1.RowCount := count + 1;

form1.StringGrid2.ColCount := count + 1;

form1.StringGrid2.RowCount := count + 1;

for i:=1 to count do

begin

form1.StringGrid1.Cells[i,0] := IntToStr(i);

form1.StringGrid1.Cells[0,i] := IntToStr(i);

form1.StringGrid1.Cells[i,i]:='****';

form1.StringGrid2.Cells[i,0] := IntToStr(i);

form1.StringGrid2.Cells[0,i] := IntToStr(i);

form1.StringGrid2.Cells[i,i]:='****';

end;

end;

procedure TForm1.FormShow(Sender: TObject);

var

i:integer;

begin

form1.UpDown1.Max := max_count;

form1.UpDown1.min := 2;

count := form1.UpDown1.Position;

form1.Edit1.Text:=IntToStr(count);

form1.StringGrid1.ColCount:=count+1;

form1.StringGrid1.RowCount:=count+1;

form1.StringGrid2.ColCount:=count+1;

form1.StringGrid2.RowCount:=count+1;

for i:=1 to count do

begin

form1.StringGrid1.Cells[i,0] := IntToStr(i);

form1.StringGrid1.Cells[0,i] := IntToStr(i);

form1.StringGrid1.Cells[i,i]:='****';

form1.StringGrid2.Cells[i,0] := IntToStr(i);

form1.StringGrid2.Cells[0,i] := IntToStr(i);

form1.StringGrid2.Cells[i,i]:='****';

end;

end;

procedure TForm1.StringGrid1SetEditText(Sender: TObject; ACol,

ARow: Integer; const Value: String);

begin

if acol=arow then form1.StringGrid1.Cells[acol,arow]:='****' ;

form1.StringGrid1.Cells[arow,acol]:=form1.StringGrid1.Cells[acol,arow];

end;

procedure TForm1.StringGrid2SetEditText(Sender: TObject; ACol,

ARow: Integer; const Value: String);

begin

if acol=arow then form1.StringGrid2.Cells[acol,arow]:='****' ;

form1.StringGrid2.Cells[arow,acol]:=form1.StringGrid2.Cells[acol,arow];

end;

procedure TForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char);

begin

if not (key in [chr(8),'0','1','2','3','4','5','6','7','8','9']) then key:=#0;

end;

procedure TForm1.StringGrid2KeyPress(Sender: TObject; var Key: Char);

begin

if not (key in [chr(8),',','0','1','2','3','4','5','6','7','8','9']) then key:=#0;

end;

procedure TForm1.Init(nomer:integer);

var

i:integer;

begin

// какие точки ему еще осталость пройти

for i:=1 to count do

q[nomer,i]:=true;

q[nomer,nomer]:=false;

//от куда муравей идет

for i:=1 to count do

t[nomer,i]:=0;

t[nomer,1]:=nomer;

end;

procedure TForm1.muravei(o:integer);

var

i,h,k :integer;

z,cheslo :double;

begin

init(o);

for h:=1 to count -1 do

begin

// знаминатель из P

z:=0;

for i:=1 to count do

if q[o,i] then

z := z + tau[o,i]/l[o,i];

// формула Р

for i:=1 to count do

if q[o,i] then

p[o,i] :=100* tau[o,i]/l[o,i] / z;

cheslo:=0;

for i:=1 to count do

if q[o,i] then

begin

cheslo := cheslo + p[o,i];

p[o,i] := cheslo;

end;

z:= random(10000)/100;

k:=0;

for i:=1 to count do

if q[o,i] then

if z< p[o,i] then

begin

k:=i;

break;

end;

// k - то точка куда муравей перемещается

q[o,k]:=false;

i:=1;

while t[o,i]<>0 do

inc(i);

// записываем номер

t[o,i]:=k;

end;

//вычесляем путь

k:= 0;

for i:=1 to count-1 do

k:=k+l[t[o,i],t[o,i+1]];

k:=k+l[t[o,1],t[o,count]];

//запомнили значение

dt[o]:=k;

// for i:=1 to count do

// form1.Memo1.Lines.Add(IntToStr(t[o,i]));

// form1.Memo1.Lines.Add('длина ровна'+FloatToStr(k));

end;

procedure TForm1.Button1Click(Sender: TObject);

var datetime1,datetime2:TDateTime;

st1: string;

i,j,k :integer;

begin

dateTime1:=Time;

randomize;

for i:=1 to count do

for j:=1 to count do

if i<>j then l[i,j]:=StrToINt(form1.StringGrid1.Cells[i,j])

else l[i,j]:=0;

for i:=1 to count do

for j:=1 to count do

if i<>j then tau[i,j]:=StrToFloat(form1.StringGrid2.Cells[i,j])

else tau[i,j]:=0;

//запускаем первого муравья

muravei(1);

//записваем его результаты

for i:=1 to count do

tm[i]:=t[1,i];

dtm:=dt[1];

for k:=1 to t_max do

begin

for i:=1 to count do

init (i);

for i:=1 to count do

muravei(i);

// если нашли лучшей результат , то записаваем его

for i:=1 to count do

if dtm > dt [i] then

begin

for j:=1 to count do

tm[j]:=t[i,j];

dtm:=dt[i];

// timer1.Interval:=timer1.Interval+1;

end;

for i:=1 to count-1 do

begin

tau[tm[i],tm[i+1]]:=tau[tm[i],tm[i+1]]+1/dtm;

tau[tm[i+1],tm[i]]:=tau[tm[i],tm[i+1]];

//timer1.Interval:=timer1.Interval+1;

end;

tau[tm[1],tm[count]]:=tau[tm[1],tm[count]]+1/dtm;

tau[tm[count],tm[1]]:=tau[tm[1],tm[count]];

for i:=1 to count do

for j:=1 to count do

form1.StringGrid2.Cells[i,j]:=FloatToStr(tau[i,j]);

end;

form1.Memo1.Clear;

for i:=1 to count do

form1.Memo1.Lines.Add(IntToStr(tm[i]));

form1.Memo1.Lines.Add('длина равна '+FloatToStr(dtm));

dateTime2:=Time;

str(8640000*(DateTime2-DateTime1):3:5,st1) ;

caption:=st1+'ms';

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

form1.UpDown1.Position:=5;

form1.StringGrid1.Cells[1,2]:=IntToStr(38);

form1.StringGrid1.Cells[1,3]:=IntToStr(74);

form1.StringGrid1.Cells[1,4]:=IntToStr(59);

form1.StringGrid1.Cells[1,5]:=IntToStr(45);

form1.StringGrid1.Cells[2,1]:=IntToStr(38);

form1.StringGrid1.Cells[2,3]:=IntToStr(46);

form1.StringGrid1.Cells[2,4]:=IntToStr(61);

form1.StringGrid1.Cells[2,5]:=IntToStr(72);

form1.StringGrid1.Cells[3,1]:=IntToStr(74);

form1.StringGrid1.Cells[3,2]:=IntToStr(46);

form1.StringGrid1.Cells[3,4]:=IntToStr(49);

form1.StringGrid1.Cells[3,5]:=IntToStr(85);

form1.StringGrid1.Cells[4,1]:=IntToStr(59);

form1.StringGrid1.Cells[4,2]:=IntToStr(61);

form1.StringGrid1.Cells[4,3]:=IntToStr(49);

form1.StringGrid1.Cells[4,5]:=IntToStr(42);

form1.StringGrid1.Cells[5,1]:=IntToStr(45);

form1.StringGrid1.Cells[5,2]:=IntToStr(72);

form1.StringGrid1.Cells[5,3]:=IntToStr(85);

form1.StringGrid1.Cells[5,4]:=IntToStr(42);

form1.StringGrid2.Cells[1,2]:=IntToStr(3);

form1.StringGrid2.Cells[1,3]:=IntToStr(2);

form1.StringGrid2.Cells[1,4]:=IntToStr(2);

form1.StringGrid2.Cells[1,5]:=IntToStr(2);

form1.StringGrid2.Cells[2,1]:=IntToStr(3);

form1.StringGrid2.Cells[2,3]:=IntToStr(1);

form1.StringGrid2.Cells[2,4]:=IntToStr(1);

form1.StringGrid2.Cells[2,5]:=IntToStr(1);

form1.StringGrid2.Cells[3,1]:=IntToStr(2);

form1.StringGrid2.Cells[3,2]:=IntToStr(1);

form1.StringGrid2.Cells[3,4]:=IntToStr(2);

form1.StringGrid2.Cells[3,5]:=IntToStr(2);

form1.StringGrid2.Cells[4,1]:=IntToStr(2);

form1.StringGrid2.Cells[4,2]:=IntToStr(1);

form1.StringGrid2.Cells[4,3]:=IntToStr(2);

form1.StringGrid2.Cells[4,5]:=IntToStr(1);

form1.StringGrid2.Cells[5,1]:=IntToStr(2);

form1.StringGrid2.Cells[5,2]:=IntToStr(1);

form1.StringGrid2.Cells[5,3]:=IntToStr(2);

form1.StringGrid2.Cells[5,4]:=IntToStr(1);

end;

end.

2. Листинг программы решения задачи распределения файлов в компьютерной сети в среде Delphi.

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

Button1: TButton;

Memo1: TMemo;

StringGrid1: TStringGrid;

Label1: TLabel;

Memo2: TMemo;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

label metka;

const m=5;

const n=3;

var t,i,k,j,number:integer;

pk,gk:string;

log,log1:boolean;

q,g,d,c_f,rec,sx,ps,ro,s,stay:real;

x,xrez,f:array[1..m,1..n] of integer;

p:array[1..m,1..n] of real;

fhelp,tay,b:array[1..n] of real;

v:array[1..n] of integer;

procedure TForm1.Button1Click(Sender: TObject);

begin

randomize;

t:=1; d:=100;

rec:=0.001;

ro:=0.01;

for j:=1 to n do begin

tay[j]:=0.01;

b[j]:=random(150);end;

{b[1]:=1000;b[2]:=1;b[3]:=1;}

for i:=1 to m do

for j:=1 to n do begin

f[i,j]:=random(10);

x[i,j]:=0;end;

for i:=1 to m do v[i]:=random(40)+1;

for j:=1 to n do begin

fhelp[j]:=0;

for i:=1 to m do

fhelp[j]:=fhelp[j]+f[i,j];end;

{-----------------methods begin--------------------------}

while (t<50) do

begin

for i:=1 to m do

for j:=1 to n do

x[i,j]:=0;

memo1.lines.add('t='+inttostr(t));{readln;}

{---------razmeshenie faila--------------}

memo1.Clear;

for i:=1 to m do

begin

s:=0;

for j:=1 to n do

s:=s+fhelp[j]*tay[j];

ps:=0;

for j:=1 to n do

begin

p[i,j]:=(tay[j]*fhelp[j])/(s);

str(p[i,j]:3:3,pk);

memo1.lines.add(pk);

ps:=ps+p[i,j]*100;

end;

{generation g}

log:=false;

while (log=false) do begin

g:=(random(99)+1);

memo1.lines.add('g='+floattostr(g));

number:=0;

q:=p[i,1]*100; {writeln('qb',q:4:2);}

if (g>0)and(g<q) then begin number:=1;log:=true;end;

for j:=1 to n-1 do

begin

if (g>q)and(g<(p[i,j+1]*100+q)) then

begin

number:=j+1;log:=true;

end;

q:=q+p[i,j+1]*100;

{writeln('q=',q:4:2);}

end;

x[i,number]:=1;

log1:=true;

for j:=1 to n do

begin

sx:=0;

for k:=1 to m do sx:=sx+v[k]*x[k,j];

if (sx>b[j]) then log1:=false;

end;

if (log1=false) then

begin log:=false; x[i,number]:=0;end;

memo1.lines.add('num='+inttostr(number)); /////////////////

{readln;}

end;{-------------end generation g----------}

//writeln('-------------');

x[i,number]:=1;

tay[number]:=(1-ro)*tay[number]+tay[number]/d;

stay:=0;

for j:=1 to n do stay:=stay+tay[j];

for j:=1 to n do tay[j]:=(1-ro)*tay[j]+stay/d;

end;{---------------end i----------------------}

c_f:=0;

for k:=1 to m do

for j:=1 to n do

c_f:=c_f+(f[k,j]*v[k]*x[k,j]);

if c_f>rec then begin

for k:=1 to m do

for j:=1 to n do

xrez[k,j]:=x[k,j];

rec:=c_f;end;

memo1.lines.add('c_f='+floattostr(c_f));

t:=t+1;

end;

stringgrid1.ColCount:=n+1;

stringgrid1.RowCount:=m+1;

for i:=1 to m do begin

for j:=1 to n do

form1.StringGrid1.Cells[j,i]:=floattostr(xrez[j,i])

//memo1.lines.add(floattostr(xrez[i,j]));

end;

memo2.lines.add('-----------------ves faila---------------------');

for i:=1 to m do

//i:=1;

memo2.lines.add('ves ' + inttostr(i) + ' faila='+floattostr(v[i]));

memo2.lines.add('------------------ves yzla---------------------');

for j:=1 to n do

//j:=1;

memo2.Lines.Add('ves ' + inttostr(j) + ' yzla=' + floattostr(b[j]));

memo2.lines.add ('c_f='+floattostr(rec));

end;

end.

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

...