Особенности генетических алгоритмов

Селекция

Мутации

Бывают точечные мутации (в первом гене), макромутаии (в нескольких генах) и хромосомные (появляются новые хромосомы)

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

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

Другой вариант селекции – отбор после каждого операции скрещивания двух лучших экземпляров среди двух потомков и двух родителей.

Часто именно потомки с F_min принужденно включаются в новое поколение, такой подход называется элипумом. Он способствует большей сходимости и локальному экстремуму. Но в многоэкстрем. Ситуации ограничивает возможность попадания в окрестности других локальных экстремумов.

Третий вариант селекции – отбор N экземпляров среди генов репродукции группы, которая состоит из родителей, потомков, мутантов, удовлетворяющих условию: F_i < t. t – порог значения функции полезности. Порог может быть равен ил среднему значению функции F в текущем поколении или значению F особи, занимающее определенное порядковое место. Суть мягкой схемы отбора – включение в новое поколение N лучших представителей репродукции группы.

Жесткая схема отбора – новое поколение экземпляры включаются с вероятностью, определяемое (1).

Четвертый вариант селекции – переупорядочивание – назначение переуп-е генов связывания со своими свойствами, носящими название эпистасис. Эпистасис имеет место если F зависит не только от значений генов, но и от их позиционирования. Связывание эпистасиса говорит о нелинейности функции F, что приводит к усложнению оптимизационной задачи.

Генетические алгоритмы не единственный способ решения задач оптимизации.

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

Минусы: Большая вычислительная сложность, но если перебор всех вариантов за разумное время возможен, то найденное решение является оптимальным.

2) Метод градиентного спуска.

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

Эти методы работают быстро, но не гарантируют оптимальности решения. Практические задачи,как правило, мультимодальны и многомерны. Комбинируя переборные методы можно получить приблизительные решения, точность которых будет выше с увеличением t_n.

Генетические алгоритмы представляют собой именно такой комбинированный метод механизма скрещивания.

Генетические алгоритмы для трассировки двухслойных каналов

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

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

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

Основная особенность генетических алгоритмов состоит в том, что анализируется не одно решение, а некоторое подмножество квазиопытных решений, названных хромосомами или стрингами.

Для каждой хромосомы должна быть цел. функция F(n), названная эволюционной.

n- число элементов в хромосоме. Функция F(n) вычисляет определенный вес каждой хромосомы. В каждой популяции хромосомы могут подвергаться действиям различных опер-в: кроссовера, инверсии, мутации, сегрегации, транслокации и т. п.

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

Задача канальной трассировки классической постановки

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

Канал – область прямоугольной формы, на одной или нескольких сторонах которой расположены контакты с системой однонаправленных магистралей.

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

Горизонтальные сегменты располагаются в одном слое, вертикальные в другом. Соединения между горизонтальными и вертикальными делятся через переходные отверстия.

Основная задача канальной трассировки – выбор наименьшей трассировки канала, достаточной для размещения в нем всех соединений и назнач. соединений на магистралях.

Необходимо минимизировать суммарную длину соединений, число переходных отверстий и т. д.

Задача канальной трассировки в классической постановке основана трассировке двустороннего канала по верхней и нижней сторонам которого проходят линейки контактов.

Изломы (т. е. переходы) горизонтального участка с одной магистрали на другой не допускаются.

Дата добавления: 2014-01-14