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

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

Алгоритм муравейника (англ. 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