Xreferat.com » Рефераты по информатике и программированию » Генетический алгоритм глобальной трассировки

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

алгоритм глобальной трассировки" width="115" height="27" />

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

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

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

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

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

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

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

трассировки

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

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

Алгоритм расчета фитнесса имеет следующий вид: в качестве исходных данных используется вектор А={al| l=1,2, …}, где 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 – ой.

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

ПТ=ПИ+ПК.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

                     F1=Генетический алгоритм глобальной трассировки      ("i)[Cmin£Ci=ai-bi]

Если оказывалось, что Сmin

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: