Генетический алгоритм глобальной трассировки (стр. 2 из 3)

Ребро г₃₁ (то есть первое ребро МСД для цепи 3) имеет три варианта прохождения маршрута, r₃₁ = {v₃₁₁, v₃₁₂, v₃₁₃}, v₃₁₁={x₅,x₁₀,x₉,x₁₄}; v₃₁₂={x₅,x₄,x₉,x₁₄}; v₃₁₃={x₅,x₁₀,x₁₅,x₁₄}.

Для решения представленного на рис. 2. структура хромосомы имеет вид рис. 5

Рис. 5

Число генов равно 5. Гены g₁ и g₂ соответствуют ребрам r₁₁ иr₁₂ дерева D₁; g₃ и g₄ соответствуют ребрам r₂₁ иr₂₂ дерева D₂; g₅ соответствует ребру r₃₁ дерева D₃. Значение g₁ равно 2, т.к. для реализации r₁₁ выбран вариант V₁₁₂. g₂ равно 1, т.к. r₁₂ реализован вариантом V₁₂₁. Аналогично, т.к. r₂₁,r₂₂ и r₃₁ реализованы соответственно вариантами V₂₁₁, V₂₂₁ и V₃₁₃, то g₃=1, g₄=1, g₅=3.

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

Пусть L – число всех ребер всех МСД. L= число выводов – число цепей. Тогда объем V₁ ОЗУ, необходимой для хранения информации об вариантах реализации ребер МСД, будет

, где n_v – число вариантов реализации одного ребра.

Объем V₂ ОЗУ необходимый для одной хромосомы

. К₂ помимо всего прочего учитывает необходимость хранения фитнесса хромосомы.

Для популяции состоящей из М хромосом

.

Таким образом, общий объем памяти

имеет линейную зависимость и при заданных параметрах n_v и M пространственная сложность алгоритма ~O(L).

3.2 Формирование исходной популяции

Для организации генетического поиска формируется исходная популяция особей P={H_i|i=1,2,..,M}, где М размер популяции. Популяция Р- представляет собой репродукционную группу – совокупность индивидуальностей, любые две из которых H_iÎP и H_jÎP, i¹j могут размножаться выступая в роли «родителей». Предварительно с помощью процедуры FORM осуществляется разбиение КП на области и формирование модели КП в виде графа W=(X,U). Далее для каждой цепи t_iÎ Т строится алгоритмом Прима один из вариантов минимального связывающего дерева D_i={r_i, l_i=1, … n_i}

Затем для каждого r_ij синтезируется набор V_ij вариантов маршрутов в ортогональном графе G, реализующих ребро r_ij. Пусть n_ij=| V_ij |- число вариантов реализации ребра r_ij.

Определяется длина L хромосомы, являющейся носителем информации о конкретном решении:

Параметр L определяет число генов в хромосоме. С помощью графика соответствия Q устанавливается соответствие Г(G, Q, R) между генами хромосомы и ребрами минимальных связывающих деревьев для всех цепей.

G={g_n| n=1, 2,… ,L}; R={r_ij| i=1, 2, … ,n_i, j=1,2, … n_i}

Образом Г(r_ij) является ген g_n. Прообразом Г^-1(g_n) является ребро r_ij Значением гена g_n, будет номер варианта реализации ребра r_ij=Г^-1(g_n) .

Ген g_n может принимать любое значение от 1 до n_ij.

В работе используется принцип случайного формирования исходной популяции.

Для этого в пределах каждой хромосомы Н_к каждый ген g_n принимает случайное значение в пределах от 1 до n_ij , где n_ijчисло вариантов реализации ребра r_ij=Г^-1(g_n).

Управляемыми параметрами при формировании популяции является М - размер популяции, n_max - максимальное число вариантов реализации ребер, т.е. ("ij) [n_ij

n_max]. Если возможное число вариантов n_ij больше n_max то возникает возможность формирования альтернативных наборов вариантов V_ij для r_ij. Кроме того существует возможность построения альтернативных МСД D_i для одной и той же цепи t_i.

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

В простейшем случае это можно реализовать с помощью повторной, случайной генерации.

3.3 Генетические операторы

Для получения нового решения (индивидуальности) используются генетические операторы: кроссинговер и мутация.

Кроссинговер заключается во взаимном обмене генами между «родителями» - хромосомами предварительно выбранной пары.

В нашем случае все хромосомы гомологичны, т.к. имеют одну и ту же структуру, одну и ту же длину и несут информацию об одном и том же наборе МСД. Гены, расположенные в одном и том же локусе хромосом, гомологичны, т.к. несут информацию об одном и том же ребре хромосомы.

Предварительно задается величина P_K – вероятность кроссинговера и вводится флажок FG с двумя состояниями «выполнять», «не выполнять». Исходное состояние FG «не выполнять». При выполнении кроссинговера последовательно просматриваются локусы выбранной пары хромосом. С вероятностью P_k «флажок» FG переходит в состояние «выполнять». Если FG перешел в состояние «выполнять», то производится обмен генами между парой хромосом в текущем локусе, далее «флажок» переходит в состояние «не выполнять», а затем осуществляется переход к следующему локусу.

Такой алгоритм кроссинговера обеспечивает мультиобмен. Число пар обменивающихся генов определяется параметром P_k.

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

Предварительно, для каждого гена g_n, определяется диапазон его возможных значений от 1 до y_n, где y_n – число сформированных вариантов реализации ребра

.

Задается параметр P_M – вероятность мутации и «флажок» FG с двумя состояниями «выполнять» и «не выполнять». Исходное состояние FG – «не выполнять».

Последовательно выбираются хромосомы из текущей популяции. В пределах выбранной хромосомы последовательно просматриваются гены. После перехода к очередному гену, FG с вероятностью P_M переходит в состояние «выполнять». Если FG перешел в состояние «выполнять», то случайным образом ген g_n принимает одно из значений в заданном диапазоне, за исключением значения, которое ген имеет перед мутацией. Далее FG переходит в состояние «не выполнять» и выбирается следующий ген хромосомы, или следующая хромосома.

Для улучшения процесса поиска лучшего решения введем дифференцируемое значение показателя

, принимающего различные значения в зависимости от значения гена.

Введем для гена g_n оценку

, где l_n – число ребер u_i, входящих в маршрут v_ijk реализующий ребро , соответствующее гену g_n. - число таких u_i,, входящих в v_ijk ,для которых показатель загрузки c_i имеет отрицательное значение.

К_n меняется от 0 до 1. Чем больше K_n, тем “хуже” маршрут v_ijk, и тем больше оснований к его смене.

Значение показателя

с учетом К_n для гена g_n определяется следующим образом

параметр D связан с P_m следующим соотношением

,

т.е. D меняется от 0 до (1-P_m).

В предельном случае

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

, где L – длина хромосомы.

3.4 Общая структура генетического поиска для глобальной

трассировки

В соответствии с методикой описанной выше на первых подготовительных этапах осуществляется разбиение КП на плоскости. Для всех цепей строятся минимальные связывающие деревья. Для всех ребер МСД формируются наборы вариантов реализующих их соединений. Управляющими параметрами генетической адаптации являются: М – размер исходной популяции, Т – число генераций, P_K – вероятность кроссинговера, P_m – вероятность мутации.

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

Алгоритм расчета фитнесса имеет следующий вид: в качестве исходных данных используется вектор А={a_l| l=1,2, …}, где a_l – пропускная способность ребра u_l. Для расчета фитнесса используется вектор B, имеющий ту же размерность, что и вектор А. Вначале элементы

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