Предыдущая страница реферата | 1  2  3  4  5 | Следующая страница реферата

Введем для гена gn оценку , где ln – число ребер ui, входящих в маршрут vijk реализующий ребро , соответствующее гену gn.  - число таких ui,, входящих в vijk ,для которых показатель загрузки ci имеет отрицательное значение.

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

Значение показателя   с учетом Кn для гена gn определяется следующим образом

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

,

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

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

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

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

трассировки

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

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

Алгоритм расчета фитнесса имеет следующий вид: в качестве исходных данных используется вектор А=al, где al – пропускная способность ребра ul. Для расчета фитнесса используется вектор B, имеющий ту же размерность, что и вектор А. Вначале  элементы  имеют нулевое значение.  Вектор В служит для учета загрузки ребер Ur всеми цепями.

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

Имея вектора А и В, рассчитываются значения показателей cl=al-bl для каждого ребра ul. На основании значений cl расcчитываются критерии F1, F2 и F3.

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

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

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

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

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

ПТ=ПИ+ПК.

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

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

Рекомендуем скачать другие рефераты по теме: тема здоровый образ жизни реферат, банк рефератов бесплатно.





Предыдущая страница реферата | 1  2  3  4  5 | Следующая страница реферата