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

Содержание

· 1 История

· 2 Обзор

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

o 2.2 Подробнее

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

o 3.1 Элитарная муравьиная система

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

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

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

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

· 4 Сходимость

· 5 Приложение

История

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

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

· 1959 — Пьер-Поль Грассе изложил теорию Stigmergy, чтобы объяснить поведение колонии термитов.^[3];

· 1983 — Денеборг и его коллеги проанализировали коллективное поведение муравьёв^[4];

· 1988 — Мэйсон и Мандерский опубликовали статью о «само-организации» среди муравьёв^[5];

· 1989 — Работа Арона, Госса, Денерборга и Пастелеса «коллективное поведение аргентинских муравьёв», которая дала идею алгоритма муравьиной колонии.^[6];

· 1989 — Реализация модели поведения в поисках питания Еблингом и его коллегами^[7];

· 1991 — М. Дориго предложил понятие «Муравьиная система» в своей докторской диссертации (которая была опубликована в 1992 году).

· 2001 — IREDA и его сотрудники опубликовали первый многоцелевой алгоритм^[8]

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

· 2002 — Бьянки и ее коллеги предложили первый стохастический алгоритм^[9];

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

· 2005 — Первые применения в проблеме сворачивания белка.

Обзор

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

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

В литературе было предложено несколько метаэвристических моделей ACO. Среди них три наиболее успешные:

· 1) ant system (Dorigo 1992, Dorigo et al. 1991, 1996)

· 2) ant colony system (ACS) (Dorigo & Gambardella 1997)

· 3) MAX-MIN ant system (MMAS) (Stutzle & Hoos 2000)

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

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