Механизмы адаптации при разбиении

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

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

Общая схема многошагового процесса перераспределения вершин между узлами заключается в следующем. На каждом шаге в узлах X1 и X2 выделяется для перераспределения подмножества вершин X*1 X1 и X*2 X2. Остаточное множество вершин объединяется в одну вершину x01 =X1 X*1, x02 =X2 X*2. В новой постановке исходная задача разбиения множества X рассматривается как задача распределения множества X*=X*1X*2 между узлами X1 и X2, причем изначально в узел X1 включена вершина x01, а в узел X2 включена вершина x02. Задача в новой постановке решается с помощью рассмотренного выше муравьиного алгоритма разбиения. Поскольку X*, как правило, значительно меньше X использование муравьиного алгоритма для формирования узла X1 будет гораздо дешевле. Выделение на каждом шаге в узлах X1 и X2 для перераспределения подмножества вершин X*1 и X*2 осуществляется с помощью адаптивной системы, основанной на идеях коллективного поведения объектов адаптации. В качестве элементарного объекта адаптации рассматривается вершина xiX. Коллектив объектов адаптации (их совокупность) соответствует объекту оптимизации (ОО).

Пусть сi+ — число ребер, связывающих xi Xv с вершинами xj Xv, xi xj, а сi- — число ребер, связывающих xi Xv с вершинами xj Xv. i = сi+ + сi-, где i — локальная степень вершины xi.

Локальная цель объекта адаптации xi — достижение такого состояния (т.е. такого распределения xi), при котором его оценка сi- =0. Глобальная цель коллектива объектов адаптации заключается в достижении такого состояния S (т.е. такого распределения вершин по узлам), при котором F (S) min.

Для реализации механизма адаптации каждому объекту xiX сопоставляется автомат адаптации ai, моделирующий поведение объекта адаптации в среде [10]. Автомат адаптации имеет две группы состояний: C1={c1i | i=1,2,…, g} и C2={c2i | i=1,2,…, g}, соответствующие двум альтернативам А1 и А2 поведения объекта адаптации в среде. Здесь А1 — остаться в том же узле и войти в состав соответствующей объединенной вершины x0v, А2 — войти в состав подмножества X*v для перераспределения. Таким образом выходной алфавит автомата А={А1,А2}.

Рис. 1. Граф — схема переходов АА

Входной алфавит Q={+,-} включает возможные отклики среды — «поощрение» (+) и «наказание» (-). Граф-схема переходов АА представлена на на рис. 1.

Отклик среды для АА ai в соответствии с состоянием среды и объекта адаптации формируется следующим образом.

Если сi- > сi+, то всегда вырабатывается сигнал «наказание» (-).

Если сi-? сi+, то с вероятностью Pн = сi- / (сi+ + сi-) вырабатывается сигнал «наказание» (-), а c вероятностью Pп=1-Pн вырабатывается сигнал «поощрение» (+).

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

На первом такте для каждого xi рассчитываются параметры сi- и сi+.

На втором такте для каждого автомата адаптации ai=Г (xi) вырабатывается отклик среды qi: «поощрение» или «наказание».

На третьем такте в каждом автомате адаптации ai под действием подаваемого на его вход отклика qi осуществляется переход в новое состояние.

На четвертом такте для каждого объекта адаптации xi реализуется альтернатива в соответствии с выходами АА. Другими словами, в соответствии с выходом АА вершина xi, либо входит в состав соответствующей объединенной вершины x0v, либо входит в состав подмножества X*v.

К обновленному множеству вершин X* применяется муравьиный алгоритм. Объект оптимизации, после реализации альтернатив и работы муравьиного алгоритма переходит в новое состояние, для которого рассчитывается показатель F (S). Состояние с лучшим значением F (S) запоминается.