Блог для любопытных и не только
Оптимизация

Муравьиный алгоритм

  • Название: Алгоритм муравьиной колонии (Ant Colony Algorithms );
  • Применение: Поиск глобального экстремума;
  • Сложность: средний;
  • Входные параметры: целевая функция, заданные ограничения;
  • Результат: Эвристический. Глобальный максимум или минимум

Пример из жизни

Вы не замечали, что природа наделила своих обитателей невероятными механизмами выживания и продолжения рода, которые “оттачивались” миллионами лет эволюции? Причем для выживания и существования природа не заставляет решать математические задачи или знать законы физики.

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

Конечно же, ученые не могли обойти вниманием эти интересные феномены. И одними из первых, кто попали в поле зрения науки, были муравьи. Эти, в буквальном смысле, слепые насекомые, которые каждый день преодолевают огромные расстояния и стараются прокормить свое гнездо. Неудивительно, что этот процесс выживания муравьиного гнезда сопровождается решением такой задачи, как составление оптимального маршрута следования.

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

Действительно, было обнаружено, что муравьи выбирают наиболее проходимые, а самое главное, короткие маршруты следования: от источника пищи до муравейника. Это удивительное открытие потребовало немедленного объяснения, каким образом это происходит. Оказалось, что муравьи обладают некими феромонами (“пахучая” субстанция), которые помогают в поиске выбора оптимального пути.

Муравьи распознают свой феромон следа в настолько низкой концентрации, что 1 мг. следового феромона при оптимальном распределении хватило бы на “провешивание” тропы длиной 120 000 км. Кроме этого, муравьи по запаху феромона могут определить не только природу предмета, но и его размеры и форму. Чтобы понять насколько чувствительны феромоны насекомых можно привести следующий пример – самец ночной бабочки чувствует феромон самки на расстоянии до 10 км.

Историческая справка

Первая версия муравьиного алгоритма предложена  Марко Дориго в 1992 году. Этот замечательный ученый, по сути, предложил математическую модель поведения муравьев, ищущих пути от колонии к источнику пищи и представляет собой метаэвристическую оптимизацию.

Колония муравьев рассматриваться как многоагентная система, в которой каждый агент (муравей) функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, поведение всей системы получается на удивление разумным.

Интересные факты: Число муравьев в одной колонии колеблется от 30 особей до нескольких миллионов. На Земле около 1016  муравьев с общей массой, приблизительно равной массе человечества

Основу «социального» поведения муравьев составляет самоорганизация — множество динамических механизмов, обеспечивающих достижение системой глобальной цели в результате низкоуровневого взаимодействия ее элементов. Принципиальной особенностью такого взаимодействия является использование элементами системы только локальной информации. Самоорганизация является результатом взаимодействия следующих четырех компонентов:

  1. Случайность;
  2. Многократность;
  3. Положительная обратная связь;
  4. Отрицательная обратная связь;
  5. Целевая функция.

Данные компоненты являются ключевыми свойствами муравьиного алгоритма. Рассмотрим их подробней на примере движения муравьев за пищей из муравейника.

Когда муравей движется (картинка 1) из муравейника (точка — F) за пищей (точка — N) на протяжении всего пути откладывается феромон (очевидно, что самый короткий путь помечен зеленой стрелкой – (a)). При этом, чем больше плотность феромона, тем короче путь, соответственно, муравей оставит на длинном участке пути меньше феромона. Чем длинней путь, тем быстрей феромон испарится; меньше его нанесут.

На картинке (2) показана схема движения муравьев – значит со временем (если по всем участкам движется примерно равное количество муравьев) муравьи оставят больше всего феромона на самом коротком участке пути. Таким образом, большинство муравьев выберет самый короткий путь (картинка 3) – то есть оставят еще больше феромона на нем, что уменьшит вероятность движения по другим маршрутам (хотя такая вероятность и сохранится, как видно (картинка 3), один муравей все еще движется по другому участку пути).

Случайность. Из вышеизложенного примера, можно выявить случайную природу движения муравьев. Действительно, на первом этапе муравьи ориентируются на всевозможные варианты построения своего пути. Даже, когда плотность феромона помогает выбрать оптимальный (самый короткий) маршрут, остаются “недоверчивые особи”, которые не оставляют попытки найти более оптимальные маршруты.

Многократность. Безусловно, с одним муравьем или даже десятками особями вряд ли получится осуществить выбор оптимального пути. Нужно много и очень много попыток найти самый короткий путь или хотя бы предупредить остальных, что не нужно двигаться в этом направлении. В качестве такого предупреждения выступает феромон и положительно обратная связь.

Положительная обратная связь. У зоологов это называется стигмержи (stigmergy). Стигмержи — это разнесенный во времени тип взаимодействия, когда один субъект взаимодействия изменяет некоторую часть окружающей среды, а остальные используют информацию об ее состоянии позже, когда находятся в ее окрестности. Таким образом, положительная обратная связь это некая “коллективная память” на основе феромона. Используя эту “память” (на основе проб и ошибок) можно найти правильное решение.

Отрицательная обратная связь. Со временем феромон испаряется, что позволяет муравьям адаптировать свое поведение под изменения внешней среды. Распределение феромона по пространству передвижения муравьев является своего рода динамически изменяемой глобальной памятью муравейника. Любой муравей в фиксированный момент времени может воспринимать и изменять лишь одну локальную ячейку этой глобальной памяти.

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

Математическое моделирование

Осталось свести идеи алгоритма к математическим формулам, которые будут подробно описаны. Действительно, как же Марко Дориго смог смоделировать движение муравья? Рассмотрим на примере классической математической задачи “коммивояжера”.

  1. Определяется целевая функция. Введем целевую функцию для поиска кратчайшего расстояния: \( n= \frac{1}{D} \), где \(D\) – расстояние до заданного пункта;
  2. Считаются вероятности перехода в заданную точку:

\( P = \frac{t^a\cdot n^b}{\sum\limits_{i=1}^mt_i^a\cdot n_i^b}\), где \( a, b \)– настраиваемые параметры, \( t  \) концентрация феромона; Обратите внимание, в числителе находится выражение  ta * nb – При a = 0 выбирается ближайший город и алгоритм становится “жадным” (который выбирает только оптимальные или самые короткие расстояния), При b = 0 будут учитываться только след феромона, что может привести к сужению пространства поиска оптимального решения.

  1. Обновление феромона: t(i+1) = (1-p)*t(i)+Q/L0, p(настраивает скорость испарения) и Q (настраивает концентрацию нанесения феромона); L0 – длина пути на определенном участке пути.

Это все математические выкладки, которые могут понадобиться при решении задачи с использованием этого алгоритма.

Задача коммивояжера состоит в поиске кратчайшего замкнутого маршрута, проходящего через все города ровно один раз. На примере видно, что коммивояжер посещает последовательно ряд узлов в графе или городов (6-2-3-4-5-1-6) – это напоминает стратегию недобросовестного продавца, который не может возвратиться в город, который посетил.

Постановка задачи:

Необходимо найти глобальный экстремум функции (может быть негладкой т.е. недеффиринцирумой) на заданной области определения с заданной точностью за приемлемое время.

Лингвистическое описание алгоритма:  

Пример реализации: Моделируется ситуация с одним муравьем, который оказался в вершине графа под номером 6. Таким образом, муравей может пойти в 1, 2, 3, 4, 5 вершины (в таблице и на графе обозначены, синим цветом). На первом шаге, устанавливается для простоты расчётов значение феромона для всех вершин графа = 0.5 (конечно можно выбрать для каждой вершины произвольные значения, но сейчас это не принципиально) на всех участках пути.

ПЕРВАЯ ИТЕРАЦИЯ

1.Определим вероятность перехода в одну из вершин (для простоты обозначим α=1 и β=1 о подборе этих алгоритмических параметров мы поговорим далее), обратите внимание, эти матапараметры будут неизменны на протяжении всего алгоритма.

 

2. На втором этапе, необходимо выбрать маршрут. Обратите внимание, что выбор происходит не по большей вероятности, а путем разыгрывания случайной величины от 0 до 1 (метод рулетки).

3.Воспользуемся калькулятором функцией rand – в моем случае получилось 0.52, поэтому выбор падает на маршрут из 6 в 2. Запомним вершину, которую уже посетили, в таблице обозначим как красные столбцы, а на рисунке перечеркнутая вершина.

ВТОРАЯ ИТЕРАЦИЯ

1.В вершине 2 определяем все возможные пути движения. Считаем вероятности перехода в 1, 3, 4, 5.

2.Выбираем маршрут путем разыгрывания случайной величины от 0 до 1 (метод рулетки).

3.Воспользуемся калькулятором функцией rand – в моем случае получилось 0.2, поэтому выбор падает на маршрут из 2 в 3. Запомним вершину, которую уже посетили, в таблице обозначим как красные столбцы, а на рисунке перечеркнутая вершина. Оранжевым цветом обозначим посещенные вершины.

ТРЕТЬЯ ИТЕРАЦИЯ

1.В вершине 2 определяем все возможные пути движения. Считаем вероятности перехода в 1, 3, 4, 5.

2. Выбираем маршрут путем разыгрывания случайной величины от 0 до 1 (метод рулетки), получается 0.1, таким образом, муравей отправится в 4 город.

3.Запомним вершину, которую уже посетили, в таблице обозначим как красные столбцы, а на рисунке перечеркнутая вершина. Оранжевым цветом обозначим посещенные вершины.   

ЧЕТВЕРТАЯ ИТЕРАЦИЯ

1.В вершинеопределяем все возможные пути движения. Считаем вероятности перехода в  1, 5.

2. Выбираем маршрут путем разыгрывания случайной величины от 0 до 1 (метод рулетки).

Воспользуемся калькулятором функцией rand – в данном случае получилось 0.6, поэтому выбор падает на маршрут из 4 в 5.

3. Запомним вершину, которую уже посетили, в таблице обозначим как красные столбцы, а на рисунке перечеркнутая вершина. Оранжевым цветом обозначим посещенные вершины.   

ПЯТАЯ ИТЕРАЦИЯ (ПОСЛЕДНЯЯ)

1. В вершине 5 определяем все возможные пути движения. К счастью, таких путей нет, кроме 1. Поэтому можно не рассчитывать вероятность и выбрать первый маршрут. Соответственно, из первой вершины можно попасть только в 6.

В конце полного прохода, выполняется обновление феромона (часть феромона должна испариться). Далее определяется ∆τ =  Q/D, где является таким же метапараметром (настоечный параметр) алгоритма, для простоты расчета примем Q = 1, D – расстояние до определенного узла, например, для второго узла, где D2 = 1.

∆τ =  1/1 = 1

Обновляем каждый феромон по формуле:

PМатапараметр, который определяет скорость испарения. При P > 1 испарение увеличивается, P < 1 испарение уменьшается. Примем P = 0.5 после окончания итерации пересчитываются нанесенный феромон, который должен испариться.

Подведем итоги и опишем работу алгоритма:

Шаг 1. Происходит инициализация муравьев (на каждый узел “помещается” муравей, т.е. число узлов равно числу муравьев). Под этим процессом понимается создание блоков “памяти”, в которых должны храниться различные параметры, которые должен помнить агент или муравей. К ним относятся: узлы графа (города), которые посетил муравей, длина пройденного пути;

Шаг 2. Происходит инициализация среды. Нанесение первоначального феромона на каждый участок пути, первоначально делается произвольным образом; устанавливаются опционные параметры алгоритма: α (степень “жадности” алгоритма), β (влияние феромона на поиск оптимального решения), P (скорость испарения феромона), Q (распределение феромона на участке пути).

Шаг 3. Запускается итеративный (повторный) процесс для каждого муравья. Для текущего муравья выбирается путь следования из всех возможных вариантов с помощью формулы (2). При этом получается набор вероятностей для каждого пути следования.

Шаг 4. Разыгрывается методом рулетки один вариант пути следования и помещается в “память” муравья, как посещенный город и рассчитанное расстояние.

Шаг 5. После завершения итерации для отдельного муравья, пересчитывается количество феромона на каждом участке пути по формуле (3). Осуществляется переход к шагу 2 до окончании итерации.

Шаг 6. Поиск в сохранных значениях минимального расстояния и порядок следования.

Блок-схема

Программная реализация
1. Создадим класс Ant, как было указано в первом шаге алгоритма необходимо инициализировать муравьев и среду (метапараметры алгоритма).Объявим в классе ряд констант и свойств, которые отвечают указанным требованиям:

2. Напишем конструктор для класса — в нем производим генерацию городов с соответствующими координатами. По координатам рассчитываем Евклидово расстояние между городами ($this->distance[$from][$to] = sqrt( $delta_x**2 + $delta_y**2 )) и «наносим» феромон на каждый отрезок пути —  $this->pheromone[$i][$j]= self::PHEROMONE.Таким образом, «внешняя среда» (города, расстояния между ними и нанесенный феромон) подготовлена и необходимо переходить к инициализации муравьев или муравьиной памяти ($this->antInit()).

Каждый муравей должен обладать памятью о ($this->ants[$ant][‘current_city’] — текущем городе, где он находится; $this->ants[$ant][‘tabu_cities’] — список городов, которые он не может посетить ( вспомните задачу «коммивояжёра» ); $this->ants[$ant][‘traversed_length’] — общая длина пройденного пути (по который можно судить о лучшем решении); $this->ants[$ant][‘path_index’] — общее количество посещенных городов. Обратите внимание, каждый муравей помещается в разные начальные города (вершины графа) — $this->ants[$ant][‘current_city’] = $count++.

3. Запускается итеративный процесс движения муравьев, который реализуют два метода: movingAnts(суммируется пройденный путь, запоминаются текущий город — current_city, следующий город — next_city и т.д.); и метод — $this->selectNextCity,

4. который осуществляет выбор следующего города на основе вычисления вероятности перехода и метода рулетки:

5. После прохода каждого муравья по всему пути, необходимо пересчитать феромон, который должен испариться и остаться после нанесения муравья:

6.Метод  run() запускает дополнительный процесс итерации, чтобы алгоритм работал дольше, не привязываясь к количеству муравьев self::MAX_EPOCH.

Заключение

В этой статье был кратко рассмотрен муравьиный алгоритм, который хорошо подходит для задач оптимизации. Стоит упомянуть, что существуют другие реализации этого алгоритма. связанные с введением так называемых элитных муравьев (данные муравьи ищут только оптимальные маршруты и их результаты учитываются при определении окончательного решения). В некоторых работах показана эффективность муравьиного алгоритма, находит близкие к оптимуму решения за значительно меньшее время даже для задач большой размерности (n > 20) . Более того, алгоритм не требует, чтобы целевая функция была гладкой(т.е. была дифференцируема).

К достоинствам можно отнести:

  • Работают лучше, чем другие алгоритмы (генетические алгоритмы, нейронные сети и т.д.);
  • Опираются на память обо всей колонии вместо памяти только о предыдущем поколении;
  • Меньше подвержены неоптимальным начальным решениям (из-за случайного выбора пути и памяти колонии);
  • Могут использоваться в динамических приложениях (адаптируются к изменениям, скажем, расстояний);
  • Успешно применялись к множеству различных задач (Routing, Traveling Salesman Problem, Vehicle Routing, Machine Learning и т.д.).

К недостаткам можно отнести:

  • Сходимость гарантируется, но время сходимости не определено;
  • Необходимо применение дополнительных методов таких, как локальный поиск;
  • Сильно зависят от метапарметров (настоечных), которые подбираются только исходя из экспериментов.

Список литературы

  1. Джонс М. Т. Программирование искусственного интеллекта в приложениях. – 2011.;
  2. Штовба С. Д. Муравьиные алгоритмы //Exponenta Pro. Математика в приложениях. – 2003. – Т. 4. – С. 70-75.;
  3. Dorigo M. Optimization, learning and natural algorithms //PhD Thesis, Politecnico di Milano. – 1992.;
  4. 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.
  5. C. Blum, 2005 «Ant colony optimization: Introduction and recent trends». Physics of Life Reviews, 2: 353—373
  6. Чураков М., Якушев А. Муравьиные алгоритмы //Электронные данные.–Режим доступа: http://rain. ifmo. ru/cat/, свободный.–Загл. с экрана. – 2006. 
  7. Муравьиные алгоритмы

Полезная информация

https://www.youtube.com/watch?v=EwDP_bAb-OI

Поделиться

Отправить ответ

avatar
tube

Видео хорошее, описание кода не очень и зачем на php?

hooper

Понятно в целом, но формулы нужно переделать

Aleksey

Интересно решение на php.
Но формулы конечно не корректные в выборе следующего города.

wpDiscuz