Реферат: Генетический алгоритм глобальной трассировки

Управляемыми параметрами при формировании популяции является М - размер популяции, 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 всеми цепями.