Просмотр кода страницы Алгоритм муравейника

{{amerge|1 марта 2010|Муравьиный алгоритм}}
[[Image:Safari ants.jpg|thumb|Поведение муравьёв явилось вдохновением для создания мета эвристической технологии оптимизации|300px]]
'''Алгоритм муравейника''' ([[англ.]] ''Ant colony optimization algorithm'' или ''ACO'') - является вероятностной техникой для решения вычислительных задач, которая может быть сведена к поиску кратчайших путей в виде графиков.
Данный алгоритм входит в семейство муравьиных алгоритмов, метод разведки роем, и представляет собой мета эвристическую ([[англ.]] [[metaheuristic]], meta - "за пределами" и heuristic - "найти") оптимизацию.
Изначально предположен доктором философских наук [[Марко Дориго]]<ref>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.</ref>
<ref name="M. Dorigo, Optimization, Learning and Natural Algorithms">M. Dorigo, ''Optimization, Learning and Natural Algorithms'', PhD thesis, Politecnico di Milano, Italie, 1992.</ref> в [[1992]] году, является первым алгоритмом на правленым на поиск оптимального пути в графе; основано на поведении муравьёв ищущих пути между колонией и источников питания.
==Обзор==
===Краткое изложение===
В реальном мире, [[муравьи]] (первоначально) ходят в случайном порядке и по нахождению продовольствия возвращаются в свою колонию, прокладывая [[феромон]]ами тропы. Если другие муравьи находят такие тропы, они, вероятнее всего, пойдут по ним. Вместо того что бы отслеживать цепочку, они укрепляют её при возвращении, если в конечном итоге находят источник питания.
Со временем, феромонная тропа начинает испарятся, тем самым уменьшая свою привлекательную силу. Чем больше времени требуется для прохождения пути до цели и обратно, тем сильнее испариться феромонная тропа. На коротком пути, для сравнения, прохождение будет более быстрым и как следствие, плотность феромонов остаётся высокой. Испарение феромонов так же имеет свойство избежания, стремления к локально-оптимальному решению. Если бы феромоны не испарялись, то путь выбранный первым был бы самым привлекательным. В этом случае, исследования пространственных решений были бы ограниченными.
Таким образом, когда один муравей находит (например, короткий) путь от колонии до источника пищи, другие муравьи, скорее всего пойдут по этому пути, и положительные отзывы в конечном итоге приводят всех муравьёв к одному, кротчайшему, пути.
===Подробнее===
[[Image:Aco branches.svg|left|400px]]
Оригинальная идея исходит от наблюдения за муравьями в процессе поиска кротчайшего пути от колонии до источника питания.
# Первый муравей находит источник пищи (F), любым способом (а), а затем возвращается к гнезду (N), оставив за собой тропу из феромоны (b).
# Затем муравьи выбирают один из четырёх возможных путей, затем укрепляют его и делают привлекательным.
# Муравьи выбирают кратчайший маршрут, так как у более длинных феромоны сильнее испарились:
Среди экспериментов по выбору между двумя путями неравной длинны, ведущие к от колонии к источнику питания, биологи заметили, то что как правило, муравьи используют кратчайший маршрут.<ref name="S. Goss">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</ref>
<ref>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</ref> Модель такого поведения заключается в следующем:

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

==Вариации алгоритма==
Вот одни из самых популярных вариаций муравьиного алгоритма:
===Элитарная муравей система===
===MMAS (Max-Min муравьиная система)<ref name="T. Stützle et H.H. Hoos">T. Stützle et H.H. Hoos, ''MAX MIN Ant System'', Future Generation Computer Systems, volume 16, pages 889-914, 2000</ref>===
===Пропорциональные псевдослучайные правила===
Представлена выше <ref name="M. Dorigo et L.M. Gambardella">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.</ref>
===Ранг муравьиная система (ASrank)===
===Длительная ортогональная колония муравьёв (COAC)===
статья не до переведена
http://en.wikipedia.org/wiki/Ant_colony_optimization

==Схожесть==
==Приложение==
===Пример: псевдо-код и формула===
 procedure ACO_MetaHeuristic
   while(not_termination)
      generateSolutions()
      daemonActions()
      pheromoneUpdate()
   end while
 end procedure
'''Края:'''<br />
Муравей будет двигаться от узла <math>i</math> к узлу <math>j</math>с вероятностью:<br />
<math>
p_{i,j} = 
\frac
{ (\tau_{i,j}^{\alpha}) (\eta_{i,j}^{\beta}) }
{ \sum (\tau_{i,j}^{\alpha}) (\eta_{i,j}^{\beta}) }
</math>, где<br />
<math>\tau_{i,j}</math> - это количество феромонов на краю <math>i,j</math>;
<math>\alpha</math> - параметр влияния на <math>\tau_{i,j}</math>;
<math>\eta_{i,j}</math> желательный край <math>i,j</math> (априорного знания, как правило,  <math>1/d_{i,j}</math>, где d расстояние);
<math>\beta</math> параметр влияния на <math>\eta_{i,j}</math>.

'''Обновление феромонов'''

===Другие примеры===
====Работа-магазин: проблемы планирования====
====Автомобиль: проблема маршрутизации====
====Задача о назначениях====
====Поставленной задачи====
====Другое====
==Трудности в определении==
==Stigmergy(?) алгоритмами==
==Похожие методы==
==История==
<div class="thumb tright" style="width:210px">
<div class="thumbcaption">
<div class="magnify" class="internal">
<timeline>
ImageSize = width:210 height:300
PlotArea = width:170 height:280 left:40 bottom:10

DateFormat = yyyy
Period = from:1985 till:2005
TimeAxis = orientation:vertical
ScaleMajor = unit:year increment:5 start:1985

Colors=
   id:fond     value:white #rgb(0.95,0.95,0.98)
   id:marque   value:rgb(1,0,0)
   id:marque_fond value:rgb(1,0.9,0.9)
BackgroundColors = canvas:fond

Define $dx = 7 # décalage du texte à droite de la barre
Define $dy = -3 # décalage vertical
Define $dy2 = 6 # décalage vertical pour double texte

PlotData=
  bar:Leaders color:marque_fond width:5 mark:(line,marque) align:left fontsize:S

  from:1989  till:1989 shift:($dx,$dy)    text:коллективное поведение
  from:1991  till:1992 shift:($dx,$dy)    text:Муравьиная система (AS)
  from:1995  till:1995 shift:($dx,$dy)    text:CACO
  from:1996  till:1996 shift:($dx,$dy)    text:ACS
  from:1996  till:1996 shift:($dx,$dy2)   text:MMAS
  from:2000  till:2000 shift:($dx,$dy)   text:GBAS
  from:2001  till:2001 shift:($dx,$dy)   text:многоцелевой

</timeline>
</div>
Хронология алгоритма.
</div>
</div>
Хронология алгоритмов муравейника:
* [[1959]], Пьер-Поль Грасс изложил теорию [[Stigmergy]], что бы объяснить поведение колонии термитов.<ref>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.</ref>;
* [[1983]], Денеборг и его коллеги изучали коллективного поведения муравьёв <ref>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.</ref>;
* [[1988]], Мэйсон Мандерский опубликовал статью о "само-организации" среди муравьёв <ref name="F. Moyson, B. Manderick">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.</ref>;
* [[1989]], работа Арона, Госса, Денерборга и Пастелеса "коллективное поведение аргентинских муравьёв", которая дала идею алгоритма муравейника.<ref name="S. Goss" />;
* [[1989]], реализация можжели поведения в поисках питания Еблингом и его коллегами <ref>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</ref>;
* [[1991]], М. Дориго предложил понятие "Муравьиная система" в своей докторской дисертации (которая была опубликована в 1992 году).

* [[2001]], IREDA и его сотрудники опубликовали первый многоцелевой алгоритм <ref>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.</ref>

* [[2002]], первое применение в разработке графики, [[Байесовский сети]];

* [[2002]], Бьянки и ее коллеги предложили первый стохастический алгоритм <ref>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.</ref>;

* [[2004]], Злочин и Дориго показывают, что некоторые алгоритмы эквивалентны: стохастического градиентного спуска, крест-энтропии и алгоритмы для оценки распределения 

* [[2005]], первые заявки на складывающиеся проблемы белка.

==Список литературы==
{{Reflist}}
==Публикации (выборочно)==
* [[Marco Dorigo|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 & [[Luca Maria Gambardella|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. [http://www.scholarpedia.org/article/Ant_Colony_Optimization  "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 ''[http://iridia.ulb.ac.be/IridiaTrSeries/IridiaTr2006-023r001.pdf Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique]''. TR/IRIDIA/2006-023

==Внешние Ссылки==
*[http://www.aco-metaheuristic.org/ Ant Colony Optimization Home Page]

{{изолированная статья}}

[[Категория:Алгоритмы оптимизации]]
[[Категория:Эволюционные алгоритмы]]