Механизмы разбиения на основе муравьиной колонии

Пусть дан граф G (X, U), где Х — множество вершин, |X| = n, U — множество ребер. Необходимо разбить множество X на два непустых и непересекающихся подмножества X1 и X2, X1X2 =X, X1 X2=, Xi. На формируемые узлы (блоки, компоненты) накладываются ограничения: |X1| = n1, |X2| = n2, n1 + n2= n. Критерий оптимизации число связей — F между X1 и X2. Цель оптимизации минимизация критерия F.

Для поиска решения задачи используется полный граф решений R (X, E), где E — множество всех ребер полного графа, связывающих множество вершин X. На множестве ребер E будем откладывать феромон. На начальном этапе на всех ребрах графа R откладывается одинаковое (небольшое) количество феромона Q/m, где m=|E|. Каждый из агентов формирует множество X1k, где k — номер агента. Формирование множества X1k осуществляется последовательно (пошагово). На каждом шаге t у k-ого агента есть список вершин, уже включенных в формируемое множество — X1k (t) и список оставшихся (свободных) вершин Xсk (t), X1k (t)Xсk (t)=X. На первом шаге в каждое формируемое множество X1k (t), где t = 1, включается вершина графа G, причем вершины графа G распределяются по узлам равномерно, то есть в каждом узле своя вершина, ( i, j) [X1i (1)X1j (1)=]. Такое распределение необходимо, чтобы все вершины графа G имели одинаковые шансы быть отправной точкой при формировании узла X1. В модификациях алгоритма использовались также ln муравьев, причем каждая группа из l муравьев используют в качестве начального одно и то же X1i (1).На конечном шаге t=n1 k-м агентом будет сформирован узел X1k (n1)=X1k. |X1(n1)| = n1.

Моделирование поведения муравьёв в задаче разбиения связано с распределением феромона на ребрах графа R. При этом вероятность включения вершины xjG в формируемое отдельным муравьем множество X1k (t), пропорциональна суммарному количеству феромона на ребрах, связывающих вершину xj с X1k (t). Количество откладываемого феромона пропорционально числу связей между сформированными узлами. Чем меньше число связей между X1k и X2k, тем больше феромона будет отложено на рёбрах полного подграфа R1к R, построенного на вершинах узла X1k следовательно, большее количество муравьёв будет включать вершины узла X1k в синтез собственных узлов. Для избегания преждевременной сходимости используется отрицательная обратная связь в виде испарения феромона. Процесс поиска решений итерационный. Каждая итерация t включает три этапа. На первом этапе муравей находит решение, на втором этапе откладывает феромон, на третьем этапе осуществляется испарения феромона. В работе используется циклический (ant-cycle) метод муравьиных систем. В этом случае ферромоны откладываются агентом на ребрах после полного формирования решения.

На первом этапе каждой итерации каждый k-ый муравей формирует свое собственное множество X1k. Процесс построения множество X1k пошаговый. На каждом шаге агент применяет вероятностное правило выбора следующей вершины для включения ее формируемое множество X1k (t).

Первый этап осуществляется следующим образом. Агент просматривает все свободные на данном шаге вершины Xсk (t). Для каждой вершины xi Xсk (t) рассчитываются два параметра:

fik — суммарный уровень феромона на ребрах графа R, связывающих xi с вершинами узла X1k (t);

sik — число связей на графе G между xi и X1k (t).

По формуле (1) — при мультипликативной свертке, либо по формуле (2) — при аддитивной свертке определяется потенциальная стоимость Fik связей xi с Xсk (t). итеративный разбиение муравьиный связь.

Fik=(fik)б· (sik+1)в

Fik=(fik)б+(sik)в

где б, в — управляющие параметры, которые подбираются экспериментально.

Вероятность Pik включения вершины xi Xсk (t) в формируемый узел X1k (t) определяется следующим соотношением.

Pik=Fik/

Агент с вероятностью Pik выбирает одну из вершин, которая включается в множество X1k (t) и исключается из множества Xсk (t).

При б = 0 наиболее вероятен выбор вершины xi максимально связанной с вершинами узла X1k (t), то есть алгоритм становится жадным.

При в = 0 выбор происходит только на основании феромона, что приводит к субоптимальным решениям.

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

После формирования за n1 шагов муравьями узлов (каждый муравей — свой узел X1k), на втором этапе итерации, каждый муравей откладывает феромон на рёбрах полного подграфа R1кR, построенного на вершинах узла X1k.

Количество феромона фk (l), откладываемое k-ым муравьем на каждом ребре подграфа R1к R, построенного на l-ой итерации, определяется следующим образом:

фk (l)= Q /Dk (l),.

где l-номер итерации, Q — общее количество феромона, откладываемое k-ым муравьем на ребрах подграфа R1к R, Dk (l) — число связей на графе G между множествами X1k и X2k, сформированными k-ым муравьем на l-ой итерации. (Другими словами, целевая функция для данного решения.).

После того, как каждый агент сформировал решение и отложил феромон, на третьем этапе происходит общее испарение феромона на ребрах полного графа R в соответствии с формулой (5).

fik = fik (1- с),

где с-коэффициент обновления (0.93−0.99).

После выполнения всех действий на итерации находится агент с лучшим решением, которое запоминается. Далее осуществляется переход на следующую итерацию. Временная сложность этого алгоритма зависит от времени жизни колонии l (число итераций), количества вершин графа n и числа муравьев m, и определяется как O (l*n2*m).