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

12.1. Биологический прототип и простейшие модели

Муравьи появились на земле более 100 миллионов лет назад и в настоящее время их популяция составляет $$10^{16}$$ особей [1], общий вес которой соизмерим с весом проживающих людей. Большинство муравьев являются социальными насекомыми, которые живут колониями от 30 до миллиона особей. При относительно простом поведении каждой отдельной особи муравьиные колонии представляют сложную социальную структуру и способны решать сложные задачи, например, находить оптимальные пути от гнезда до источника пищи. Это привлекло внимание многих исследователей, которые изучали механизмы взаимодействия особей колонии. Среди них, прежде всего, привлекла внимание исследователей непрямая форма связи между особями, которая была названа "стигметрия" ("stigmergy") и представляет собой разнесенное во времени взаимодействие, при котором одна особь изменяет некоторую область окружающей среды, а другие особи используют эту информацию в процессе решения задачи. Эта информация (изменение окружающей среды) носит локальный характер – она может быть изменена (и воспринята) только насекомыми, посетившими данный локус – участок среды. Стигметрия является непрямой и асинхронной формой коммуникации, в которой насекомые изменяют окружающую среду для передачи информации другим насекомым, которые реагируют на это изменение. Слово "stigmergy" образовано из двух греческих слов: "stigma", означающее знак; "ergon" - работа. Особи воспринимают сигналы (в виде знаков), которые порождают некоторый отклик или действие. Определены две формы стигметрии[2]: сематектоническая (sematectonic) и знаковая(sign-based). Сематектоническая относится к коммуникации посредством изменения физических характеристик окружающей среды. Примером сематектонической стигметрии являются действия при постройке гнезда, его очистке и выращивании выводка. Сигнальная стигметрия реализует коммуникацию с помощью сигнального механизма в виде химических соединений, откладываемых муравьями.

Конкретно, во многих муравьиных колониях стигметрия реализуется с помощью специального фермента "феромона", который откладывается муравьем в процессе движения. При этом муравей помечает феромоном посещенный участок среды. Остальные муравьи воспринимают "запах" отложенного феромона и стараются следовать по отмеченному пути. Это порождает асинхронную и непрямую схему коммуникации, где муравьи передают информацию друг другу с помощью феромона. При этом возникает положительная обратная связь – даже малое количество феромона заставляет муравьев идти по помеченному пути и откладывать на нем все большее количество фермента. Адаптивность поведения муравьев основана на восприятии испарений феромона, которое в природе продолжается несколько суток. Можно провести аналогию между распределением феромона в окружающем колонию пространстве и глобальной памятью муравейника, которая носит динамический характер.

Муравьиные алгоритмы (МА), как и большинство, ранее рассмотренных видов эволюционных алгоритмов, основаны на использовании популяции потенциальных решений и разработаны для решения задач комбинаторной оптимизации, прежде всего, поиска различных путей на графах. Кооперация между особями (искусственными муравьями) здесь реализуется на основе моделирования стигметрии. При этом каждый агент, называемый искусственным муравьем, ищет решение поставленной задачи. Искусственные муравьи последовательно строят решение задачи, передвигаясь по графу, откладывают феромон и при выборе дальнейшего участка пути учитывают концентрацию этого фермента. Чем больше концентрация феромона в последующем участке, тем больше вероятность его выбора.

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

Рассмотрим эксперименты с препятствиями, которые показаны на рис.12.1,рис.12.2,рис.12.3,рис.12.4 [3].

(рис 12.1) Движение муравьев без препятствия. (рис 12.2) Препятствие на пути между гнездом и пищей. (рис 12.3) Начальная фаза движения муравьев с препятствием. (рис 12.4) Выбор муравьями кратчайшего пути.

Здесь на первом рисунке показано движение муравьев между гнездом и источником пищи без препятствия. Далее на рис.12.1,рис.12.2,рис.12.3,рис.12.4 показан характер движения в том случае, когда на пути возникло препятствие.

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

Не менее известный эксперимент с двумя мостами был проведен с колонией аргентинских муравьев, который представлен на рис.12.5,рис.12.6 [4].Здесь на пути между гнездом и пищей необходимо сделать выбор одного из двух мостов.

(рис 12.5) Эксперимент с двумя мостами. (рис 12.6) Выбор кратчайшего пути.

Здесь на рис.12.5 показан случай с двумя эквивалентными путями между гнездом и пищей. Эксперименты показали одинаковую концентрацию муравьев на обоих возможных путях. Далее на рис.12.6 представлен случай, когда мосты имеют разную длину. В начальной фазе муравьис равной вероятностью выбирают мосты. Но далее, при увеличении концентрации феромона на коротком пути они выбирают оптимальный путь.

Пусть $$n_A(t)$$ и $$n_B(t)$$ обозначают число муравьев на путях A и B соответственно в момент времени $$t$$. Эмпирически было найдено, что вероятность выбора моста в момент времени $$t$$ происходит в соответствии со следующей формулой [4]:

$$P_A(t+1)=\frac{(c+n_A(t))^{\alpha}}{(c+n_A(t))^{\alpha}+(c+n_B)^{\alpha}}=1-P_B(t+1),$$

где $$c$$ характеризует степень "привлекательности" неисследованной ветви, и $$\alpha$$ определяет смещение при использовании феромона в процессе выбора варианта решения. На основе вероятностей, определяемых (12.1), правило выбора муравьем моста можно сформулировать следующим образом. Пусть случайным образом генерируется число U(0,1) в интервале (0,1).

Если $$U(0,1)\le P_A(t+1)$$, то муравей выбирает путь A, иначе – путь B.

Отметим, что несмотря на то, что муравьиная колония демонстрирует сложное адаптивное поведение, которое позволяет ей решать трудные задачи, поведение одного муравья подчиняется достаточно простым правилам. Муравья можно рассматривать как агента, подвергающегося воздействию и формирующего на него соответствующую реакцию: муравей воспринимает концентрацию феромона и на этой основе выполняет действие. Поэтому муравей абстрактно может рассматриваться как простой вычислительный агент. Искусственный муравей алгоритмически моделирует простое поведение реального муравья (точнее его интересующие нас аспекты). Логика поведения искусственного муравья представлена в алгоритме А12.1 [2].

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

12.2. Простой муравьиный алгоритм

Первые муравьиные алгоритмы, разработанные в [1], относятся по современной классификации к "муравьиным системам" (antsystems), которые будут изложены ниже. Сначала мы рассмотрим (исключительно в учебных целях) простой муравьиный алгоритм (ПМА) (simple ant colony optimization -SACO), в котором фактически формализованы приведенные выше экспериментальные исследования и представлены основные аспекты муравьиных алгоритмов (МА) [2].

В качестве иллюстрации возьмем задачу поиска кратчайшего пути между двумя узлами графа $$G=(V,E)$$, где $$V$$– множество узлов (вершин), а $$E$$ – матрица, которая представляет связи между узлами. Пусть $$n_G=|V|$$- число узлов в графе. Обозначим $$L^k$$– длину пути в графе, пройденного $$k$$-м муравьем, которая равна числу пройденных дуг (ребер) от первой до последней вершины пути. Пример графа с выделенным путем представлен на рис.12.7. С каждой дугой, соединяющей вершины $$(i,j)$$, ассоциируем концентрацию феромона $$\tau_{ij}$$.

(рис 12.7) Пример графа.

Строго говоря, в начальный момент времени концентрация феромона для каждой дуги графа нулевая, но мы для удобства каждой дуге присвоим небольшое случайное число $$\tau_{ij}(0)$$.

Муравей выбирает следующую дугу пути случайным образом в фактически в соответствии с алгоритмом 12.1 следующим образом. Множество муравьев $$k=\{1,…,n_k\}$$ помещаются в начальную вершину. В каждой итерации ПМА каждый муравей пошагово строит путь до конечной вершины. При этом в каждой вершине каждый муравей должен выбрать следующую дугу пути. Если $$k$$-ймуравей находится в $$i$$-ой вершине,то он выбирает следующую вершину $$j\in N_i^k$$ на основе вероятностей перехода

$$p_{ij}^k(t)=\begin{cases}\frac{\tau_{ij}^{\alpha}(t)}{\sum_{j\in N_j^k} \tau_{ij}^{\alpha}(t)},\mbox{если $j\in N_i^k$}\\0,\mbox{если $j\notin N_i^k$}\end{cases}.$$

Здесь $$N_i^k$$ представляет множество возможных вершин, связанных с $$i$$-й вершиной, для $$k$$-го муравья. Если для любого $$i$$-го узла и $$k$$-го муравья $$N_i^k=\varnothing$$, тогда предшественник узла $$i$$ включается в $$N_i^k$$. В этом случае в пути возможны петли. Эти петли удаляются при достижении конечного города пути. В (12.2) $$\alpha$$- положительная константа, которая определяет влияние концентрации феромона. Очевидно большие значения $$\alpha$$ повышают влияние концентрации феромона. Это особенно существенно в начальной стадии для начальных случайных значений концентрации, что может привести к преждевременной сходимости к субоптимальным решениям. Когда все муравьи построили полный путь от начальной до конечной вершины, удаляются петли в путях, и каждый муравей помечает свой построенный путь, откладывая для каждой дуги феромон в соответствии со следующей формулой

$$\Delta\tau_{ij}^k(t)=\frac{1}{L^k(t)}$$

Здесь $$L^k(t)$$ – длина пути, построенного $$k$$-м муравьем в момент времени $$t$$.

Таким образом, для каждой дуги графа концентрация феромона определяется следующим образом

$$\tau_{ij}(t+1)=\tau_{ij}(t)+\sum_{k=1}^{n_k}\Delta\tau_{ij}^k(t),$$

где $$n_k$$- число муравьев. Из (12.3) следует, что общая концентрация феромона для данной дуги пропорциональна "качеству" путей, в которые входит эта дуга, поскольку откладываемое количество феромона согласно (12.3) отражает "качество" соответствующего пути. В данном случае "качество" обратно пропорционально длине пути (числу дуг, вошедших в путь). Но в общем случае может быть использована и другая мера качества (например, стоимость проезда по данному пути или геометрическое расстояние и т.п.). Пусть $$x^k(t)$$ обозначает решение в момент $$t$$, и некоторая функция $$f(x^k(t))$$ выражает качество решения. Если $$\Delta\tau^k$$ не пропорционально качеству решения и все муравьи откладывают одинаковое количество феромона $$(\Delta\tau_{ij}^1=\Delta\tau_{ij}^2=\dots=\Delta\tau_{ij}^k)$$, то существует только один фактор, который зависит от длины пути и способствует выбору коротких путей. Это ведет к двум основным способам оценки качества решений, которые используются в МА:

неявная оценка, где муравьи используют отличие в длине путей относительно построенных путей другими муравьями;

явная оценка, количество феромона пропорционально некоторой мере качества построенного решения.

В нашем случае мы имеем явную оценку качества решения согласно (12.3), которая ведет к тому, что дуги, входящие в длинные пути, становятся менее привлекательными для окончательных решений.

В алгоритме А12.2 [2] могут быть использованы различные критерии окончания, например,

окончание при превышении заданного числа итераций;

окончание по найденному приемлемому решению $$f(x^k(t)\le\varepsilon$$;

окончание, когда все муравьи следуют одним и тем же путем.

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

$$\tau_{ij}(t)\gets (1-\rho)\tau_{ij}(t),$$

где $$\rho\in[0,1]$$. При этом константа $$\rho$$ определяет скорость испарения, которое заставляет муравьи "забывать" предыдущие решения. Очевидно, что при больших значениях $$\rho$$ феромон испаряется быстро, в то время как малые значения $$\rho$$ способствуют медленному испарению. Отметим, что чем больше испаряется феромон, тем поиск становится более случайным.

Так при $$\rho=1$$ мы имеем случайный поиск.

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

Эксперименты (DorigoM., DiCaro [4]) показали, что:

ПМА работает хорошо для очень маленьких графов и в большинстве случаев находит кратчайший путь;

для больших графов характеристики ухудшаются, алгоритм становится менее стабильным и более чувствительным к выбору параметров;

сходимость к кратчайшему пути хорошая при малом числе муравьев, в то время как большое количество муравьев часто ведет к тому, что процесс поиска не сходится;

эффект испарения более важен для сложных графов. В этом случае при $$\rho=0$$ (нет испарения) алгоритм часто не сходится. С другой стороны, если феромон испаряется слишком быстро (большие значения $$\rho$$), алгоритм часто сходится к субоптимальным решениям;

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

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

12.3.Муравьиная система

Первый муравьиный алгоритм был разработан M.Дориго[2].По современной классификации он относится к (antsystem) муравьиной системе (МС). По сравнению с простым муравьиным алгоритмом в МС улучшены характеристики за счет изменения метода вычисления вероятности выбора следующей вершины путем учета эвристической информации и ввода списка запрещенных вершин (tabulist). Конкретно, в МС вероятность перехода из $$i$$-ой вершины в $$j$$-ю вершину определяется следующим образом

$$p_{ij}^k(t)=\begin{cases}\frac{\tau_{ij}^{\alpha}(t)\eta_{ij}^{\beta}(t)}{\sum_{u\in N_j^k} \tau_{iu}^{\alpha}(t)\eta_{iu}^{\beta}(t)},\mbox{если $j\in N_i^k(t)$}\\0,\mbox{если $j\notin N_i^k(t)$}\end{cases}.$$

где: 1) $$\tau_{ij}$$ представляет апостериорную эффективность перехода из вершины $$i$$ в $$j$$, которая определяется интенсивностью феромона для соответствующей дуги; 2) $$\eta_{ij}$$ представляет априорную эффективность перехода из $$i$$ в $$j$$ на основе некоторой эвристики.

Вероятность перехода в МС, определяемая (12.6), отличается от аналога в ПМА, заданной (12.2), двумя аспектами:

При вычислении вероятности перехода в МС предпринята попытка сбалансировать влияние интенсивности феромона $$\tau_{ij}$$(отражающее предысторию успешных действий) и эвристической информации $$\eta_{ij}$$(выражающее предпочтительность некоторого выбора). Этот баланс управляет процессом эксплуатации-расширения в пространстве поиска решения. Баланс регулируется значениями коэффициентов $$\alpha$$ и $$\beta$$. При $$\alpha=0$$ информация о концентрации феромона не используется и предыдущий опыт игнорируется. Если $$\beta=0$$, то не учитывается эвристическая информация и мы имеем простой МА. Эвристическая информация о предпочтительности выбора следующей вершины можетпредставляться в различной форме и зависит от задачи. Например, для выбора кратчайшего пути можно использовать $$\eta_{ij}=\frac{1}{d_{ij}}$$, где $$d_{ij}$$- расстояние между вершинами $$i$$ и $$j$$. Очевидно, что в этом случае предпочтительней короткая дуга, исходящая из вершины $$i$$.

Множество $$N_i^k$$ определяет множество допустимых вершин для $$k$$-го муравья. Это множество может включать соседние к $$i$$ вершины, которые не посещались $$k$$-м муравьем. Для этого для каждого муравья создается и отслеживается табу-список. Вершины из этого списка удаляются из $$N_i^k$$, поскольку каждая вершина может посещаться только один раз.

Некоторые авторы [6] вместо (12.6) в МС используют другую форму выражения для вероятности:

$$p_{ij}^k(t)=\begin{cases}\frac{\alpha\tau_{ij}(t)+(1-\alpha)\eta_{ij}(t)}{\sum_{u\in N_j^k}(\alpha\tau_{iu}(t)+(1-\alpha)\eta_{iu}(t))},\mbox{если $j\in N_i^k(t)$}\\0,\mbox{если $j\notin N_i^k(t)$}\end{cases}.$$

Здесь параметр $$\alpha$$ определяет относительную важность концентрации феромона $$\tau_{ij}(t)$$ по сравнению с эвристикой $$\tau_{ij}$$. Данный вариант МС по сравнению с предыдущим не требует задания параметра $$\beta$$.

Испарение феромона реализуется согласно (12.5) – после построения пути каждым муравьем, концентрация феромона на каждой дуге корректируется следующим образом:

$$\tau_{ij}(t+1)=\tau_{ij}(t)+\Delta\tau_{ij}(t),$$

где

$$\Delta\tau_{ij}(t)=\sum_{k=1}^{n_k}\Delta\tau_{ij}^k(t)$$

и $$\Delta\tau_{ij}^k(t)$$- количество феромона, откладываемое муравьем $$k$$ на дуге $$(i,j)$$ в момент времени $$t$$.

M.Дориго разработал три модификации МС, которые отличаются методом вычисления $$\Delta\tau_{ij}^k$$(в предположении, что решается задача минимизации):

Ant-cycle AS, где

$$\Delta\tau_{ij}^k(t)=\begin{cases}\frac{Q}{f(x^k(t))},\mbox{если дуга $(i,j)$ есть в пути $x^k(t)$}\\0,\mbox{иначе}\end{cases},$$

где $$Q$$- положительная константа. Здесь количество феромона откладывается обратно пропорционально качеству $$f(x^k(t))$$ на дугах полного пути, построенного муравьем. При этом для изменения концентрации феромона используется глобальная информация.

При решении задач максимизации в этом случае

$$\Delta\tau_{ij}^k(t)=\begin{cases}Qf(x^k(t)),\mbox{если дуга $(i,j)$ есть в пути $x^k(t)$}\\0,\mbox{иначе}\end{cases},$$

Ant-density AS, где

$$\Delta\tau_{ij}^k(t)=\begin{cases}Q,\mbox{если дуга $(i,j)$ есть в пути $x^k(t)$}\\0,\mbox{иначе}\end{cases},$$

В этой модификации каждый муравей откладывает одинаковое количество феромона на любой дуге построенного пути. Этот подход учитывает только количество муравьев, прошедших по данной дуге $$(i,j)$$. Чем выше плотность трафика на дуге, тем более она привлекательна для окончательного решения.

Ant-quantity AS, для которой

$$\Delta\tau_{ij}^k(t)=\begin{cases}\frac{Q}{d_{ij}},\mbox{если дуга $(i,j)$ есть в пути $x^k(t)$}\\0,\mbox{иначе}\end{cases}.$$

В этом случае при коррекции концентрации феромона используется только локальная информация – расстояние $$d_{ij}$$ и МС предпочитает выбирать короткие дуги.

В целом МС-алгоритм представлен ниже псевдокодом A12.3[6]. Здесь на этапе инициализации размещение муравьев определяется решаемой задачей. Если целью является поиск кратчайшего пути между заданными вершинами графа, то все $$n_k$$ муравьев размещаются на начальной вершине. С другой стороны, если целью является построение кратчайшего гамильтонова цикла (соединяющего все вершины), то $$n_k$$ муравьев случайно размещаются на всем графе. Это расширяет пространство поиска. Инициализация феромона выполняется с помощью либо малой константы $$\tau_0$$, либо небольших значений из диапазона $$[0,\tau_0]$$.

Автор МС M.Дориго[6] исследовал характеристики всех трех приведенных модификаций, прежде всего, при решении задачи коммивояжера. Версия Ant-cycle AS работала быстрее, в силу использования глобальной информации.

Кроме этого Дориго[6] ввел стратегию элитизма, где в дополнение коррекции феромона согласно (12.4) дополнительно добавляется количество феромона, пропорциональное длине лучшего пути для всех его дуг следующим образом:

$$\tau_{ij}(t+1)=\tau_{ij}(t)+\Delta\tau_{ij}(t)+n_e\Delta\tau_{ij}^e(t),$$

где

$$(t)=\begin{cases}\frac{Q}{f(\tilde x(t))},\mbox{if $(i,j)\in\tilde x(t)$}\\0,\mbox{иначе}\end{cases}.$$

Здесь $$e$$– число элитных муравьев, $$\tilde x(t)$$- лучшее корректное решение с $$f(\tilde x(t))=\min_{k=1\dots n_k}\{f(x^k(t))\}.$$.

12.4 Система муравьиных колоний

Дальнейшее развитие подход, разработанный в МС, получил в методе, который по современной классификации относится к "системе муравьиных колоний" (СМК) (ant colony system – ACS[7]). По сравнению с предыдущим данный метод отличается по четырем аспектам: 1) используется другое правило перехода ; 2) применяется другое правило изменения концентрации феромона; 3) вводится локальная коррекция феромона; 4) используются списки кандидатов, которые отдают предпочтение некоторым вершинам. Далее мы рассмотрим реализацию этих модификаций.

В данном методе используется правило перехода, которое можно назвать "псевдослучайно-пропорциональное", где $$k$$-й муравей, находясь в вершине $$i$$, выбирает очередную вершину $$j$$ следующим образом:

$$j=\begin{cases}\arg\max_{u\in N_i^k(t)}\{\tau_{iu}(t)\eta_{iu}^{\beta}(t)\}},\mbox{если $r\le r_0$}\\J,\mbox{если $r>r_0$}\end{cases},$$

где $$r\sim U(0,1)$$, и $$r_0\in [0,1]$$ определяется пользователем и следующий узел $$j\in N_i^k(t)$$ выбирается случайным образом с вероятностью

$$p_{ij}^k(t)=\frac{\tau_{ij}(t)\eta_{ij}^{\beta}(t)}{\sum_{u\in N_i^k}\tau_{iu}(t)\eta_{iu}^{\beta}(t)},$$

где $$N_i^k(t)$$ множество доступных для посещения вершин. Это правило перехода отдает предпочтение коротким путям с большой концентрацией феромона. Параметр $$r_0$$ используется для регулирования баланса между эксплуатацией и расширением пространства поиска решений: при $$r\le r_0$$ алгоритм эксплуатирует пространство, выбирая лучший путь; в случае $$r> r_0$$ алгоритм расширяет пространство поиска. Отметим, что это правило совпадает с правилом перехода МС при $$r> r_0$$. Кроме этого, фактически в правиле коэффициент $$\alpha=1$$(не присутствует в (12.18)). В отличие от МС здесь концентрацию феромона разрешается изменять только лучшим (в глобальном смысле) муравьям, которые построили кратчайший путь $$x^+(t)$$, в соответствии со следующим правилом

$$\tau_{ij}(t+1)=(1-\rho_1)\tau_{ij}(t)+\rho_1\Delta\tau_{ij}(t),$$

где

$$\Delta\tau_{ij}(t)=\begin{cases}\frac{1}{f(x^+(t))},\mbox{если $(i,j)\in x^+(t)$}\\0,\mbox{если $(i,j)\notin x^+(t)$}\end{cases}$$

и $$f(x^+)(t)=|x^+(t)|$$ в случае построения кратчайшего пути.

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

В [7] реализовано два метода выбора пути $$x^+(t)$$:

лучшего на итерации, где $$x^+(t)$$ представляет лучший путь, найденный за текущую итерацию, который обозначается $$\tilde x(t)$$;

глобально лучшего, где $$x^+(t)$$ представляет лучший путь, найденный с первой по текущую итерацию, который обозначается $$\hat x(t)$$.

Испарение феромона в СМК тоже происходит по сравнению с МС по другим правилам. Согласно (12.19) для малых значений $$\rho_1$$ текущая концентрация на дугах происходит медленно и влияние построенного лучшего пути ослабляется. С другой стороны, для больших значений $$\rho_1$$ отложенный феромон испаряется быстро и влияние построенного лучшего пути усиливается. Это способствует расширению пространству поиска. Иногда значение $$\rho_1$$ позволяют изменяться в процессе поиска решения: на начальной стадии используются большие значения, а на конечной – малые.

В дополнение к глобальному изменению в СМК применяется локальная коррекция концентрации феромона в соответствии со следующим правилом:

$$\tau_{ij}(t)=(1-\rho_2)\tau_{ij}(t)+\rho_2\tau_0,$$

где $$\rho_2\in(0,1)$$ и $$\tau_0$$- малая положительная константа. Эксперименты при решении задачи коммивояжера показали [7], что значение $$\tau_0=(n_GL)^{-1}$$ дает хорошие результаты, где $$n_G$$- число узлов в графе и $$L$$ – длина тура, построенного с применением жадной эвристики.

Отметим, что в СМК также переопределяется $$N_i^k(t)$$ - множество доступных для посещения вершин, которое содержит списки вершин-кандидатов для посещения. Пусть $$n_l<|N_i^k(t)|$$ означает число узлов в списке кандидатов. Ближайшие (по расстоянию или стоимости) $$n_l$$ узлов к узлу $$i$$ включаются в список кандидатов согласно произведенному ранжированию. При выборе следующего узла выбирается лучший из списка кандидатов. Если список кандидатов пуст, то узел $$j$$ выбирается из остатка $$N_i^k(t)$$. В этом случае выбор может быть сделан на основе уравнения (12.18) или же взят ближайший узел $$j\in N_i^k(t)$$. В целом алгоритм СМК представлен псевдокодом А12.4 [4].

12.5 Максиминная муравьиная система

Данная модификация (макси-минная муравьиная система МММС - Max-MinAntSystem [8]) разработана для преодоления проблемы преждевременной стагнации. Ее основное отличие от МС в том, что интенсивность феромона ограничивается в некотором заданном интервале. Кроме этого, здесь изменять концентрацию феромона разрешается только лучшим муравьям, начальная концентрация феромона устанавливается в максимально допустимые значения и используется механизм сглаживания для концентрации феромона.

В МММС концентрация феромона изменяется, также как и в СМК, согласно уравнению (12.19), где $$\Delta\tau_{ij}(t)$$ вычисляется на основе либо глобально, либо лучшего на итерации пути. Первая версия МММС использовала при коррекции феромона лучший на текущей итерации путь $$\tilde x(t)$$, последние версии основаны на применении глобально лучшего пути $$\hat x(t)$$ с различными стратегиями:

Использование только глобально лучшего пути $$\hat x(t)$$ для определения концентрации $$\Delta\tau_{ij}(t)$$, что ускоряет процесс поиска, но с другой стороны сужает его.

Использование смешанных стратегий, где для коррекции концентрации феромона используются как $$\hat x(t)$$, так и $$\tilde x(t)$$. При этом для расширения пространства поиска, в основном, применяется лучший за текущую итерацию путь с периодическим подключением глобально лучший путь. Обычно частота использования последнего увеличивается в процессе поиска.

В случае стагнации все значения концентрации феромона $$\tau_{ij}$$ реинициализируются до допустимых максимальных значений, после чего допускается использовать только лучший за текущую итерацию путь ограниченное число итераций.

Для определения точки стагнации используется коэффициент $$\lambda$$-ветвления [9] со значением $$\lambda=0,05$$. При этом $$\lambda_i$$ определяется как число дуг, исходящих из узла $$i$$ со значением $$\tau_{ij}$$ больше чем $$\lambda\delta_i+\tau_{i,\min};\delta_i=\tau_{i,\max}-\tau_{i,\min}$$, где

$$\tau_{i,\min}=\substack{\min\{\tau_{ij}\}\\j\in N_i}$$ $$\tau_{i,\min}=\substack{\max\{\tau_{ij}\}\\j\in N_i}$$

и $$N_i$$- множество узлов, соединенных с узлом $$i$$. Если

$$\frac{\sum_{i\in V}\lambda_i}{n_G}<\varepsilon,$$

где $$\varepsilon$$- малое положительное значение, то предполагается, что наступила стагнация в процессе поиска.

В процессе поиска в МММС все значения концентрации феромона $$\tau_{ij}$$ ограничены в заданном диапазоне. В первой версии МММС $$\tau_{ij}\in[\tau_{\min},\tau_{\max}]$$ для всех дуг $$(i,j)$$, где границы диапазона $$\tau_{\min},\tau_{\max}]$$ постоянны и зависят от решаемой задачи. Если после коррекции концентрации феромона имеем $$\tau_{ij}(t+1)>\tau_{\max}$$, то полагаем $$\tau_{ij}(t+1)=\tau_{\max}$$. Аналогично при $$\tau_{ij}(t+1)<\tau_{\min}\ \tau_{ij}(t+1)=\tau_{\min}$$. Ограничение значений концентрации иногда позволяет избежать стагнации. В целом алгоритм представлен псевдокодом А12.5[4].

12.6 Q-муравьиная система

В [10] разработана модификация СМК (в современной классификации – Ant-Q), в которой правило локального изменения концентрации феромона реализовано на основе метода Q-обучения (Q-learning).

Пусть $$\mu_{ij}(t)$$ обозначает AQ-значение дуги $$(i,j)$$ в момент $$t$$. Тогда правило перехода для этой дуги определяется следующим образом

$$j=\begin{cases}\arg\max_{u\in N_i^k(t)}\{\mu_{iu}^{\alpha}(t)\eta_{iu}^{\beta}(t)\}},\mbox{если $r\le r_0$}\\J,\mbox{если $r>r_0$}\end{cases}.$$

Здесь коэффициенты $$\alpha,\beta$$ определяют важность AQ-величин $$\eta_{ij}$$ и эвристической информации . AQ-величины отражают предпочтительность перехода $$(i,j)$$. В уравнении (12.25) $$j$$ – случайная переменная, значение которой выбирается в соответствии с распределением, которое определяется функцией AQ-величин $$\mu_{ij}$$ и $$\eta_{ij}$$. Предложено три различных правила для выбора значения $$j$$:

псевдослучайный выбор, где следующая вершина $$j$$ случайным образом выбирается из множества $$N_i^k(t)$$ в соответствии с однородным распределением;

псевдослучайный пропорциональный выбор, где $$j\in V$$ выбирается в соответствии со следующим распределением

$$p_{ij}^k(t)=\begin{cases}\frac{\mu_{ij}^{\alpha}(t)\eta_{ij}^{\beta}(t)}{\sum_{u\in N_j^k}\mu_{ij}^{\alpha}(t)\eta_{ij}^{\beta}(t)},\mbox{если $j\in N_i^k(t)$}\\0,\mbox{если $j\notin N_i^k(t)$}\end{cases}.$$

случайный пропорциональный выбор соответственно (12.25) с $$r_0=0$$.В [10] отмечено, что псевдослучайный пропорциональный выбор лучше показал себя при решении задачи коммивояжера.

AQ-величины обучаются с использованием следующих правил коррекции:

$$\mu_{ij}(t+1)=(1-\rho)\mu_{ij}(t)+\rho\left(\Delta\mu_{ij}(t)+\substack{\gamma\max\{\mu_{iu}(t)\}\\u\in N_j^k(t)}\right),$$

где $$\rho$$-коэффициент переоценки (по аналогии с испарением феромона) и $$\gamma$$- шаг обучения. Отметим, что при $$\gamma=0$$ уравнение (12.27) сводится к уравнению (12.19) . В Ant-Q уравнение (12.27) применяется для каждого муравья после каждого нового выбора $$j$$, но с $$\Delta\mu_{ij}(t)=0$$. Эффект заключается в том, что AQ-величины, связанные с дугой $$(i,j)$$, уменьшаются путем умножения на $$(\rho-1)$$ каждый раз, когда дуга выбирается в потенциальное решение. В тоже время AQ-величина корректируется пропорционально AQ-величине лучшей дуги $$(i,j)$$.

12.7 Быстрая муравьиная система

Данная модификация (FastAntSystem [11]) первоначально разработана для решения квадратичной задачи о назначениях (quadratic assignment problem). В быстрой муравьиной системе (БМС) по сравнению с другими муравьиными алгоритмами используется популяция, состоящая из одного муравья, и другие правила коррекции феромона без испарения. Естественно, использование только одного муравья снижает вычислительную сложность алгоритма. В БМС применяется правило перехода (12.6) со значением коэффициента $$\beta=0$$(эвристическая информация не используется). Таким образом, правило коррекции концентрации феромона следующее:

$$\tau_{ij}(t+1)=\tau_{ij}(t)+w_1\Delta\tilde\tau_{ij}(t)+w_2\Delta\hat\tau_{ij}^+(t),$$

где коэффициенты $$w_1$$ и $$w_2$$ определяют относительный вклад текущего решения и лучшего глобального, которые вычисляются согласно

$$\Delta\tilde\tau_{ij}(t)=\begin{cases}1,\mbox{если $(i,j)\in\tilde x(t)$}\\0,\mbox{если $(i,j)\notin\tilde x(t)$}\end{cases}$$ $$\Delta\hat\tau_{ij}(t)=\begin{cases}1,\mbox{если $(i,j)\in\hat x(t)$}\\0,\mbox{если $(i,j)\notin\hat x(t)$}\end{cases}$$

Здесь, как и ранее, $$\tilde x(t)$$ и $$\hat x(t)$$ представляют соответственнонайденный лучший путь на итерации $$t$$ и лучший путь в глобальном смысле (с первой по $$t$$-ю итерацию). При инициализации $$\tau_}ij}(0)=0$$. Когда найдено новое решение $$\hat x(t)$$, производится переинициализация $$\tau_}ij}(0)=0$$.

12.8 Antabu

Эта модификация МС [12] включает локальный поиск с использованием tabu-поиска для улучшения решений, полученных на каждой итерации МС. Кроме этого, изменено глобальное правило пересчета концентрации феромона, где любой муравей откладывает феромон на каждой дуге пропорционально качеству пути согласно следующей формуле:

$$\tau_{ij}(t+1)=(1-\rho)\tau_{ij}(t)+(\frac{\rho}{f(x^k(t))})(\frac{f(x^-(t))-f(x^k(t))}{f(\hat x(t))}),$$

где $$f(x^-(t))$$- стоимость найденного худшего пути и $$f(\hat x(t))$$- стоимость лучшего пути, найденного $$k$$-м муравьем. Уравнение (12.31) применяется для каждого муравья $$k$$ и каждой дуги $$(i,j)\in x^k(t)$$.

12.9 Ранговая МС

Ранговая муравьиная система (РМС)[13] (в оригинале AS-rank) отличается следующими особенностями: 1) концентрацию феромона разрешается изменять только лучшему муравью на дугах глобально лучшего пути; 2) используются элитные муравьи; 3) муравьи изменяют концентрацию феромона на основе ранжирования в соответствии со следующим правилом:

$$\tau_{ij}(t+1)=(1-\rho)\tau_{ij}(t)+n_e\Delta\hat\tau_{ij}(t)+\Delta\tau_{ij}^r(t),$$

где

$$\Delta\hat\tau_{ij}(t)=\frac{Q}{f(\hat x(t))},$$

и $$\hat x(t)$$- лучший построенный путь.

Если используются $$n_e$$ элитных муравьев и $$n_k$$ муравьев ранжируются

$$f(x^1(t))\le f(x^2(t))\le\dots\le f(x^{n_k}(t)),$$

то

$$\Delta\tau_{ij}^r=\sum_{\sigma=1}^{n_e}\Delta\tau_{ij}^\sigma(t),$$

где

$$\Delta\tau_{ij}^{\sigma}(t)=\begin{cases}\frac{(n_e-\sigma)Q}{f(x^{\sigma}(t))},\mbox{если $(i,j)\in x^{\sigma}(t)$}\\0,\mbox{если $(i,j)\notin x^{\sigma}(t)$}\end{cases}$$

Здесь $$\sigma$$ указывает ранг (номерпо порядку) соответствующего муравья. Эта стратегия элитизма отличается от рассматривавшейся ранее в МС тем, что вклад элитного муравья в откладываемый феромон прямо пропорционален его рангу.

12.10 Муравьи (ANTS)

Данная модификация [14] отличается от МС следующими особенностями: 1) методом вычисления вероятности перехода; 2) глобальным правилом изменения концентрации феромона; 3) методом борьбы со стагнацией. Здесь вероятность перехода вычисляется в соответствии с уравнением (12.8). Как обычно, множество $$N_i^k$$ содержит все возможные переходы из узла $$i$$. Концентрация феромона корректируется после того как все муравьи построили свои пути в соответствии с уравнениями (12.5) и (12.17). Но при этом

$$\Delta\tau_{ij}^{\sigma}=\tau_0(1-\frac{f(x^k(t))-\varepsilon}{\overline f(t)\varepsilon}),$$

где $$f(x^k(t))$$ представляет стоимость соответствующего пути $$x^k(t)$$ $$k$$-го муравья на $$t$$-й итерации и $$\overline {f(t)}$$- средняя стоимость последних $$\hat n_t$$ глобально лучших решений, найденных алгоритмом. Если $$f(\hat x^k(t))$$ представляет стоимость глобально лучшего решения на итерации $$t$$, то

$$\overline f(t)\frac{\sum_{t'=t-\hat n_e}^tf(\hat x(t'))}{\hat n_t}.$$

В целом алгоритм ANTS представлен псевдокодом A12.6[4].

Если $$t<\hat n_t$$, то среднее вычисляется на множестве доступных $$t$$ лучших решений. В уравнении (12.36) $$\varepsilon$$- нижняя граница стоимости оптимального решения. Метод вычисления количества феромона, откладываемого каждым муравьем $$\Delta\tau_{ij}^k$$, часто позволяет избежать преждевременной стагнации.

12.11. Параметры муравьиных алгоритмов

Эффективность МА зависит от ряда управляющих параметров, к которым относятся: $$n_k$$- число искусственных муравьев; $$n_{t0}$$- максимальное число итераций, $$\tau_0$$- начальная концентрация феромона, $$\rho_1,\rho_2$$- устойчивость феромона(для ACS), $$\alpha$$- интенсификация феромона (для ACS $$\alpha=1$$), $$\beta$$- интенсификация эвристики. Далее мы рассмотрим эти параметры.

Число муравьев $$n_k$$ существенно влияет на характеристики МА – очевидно большое число $$n_k$$ ведет к большей вычислительной сложности. Чем больше муравьев используется, тем больше путей строится и откладывается больше феромона. Например, вычислительная сложность МС оценивается $$O(n_c,n_G^2,n_k)$$, где $$n_c=n_tn_k$$- общее число циклов, $$n_t$$- число итераций, $$n_G$$- число узлов в решениях (в предположении, что все решения имеют одинаковое число узлов).

Успешное применение МА обусловлено, прежде всего, совместным поведением множества муравьев. Благодаря откладываемому феромону, муравьи передают полученный опыт и знания. Чем меньше используется муравьев, тем слабее способность алгоритма к исследованию и следовательно меньше информации о пространстве поиска доступно другим муравьям. Малое число муравьев может вызвать преждевременную стагнацию или нахождение субоптимальных решений. Экспериментально показано, что при решении задачи коммивояжера число муравьев, соизмеримое с числом узлов графа $$n_k\approx n_G$$, дает хорошие результаты. Известны и более строгие оценки $$n_k$$[6], в которых вычисляется оптимальное число муравьев

$$n_k=\frac{\log(\phi_1-1)-\log(\phi_2-2)}{r_0\log(1-\rho_2)},$$

где $$\phi_1\tau_0$$- средняя концентрация феромона на дугах лучшего пути перед глобальной коррекцией и $$\phi_2\tau_0$$- концентрация после этой коррекции. К сожалению, оптимальные значения $$\phi_1,\phi_2$$ неизвестны. Экспериментальные исследования для задачи коммивояжера дают оптимальное соотношение $$(\phi_1-1)/(\phi_2-1)\approx 0.4$$, из которого следует $$n_k=10$$[8]. Следует подчеркнуть, что эти оценки получены только для определенного алгоритма, и в общем случае оптимальные значения $$n_k$$ могут быть различными для разных задач.

Максимальное число итераций $$n_t$$ играет важную роль для поиска качественных решений. При малом числе $$n_t$$ муравьям может не хватить времени для построения оптимального пути. С другой стороны, если $$n_t$$ слишком велико, будут произведены лишние вычисления.

Значения начальной концентрации $$\tau_0$$ также влияют на характеристики МА. При начальной инициализации дугам обычно присваивается либо малое постоянное положительное значение $$\tau_0$$, либо малое случайное значение их диапазона $$[0,\tau_0]$$. Большое значение $$\tau_0$$ в случае случайного выбора может давать большие отличия в начальной концентрации, что может привести к начальному выбору неперспективного решения.

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

12.12 Решение задач в динамической среде

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

Например, при определении вероятности перехода в системе муравьиных колоний (ACS) согласно (12.18) выбор малых значений $$r_0$$ и увеличение $$\beta$$ усиливают способности алгоритма к расширению пространства поиска, что необходимо при решении подобных задач. Это больше способствует выбору случайных решений, где новая измененная эвристическая информация учитывает изменяющееся окружение.

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

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

В [15] предложено восстанавливать решение при изменении среды. Это можно сделать с помощью локальных процедур поиска для всех решений. Компоненты, подвергшиеся изменению, устраняются из решения (дуга графа удаляется из пути, а вершина-предшественник соединяется с вершиной- последователем). Вместо удаленных компонент вносятся другие дуги,неиспользованные в решении, обычно выбираемые на основе жадных алгоритмов.

При альтернативном подходе при обнаружении окружения следует изменить правила коррекции феромона так, чтобы они способствовали расширению пространства поиска. Например, в [16] в таких ситуациях изменяются как локальные, так и глобальные правила. Локальное правило коррекции изменяется следующим образом:

$$\tau_{ij}(t+1)=(1-\rho_1(\tau_{ij}(t))\tau_{ij}(t)+\Delta\tau_{ij}(t),$$

где $$\rho_1(\tau_{ij})$$- монотонно возрастающая функция $$\tau_{ij}$$, например,

$$\rho_1(\tau_{ij})=\frac{1}{1+e^{-\tau_{ij}+\theta}}$$

с $$\theta>0$$

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

Глобальная коррекция выполняется аналогично, только относительно глобально лучшего и глобально худшего решений

$$\tau_{ij}(t+1)=(1-\rho_2(\tau_{ij}(t)))\tau_{ij}(t)+\gamma_{ij}\Delta\tau_{ij}(t),$$

где

$$\gamma_{ij}=\begin{cases}+1,\mbox{если $(i,j)$-глобально лучшее решение,}\\-1,\mbox{если $(i,j)$-глобально худнее решение,}\\0,\mbox{иначе}\end{cases}.$$

В работе [3] предложено три основных правила коррекции феромона при изменении среды, целью которых является поиск оптимального баланса между изменением ("сбросом") достаточно большого фрагмента информации для расширения пространства поиска и сохранения достаточной информации о полученных результатах для ускорения процесса поиска. Для каждой из этих стратегий по-разному вычисляется коэффициент "сброса" $$\gamma\in[0,1]$$ и используется следующее правило реинициализации феромона

$$\tau_{ij}(t+1)=(1-\gamma_i)\tau_{ij}+\gamma_i\frac{1}{n_G-1},$$

где $$n_G$$- число узлов в графе. При вычислении коэффициента сброса $$\gamma_i$$, как было сказано выше, предложены три различные стратегии:

стратегия рестарта, для которой

$$\gamma_i=\lambda_K$$

где $$\lambda_K\in[0,1]$$- параметр этой стратегии. Отметим, что данная стратегия не учитывает информацию о месте изменения среды.

$$\eta$$-стратегия, при которой используется эвристическая информация $$(d_{ij})$$

$$\gamma_i=\max\{0,d_{ij}^n\},$$

где

$$d_{ij}^n=1-\frac{\overline n}{\lambda_{\eta}\eta_{ij}},\lambda_{\eta}\in[0,\infty)$$

и

$$\overline{\eta}=\frac{1}{n_G(n_G-1)}\sum_{i=1}^{n_G}\sum_{j=1,j\ne i,\eta_{ij}}.$$

Здесь $$\gamma_i$$ пропорционально расстоянию от изменившегося компонента и выравнивание концентрации феромона выполняется для дуг, которые инцидентны изменившийся компоненте.

$$\tau$$-стратегия, где выравнивание концентрации для ближних (к изменению среды) компонент больше, чем для дальних:

$$\gamma_i=\min\{1,\lambda_{\tau}d_{ij}^{\tau}\},\lambda_{\eta}\in[0,\infty),$$

где

$$d_{ij}^{\tau}=\max_{n_{ij}}\{\prod_{(x,y)\in N_{ij}}\frac{\tau_{xy}}{\tau{\max}}\}$$

и $$N_{ij}$$- множество всех путей от $$i$$ до $$j$$.

12.13 Применение муравьиных алгоритмов

Муравьиные алгоритмы использовались при решении многих реальных задач, прежде всего задач комбинаторной оптимизации, из которых самой "популярной" является задача коммивояжера. Для того чтобы разработать муравьиный алгоритм для решения конкретной задачи, необходимо:

Соответствующее представление в виде графа для описания дискретного пространства поиска. Граф должен представлять все состояния и переходы между ними. Необходима также схема представления потенциального решения.

Определить правила коррекции концентрации феромона, которые определяют положительную обратную связь в процессе.

При необходимости разработать эвристику для определения предпочтительности дуги в графе.

Определить эвристику поведения муравья при построении решения в виде вероятности перехода.

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

Определить основные параметры МА (число искусственных муравьев и т.п.).

Далее рассмотрим использование МА на примере задачи коммивояжера, на которой впервые были апробированы МА. Напомним, что формальная постановка этой задачи изложена в разделе 3. Здесь мы имеем естественное представление задачи в виде графа $$G=(V,E,D)$$, где $$V$$ –множество вершин, каждая из которых представляет город, множество дуг графа $$E$$ представляет связи между городами и $$D$$- матрица расстояний, где каждой дуге $$(i,j)\in E$$ приписывается вес $$d_{ij}$$.

Предпочтительность выбора вершины $$j$$ после $$i$$ в данном случае естественно определить как $$\eta_{ij}=\frac{1}{d_{ij}(t)}$$, где время $$t$$ существенно только для задач с изменяющимся окружением.

Решение задачи должно удовлетворять двум ограничениям: 1) все города должны быть посещены, 2) каждый город разрешается посещать только один раз. Для проверки второго ограничения часто используется tabu-список для каждого потенциального решения, где содержатся посещенные города. Пусть $$\gamma^k$$ обозначает tabu-список для $$k$$-го муравья (потенциального решения). Тогда $$N_i^k(t)=v/\gamma^k(t)$$- множество непосещенных городов после достижения города $$i$$.

При решении задачи каждое потенциальное решение представляется искусственным муравьем. При инициализации муравьи располагаются на городах случайным образом и далее каждый муравей строит свое решение путем выбора в текущей вершине $$i$$ следующей вершины $$j$$, используя вероятность перехода в соответствии с одним из представленных выше вариантов МА.

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

В настоящее время муравьиные алгоритмы получили применение при решении следующих практических задач [3]:

маршрутизация (прежде всего, в сетях – networkrooting);

задачиназначения (quadratic assignment problem, graph coloring, generalized assignment, frequentially assignment);

машинноеобучение (classification rules, Bayesian networks, fuzzy systems);

кластеризация данных;

роботика (vehiclerouting и др. );

календарноепланированиеисоставлениерасписания( job shop, open shop, flow shop, total terdiness, project sheduling, group shop);

покрытиемножества, задачаобукладкерюкзака(multi-knapsack, max independent set, reduncy allocation, set covering, maximum clique, weight constrained graph tree partition, bin packing);

биоинформатика;

обработка текстов.

Этот список можно продолжить, поскольку число публикаций с использованием МА последние десять лет быстро растет.

Контрольные вопросы

Опишите эксперимент с двумя мостами.

Как представляется потенциальное решение задачи в МА?

Что отражает и как определяется концентрация феромона в простом МА?

Зачем нужно и как определяется испарение феромона в простом МА?

Опишите простой МА.

Объясните влияние параметров $$\alpha,\beta$$ в правиле выбора следующей вершины (12.2).

Как оценивается качество построенного решения в МА?

Какие критерии окончания могут быть использованы в простом МА?

Чем отличается метод "муравьиная система" от простого МА?

Какие модификации МС вам известны?

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

Что такое глобальное и локальное правило коррекции в СМК?

Что такое глобально лучший путь и лучший на текущей итерации путь в максиминной муравьиной систем?

Чем отличается Q-муравьиная система от "системы муравьиных колоний"?

Для решения какой задачи была разработана "быстрая муравьиная система"?

Опишите модификацию Antabu.

Каковы особенности у ранговой муравьиной системы?

Опишите модификацию ANTS.

Опишите основные параметры МА.

Чем отличаются задачи в изменяющейся среде от стационарных?

Какие стратегии решения задач с изменяющейся средой вы знаете?

Какие области применения МА при решении практических задач вы знаете?

В чем сходство и различие между муравьиными и эволюционными алгоритмами?

Краткие итоги:

изложены основыметода муравьиных колоний, который основан на моделирования стигметрии – обмена информацией между особями популяции путем откладывания специального фермента - феромона;

описан базовый муравьиный алгоритм и его применение к решению задачи коммивояжера;

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

описаны различные виды фитнесс-функций, применямых в МА;

рассмотрено решения задач в изменяющейся среде на основе муравьиных алгоритм;

выполнено сравнение метода муравьиных колоний и эволюционных методов, рассмотрены их сходство и различие.