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

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

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

Обзор

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

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

Подробнее

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

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

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

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

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

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

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

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

Представлена выше

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

статья недопереведена http://en.wikipedia.org/wiki/Ant_colony_optimization

Приложение

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

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 })}}$, где
$\tau _{i,j}$ — это количество феромонов на краю $i,j$; $\alpha$ — параметр влияния на $\tau _{i,j}$; $\eta _{i,j}$ желательный край $i,j$ (априорного знания, как правило, $1/d_{i,j}$, где d расстояние); $\beta$ параметр влияния на $\eta _{i,j}$.

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

История

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

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

• 1959, Пьер-Поль Грасс изложил теорию Stigmergy, что бы объяснить поведение колонии термитов.;
• 1983, Денеборг и его коллеги изучали коллективного поведения муравьёв ;
• 1988, Мэйсон Мандерский опубликовал статью о «само-организации» среди муравьёв ;
• 1989, работа Арона, Госса, Денерборга и Пастелеса «коллективное поведение аргентинских муравьёв», которая дала идею алгоритма муравейника.;
• 1989, реализация можжели поведения в поисках питания Еблингом и его коллегами ;
• 1991, М. Дориго предложил понятие «Муравьиная система» в своей докторской дисертации (которая была опубликована в 1992 году).

• 2001, IREDA и его сотрудники опубликовали первый многоцелевой алгоритм

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

• 2002, Бьянки и ее коллеги предложили первый стохастический алгоритм ;

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

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

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

• 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