Алгоритм муравейника

Алгоритм муравейника

Поведение муравьёв явилось вдохновением для создания мета эвристической технологии оптимизации

Алгоритм муравейника (англ. Ant colony optimization algorithm или ACO) — является вероятностной техникой для решения вычислительных задач, которая может быть сведена к поиску кратчайших путей в виде графиков. Данный алгоритм входит в семейство муравьиных алгоритмов, метод разведки роем, и представляет собой мета эвристическую (англ. metaheuristic, meta — «за пределами» и heuristic — «найти») оптимизацию. Изначально предположен доктором философских наук Марко Дориго^{[1] [2]} в 1992 году, является первым алгоритмом направленым на поиск оптимального пути в графе; основано на поведении муравьёв ищущих пути между колонией и источников питания.

Обзор

Краткое изложение

В реальном мире, муравьи (первоначально) ходят в случайном порядке и по нахождению продовольствия возвращаются в свою колонию, прокладывая феромонами тропы. Если другие муравьи находят такие тропы, они, вероятнее всего, пойдут по ним. Вместо того, чтобы отслеживать цепочку, они укрепляют её при возвращении, если в конечном итоге находят источник питания. Со временем феромонная тропа начинает испаряться, тем самым уменьшая свою привлекательную силу. Чем больше времени требуется для прохождения пути до цели и обратно, тем сильнее испарится феромонная тропа. На коротком пути, для сравнения, прохождение будет более быстрым и как следствие, плотность феромонов остаётся высокой. Испарение феромонов так же имеет свойство избежания, стремления к локально-оптимальному решению. Если бы феромоны не испарялись, то путь, выбранный первым, был бы самым привлекательным. В этом случае, исследования пространственных решений были бы ограниченными. Таким образом, когда один муравей находит (например, короткий) путь от колонии до источника пищи, другие муравьи, скорее всего пойдут по этому пути, и положительные отзывы в конечном итоге приводят всех муравьёв к одному, кротчайшему, пути.

Подробнее

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

1. Первый муравей находит источник пищи (F) любым способом (а), а затем возвращается к гнезду (N), оставив за собой тропу из феромонов (b).
2. Затем муравьи выбирают один из четырёх возможных путей, затем укрепляют его и делают привлекательным.
3. Муравьи выбирают кратчайший маршрут, так как у более длинных феромоны сильнее испарились.

Среди экспериментов по выбору между двумя путями неравной длины, ведущих от колонии к источнику питания, биологи заметили, что, как правило, муравьи используют кратчайший маршрут.^{[3] [4]} Модель такого поведения заключается в следующем:

• Муравей (так называемый «Блиц») проходит случайным образом от колонии
• Если он находит источник пищи, то возвращается в гнездо, оставляя за собой след из феромона
• Эти феромоны привлекают других муравьёв находящихся вблизи, которые вероятнее всего пойдут по этому маршруту
• Вернувшись в гнездо они укрепят феромонную тропу
• Если существует 2 маршрута, то по более короткому, за то же время, успеют пройти больше муравьёв, чем по длинному
• Короткий маршрут станет более привлекательным
• Длинные путь в конечном счёте исчезнут из-за испарения феромонов

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

Вариации алгоритма

Вот одни из самых популярных вариаций муравьиного алгоритма:

Элитарная муравей система

MMAS (Max-Min муравьиная система)^[5]

Добавляются граничные условия на количество феромонов (τ_max,τ_min). Феромоны откладываются только на глобально лучших или лучших в итерации путях. Все рёбра инициализируются значением τ_max

Пропорциональные псевдослучайные правила

Представлена выше ^[6]

Ранговая муравьиная система (ASrank)

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

Длительная ортогональная колония муравьёв (COAC)

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

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

Схожесть

Приложение

Пример: псевдо-код и формула

procedure ACO_MetaHeuristic

  while(not_termination)
     generateSolutions()
     daemonActions()
     pheromoneUpdate()
  end while
end procedure

Края:
Муравей будет двигаться от узла i к узлу j с вероятностью:
$p_{i,j} = \frac { (\tau_{i,j}^{\alpha}) (\eta_{i,j}^{\beta}) } { \sum (\tau_{i,j}^{\alpha}) (\eta_{i,j}^{\beta}) }$, где
τ_i,j — это количество феромонов на краю i,j; α — параметр влияния на τ_i,j; η_i,j желательный край i,j (априорного знания, как правило, 1 / d_i,j, где d расстояние); β параметр влияния на η_i,j.

Обновление феромонов τ_i,j = (1 − ρ)τ_i,j + Δτ_i,j

где

τ_i,j — количество феромона на дуге i,j
ρ — скорость испарения феромона
Δτ_i,j — количество отложенного феромона, обычно определяется как

$\Delta \tau^{k}_{i,j} = \begin{cases} 1/L_k & \mbox{if ant }k\mbox{ travels on edge }i,j \\ 0 & \mbox{otherwise} \end{cases}$

где L_k — стоимость k-го пути муравья (обычно длина).

Другие примеры

Работа-магазин: проблемы планирования

Автомобиль: проблема маршрутизации

Задача о назначениях

Поставленной задачи

Другое

Трудности в определении

Stigmergy(?) алгоритмами

Похожие методы

История

Хронология алгоритма.

Хронология алгоритмов муравейника:

• 1959 Пьер-Поль Грасс изложил теорию Stigmergy, что бы объяснить поведение колонии термитов.^[8];
• 1983 Денеборг и его коллеги изучали коллективного поведения муравьёв ^[9];
• 1988 Мэйсон Мандерский опубликовал статью о «само-организации» среди муравьёв ^[10];
• 1989 работа Арона, Госса, Денерборга и Пастелеса «коллективное поведение аргентинских муравьёв», которая дала идею алгоритма муравейника.^[3];
• 1989 реализация можжели поведения в поисках питания Еблингом и его коллегами ^[11];
• 1991 М. Дориго предложил понятие «Муравьиная система» в своей докторской дисертации (которая была опубликована в 1992 году).
• 2001 IREDA и его сотрудники опубликовали первый многоцелевой алгоритм ^[12]
• 2002 первое применение в разработке графики, Байесовские сети;
• 2002 Бьянки и ее коллеги предложили первый стохастический алгоритм ^[13];
• 2004 Злочин и Дориго показывают, что некоторые алгоритмы эквивалентны: стохастического градиентного спуска, перекрестной энтропии и алгоритмы для оценки распределения
• 2005 первые применения в проблеме сворачивания белка.

Список литературы

1. ↑ A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134—142, 1991.
2. ↑ M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
3. ↑ ^{1 2} S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, The self-organized exploratory pattern of the Argentine ant, Naturwissenschaften, volume 76, pages 579—581, 1989
4. ↑ J.-L. Deneubourg, S. Aron, S. Goss et J.-M. Pasteels, The self-organizing exploratory pattern of the Argentine ant, Journal of Insect Behavior, volume 3, page 159, 1990
5. ↑ T. Stützle et H.H. Hoos, MAX MIN Ant System, Future Generation Computer Systems, volume 16, pages 889—914, 2000
6. ↑ M. Dorigo et L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, volume 1, numero 1, pages 53-66, 1997.
7. ↑ X Hu, J Zhang, and Y Li (2008). Orthogonal methods based ant colony search for solving continuous optimization problems. Journal of Computer Science and Technology, 23(1), pp.2-18.
8. ↑ P.-P. Grasse, La reconstruction du nid et les coordinations inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La theorie de la Stigmergie : Essai d’interpretation du comportement des termites constructeurs, Insectes Sociaux, numero 6, p. 41-80, 1959.
9. ↑ J.L. Denebourg, J.M. Pasteels et J.C. Verhaeghe, Probabilistic Behaviour in Ants : a Strategy of Errors?, Journal of Theoretical Biology, numero 105, 1983.
10. ↑ F. Moyson, B. Manderick, The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism, Actes de AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, Californie, 1988.
11. ↑ M. Ebling, M. Di Loreto, M. Presley, F. Wieland, et D. Jefferson,An Ant Foraging Model Implemented on the Time Warp Operating System, Proceedings of the SCS Multiconference on Distributed Simulation, 1989
12. ↑ S. Iredi, D. Merkle et M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms, Evolutionary Multi-Criterion Optimization, First International Conference (EMO’01), Zurich, Springer Verlag, pages 359—372, 2001.
13. ↑ L. Bianchi, L. M. Gambardella et M. Dorigo, An ant colony optimization approach to the probabilistic traveling salesman problem, PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer Verlag, Berlin, Allemagne, 2002.

Публикации (выборочно)

• M. Dorigo, 1992. Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy.
• M. Dorigo, V. Maniezzo & A. Colorni, 1996. «Ant System: Optimization by a Colony of Cooperating Agents», IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26 (1): 29-41.
• M. Dorigo & L. M. Gambardella, 1997. «Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem». IEEE Transactions on Evolutionary Computation, 1 (1): 53-66.
• M. Dorigo, G. Di Caro & L. M. Gambardella, 1999. «Ant Algorithms for Discrete Optimization». Artificial Life, 5 (2): 137—172.
• E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2
• M. Dorigo & T. Stützle, 2004. Ant Colony Optimization, MIT Press. ISBN 0-262-04219-3
• M. Dorigo, 2007. «Ant Colony Optimization». Scholarpedia.
• C. Blum, 2005 «Ant colony optimization: Introduction and recent trends». Physics of Life Reviews, 2: 353—373
• M. Dorigo, M. Birattari & T. Stützle, 2006 Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique. TR/IRIDIA/2006-023

Ссылки

• Ant Colony Optimization Home Page

Связать^?