Общая структура представления решений в алгоритмах разбиения на основе роевого интеллекта и генетического поиска

В эвристических алгоритмах роевого интеллекта многомерное пространство поиска населяется роем частиц [7]. Каждая частица представляет некоторое решение. В нашем случае решение задачи разбиения. Процесс поиска решений заключается в последовательном перемещении частиц в пространство поиска. Обозначим позицию частицы i в пространстве решений в момент времени t (t имеет дискретные значения) как xi (t). По аналогии с эволюционными стратегиями, рой можно трактовать как популяцию, а частицу как индивида (хромосому). Это дает возможность построения гибридной структуры поиска решения, основанную на сочетании генетического поиска с методами роевого интеллекта. Связующим звеном такого подхода является структура данных, описывающая в виде хромосомы решение задачи. Если в качестве частицы используется хромосома, то число параметров, определяющих положение частицы в пространстве решений должно быть равно числу генов в хромосоме. Значение каждого гена откладывается на соответствующей оси пространства решений. В этом случае возникают некоторые требования к структуре хромосомы и значениям генов. Значения генов могут быть непрерывными или дискретными. Значения генов должны быть независимыми друг от друга, то есть хромосомы должны быть гомологичными.

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

Будем решение задачи разбиения представлять в виде вектора P={pi | i=1,2,…, n}. Значением pi — является номер некоторой вершины, причем (ij)[pi? pj]. Элементы pi для которых 1 i n1, соответствуют первому узлу Х 1. Элементы pi для которых n1+1 i n1+n2 соответствуют второму узлу Х 2 и т. д. В общем случае для элементов pi справедливо:

(i)[(1+dj i dj + nj) (pi Xj)], j=1,2,…, k,

где dj = () —nl.

Таким образом, разбиение определяется перестановкой элементов pi в векторе P.

Хромосома, соответствующая решению Р, состоит из генов, число которых на единицу меньше числа n элементов в векторе P: H={gl | l=1,2,…,(n-1)}. Решение Р получается путем применения к хромосоме рекурсивной процедуры декодирования.

Ген gl может принимать значения, лежащие в интервале 1 gl n-l+1, т. е. чем больше порядковый номер t, тем меньшее значение он может принять. Декодирование хромосомы выполняется последовательно, начиная с первого гена g1. На шаге l декодируется ген gl. В результате декодирования гена gl определяется номер элемента, помещаемого в позицию l. Для декодирования хромосомы используется опорный вектор номеров элементов B1={bi1 | i=1,2,…, n}. После декодирования очередного гена gl вектор Bl уменьшается, путем удаления из него номера элемента, определенного при декодировании gl.

Пусть на шаге l (l=1,2,…,(n-1)) декодируется ген gl. К моменту декодирования gl, получен вектор Bl={bil | i=1,2,…, (n-t+1)}, путем удаления l-1 элемента из B1 на предыдущих шагах. Определяется значение z гена gl, т. е. z=gl. В векторе Bl определяется номер bzl очередного элемента, который помещается в позицию l, т. е. pl присваивается значение bzl, (pl=bil). После этого формируется вектор Bl+1, для этого из Bl удаляется элемент bzl.

Связь между элементами bil+1 и bil определяется с помощью следующих выражений:

bil+1= bil, i=1,2,…,(z-1), z=gl; bz+j-1l+1=bz+jl, j=1,2,…((n-l+1)-z).

На шаге n вектор Bn состоит из одного элемента b1n, поэтому pn=b1n.

Рассмотрим метод декодирования на примере. Пусть имеется хромосома H= и опорный вектор B1= (рис. 1).

На первом шаге рассматриваем ген g1. i=g1=5. Отсюда p1=bi1=b51=4. Элемент b51 удаляется из B1 и получается B2=. На втором шаге рассматривается ген g2. Отсюда i=g2=2. Тогда p2=b22=3. Элемент b22 удаляется из B2 и получается B3=. На третьем шаге рассматриваем ген g3. i=g3=3. Тогда p3=b33=5. Элемент b33 удаляется из B3 и получается B4=. На четвертом шаге рассматривается ген g4. i=g4=2. Отсюда p4=b24=1. Удаляем b24 из B4 и получаем B5=. Так как b15 является единственным элементом в векторе B5, то p5=b15=2. Таким образом, построенный вектор P имеет вид: P=.

Трудоемкость декодирования хромосом имеет оценку O (n).