4479-1 (662818), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Затем для каждого 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 определяется следующим образом

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

,

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

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

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

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

трассировки

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

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

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

Значения растут последовательно и, после просмотра всех генов, b_l является значением числа цепей, проходящих через u_l.

Имея вектора А и В, рассчитываются значения показателей c_l=a_l-b_l для каждого ребра u_l. На основании значений c_l расcчитываются критерии F₁, F₂ и F₃.

Если учесть, что число вариантов имеет фиксированное значение и обычно, не превышает 4-6, то трудоемкость подсчета вектора В линейна и пропорциональна длине хромосом. Трудоемкость процедуры поиска c_min также линейна. В связи с этим трудоемкость t_ф расчета фитнесса для одной хромосомы имеет линейную зависимость от длины хромосомы t_фO(L).

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

Селекция родительских пар хромосом осуществляется либо на основе «принципа рулетки», либо на основе рейтинга популяции.

С этой целью все хромосомы популяции сортируются в соответствии с рассчитанными значениями фитнесса. После этого осуществляется селекция пары родственных хромосом по правилу: i - я с i+1 – ой.

Для каждой новой индивидуальности, образованной в результате кроссинговера, расчитывается фитнесс. После кроссинговера текущая популяция П_Т включает исходную П_И и популяцию П_К , образовавшуюся в результате выполнения кроссинговера.

П_Т=П_И+П_К.

Далее ко всем индивидуальнастям П_Т применяется оператор мутации. Для всех индивидуальностей популяции П_М , образовавшихся в результате мутации расчитывается фитнесс. Заключительным этапом в пределах одного поколения является процесс редукции популяции П_Т=П_И+П_К+П_М до размеров П_И на основе селективного отбора. Селекция осуществляется на основе “принципа рулетки”.

Вероятность выбора индивидуальности определяется как:

С помощью коэффициентов К_i, которые для «лучших» индивидуальностей имеют большие значения, чем у «худших», достигаются увеличение вероятности выбора «лучших» индивидуальностей.

Временная сложность алгоритма определяется общими (подготовительными) затратами to и затратами в пределах каждого поколения td . Общие затраты складываются из затрат на построении минимальных связывающих деревьев td ,формирование вариантов реализации ребер tb ,и формирования исходной популяции tи: to=td+tb+tи.

Затраты на построение МСД находятся в зависимости от числа МСД. С другой стороны при построении конкретного МСД затраты пропорциональны квадрату числа связываемых вершин . Учитывая , что число ребер n всех МСД пропорционально числу МСД , можно считать, что оценка ВСА t_о лежит в пределах О(n)-O(n²), причем чем больше n тем ближе к О(n).

Затраты в пределах поколения tn складываются из затрат на операторы кроссинговера tк , мутации tm ,расчета фитнесса tф и селекции tс .

Как уже указывалось выше затраты tк ,tм и tф при обработке одной хромосомы имеют линейную зависимость от n . tс имеет линейную зависимость от объема популяции М . Тогда временные затраты в пределах поколения имеют оценку О(nM). Для Т генераций временная сложность алгоритма имеет оценку О(nMT) . Учитывая что параметры М и Т сравнимы или значительно меньше n, можно считать , что оценка временной сложности всего алгоритма в целом лежит в пределах О(n²)-O(n³).

4. Экспериментальные исследования генетического алгоритма глобальной трассировки

Алгоритм глобальной трассировки был реализован на языке С++, экспериментальные исследования проводились на ЭВМ типа IBM PC/AT Pentium 133.

При проведении экспериментальных исследований преследовались две цели:

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

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

Для проведения исследований были синтезированы 5 тестовых примеров.

Основные характеристики примеров.

Использовалось КП с размерами 10*10 (10 дискретов по горизонтали и 10 дискретов по вертикали). Выводы, связываемые цепями, размещались внутри дискретов. В каждом дискрете только один вывод одной цепи. Число выводов, связываемых одной цепью - от 2 до 5. В один дискрет назначалось до 10 выводов. Среднее число цепей - 200 -250. Назначение выводов в дискреты осуществлялось случайным образом.

Оптимизация проводилась по критерию:

F₁= (_i)[C_minC_i=_i-_i]

Если оказывалось, что С_min0, то оптимизация автоматически переключалась на критерий F₂ = m - , где - число ребер, проходящих через грани с отрицательным значением С_min.

Для нахождения наилучшего сочетания таких параметров, как Р_м, Р_к, М и Т, а также для выбора последовательности и типа генетических операторов экспериментальные исследования проводились следующим образом:

Для каждого примера сначала фиксировался параметр Р_м и изменялись параметры Р_к и М. Проводилась серия из десяти экспериментов для каждого фиксированного набора параметров. Затем фиксировался параметр Р_к. Формирование исходной популяции осуществлялось следующим образом. Для каждой цепи строилось МСД. Если в процессе его построения возможно несколько альтернатив, то выбиралась первая. Для каждого ребра каждого дерева формировался набор вариантов маршрутов. Для каждой хромосомы исходной популяции выбор вариантов осуществлялся случайным образом.

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

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

Характеристики

Список файлов реферата