Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Краткое изложениеСтр 1 из 3Следующая ⇒ Содержание · 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) Краткое изложение В реальном мире, муравьи (первоначально) ходят в случайном порядке и по нахождению продовольствия возвращаются в свою колонию, прокладывая феромонами тропы. Если другие муравьи находят такие тропы, они, вероятнее всего, пойдут по ним. Вместо того, чтобы отслеживать цепочку, они укрепляют её при возвращении, если в конечном итоге находят источник питания. Со временем феромонная тропа начинает испаряться, тем самым уменьшая свою привлекательную силу. Чем больше времени требуется для прохождения пути до цели и обратно, тем сильнее испарится феромонная тропа. На коротком пути, для сравнения, прохождение будет более быстрым и как следствие, плотность феромонов остаётся высокой. Испарение феромонов также имеет свойство избежания стремления к локально-оптимальному решению. Если бы феромоны не испарялись, то путь, выбранный первым, был бы самым привлекательным. В этом случае, исследования пространственных решений были бы ограниченными. Таким образом, когда один муравей находит (например, короткий) путь от колонии до источника пищи, другие муравьи, скорее всего пойдут по этому пути, и положительные отзывы в конечном итоге приводят всех муравьёв к одному, кратчайшему, пути.
|