- •Алгоритмические методы конструирования эвс § 1. Общая характеристика основных задач этапа конструкторского проектирования
- •§ 2. Математические модели схем эвс
- •Граф коммутационной схемы
- •Гиперграф
- •Взвешенный неориентированный граф
- •§ 3. Математическая постановка задачи компоновки схем конструктивно унифицированными модулями
- •Минимальное число межблочных связей;
- •Математическая постановка задачи компоновки с использованием модели внг
- •Математическая постановка задачи компоновки с использованием модели гг
- •Общая характеристика алгоритмов компоновки конструктивных модулей
- •§ 4. Последовательный алгоритм компоновки
- •§ 5. Задача размещения конструктивных модулей
- •§ 6. Конструктивные алгоритмы размешения
- •Последовательные алгоритмы размещения по связности
- •Тема Параллельно-последовательное размещение Метод обратного размещения.
- •Итерационные алгоритмы размещения
- •§ Задача покрытия схем набором конструктивных модулей.
- •Трассировка печатных соединений
- •Волновой алгоритм решения задачи трассировки.
- •Лучевой алгоритм трассировки.
- •Алгоритм Рабина.
- •Алгоритм слежения за целью.
- •Алгоритм Прима.
- •Генетические алгоритмы Основные понятия и определения
- •Генетические алгоритмы
- •Постановка задачи поиска оптимальных решений с помощью генетических алгоритмов
- •Простой генетический алгоритм
- •Выбор родителей
- •Скрещивание
- •Селекция
- •Разновидности ген. Операторов
- •Мутации
- •Селекция
- •Особенности генетических алгоритмов
- •Генетические алгоритмы для трассировки двухслойных каналов
- •Задача канальной трассировки классической постановки
- •Описание каналов
- •Генетические алгоритмы для канальной трассировки
- •Стандартная схема генетического поиска. Структура г.А.
- •Генетическое опер-и прим-е в алгоритме канальной трассировки. Кодирование хромосомы
- •Кроссовер и мутация
Кроссовер и мутация
Согласно структуре ГА все хромосомы (случайно полученные решения) оцениваются целевой функцией F(A). Далее, согласно процедуре селекции (отбора) производится построение списка упорядоченных хромосом. На основе анализа этого списка производится подбор пар хромосом на основе элитной селекции(хромосома с наилучшим значением целевой функции и случайно выбранной хромосомой).
После подбора пар применяется оператор кроссовера – ОК с вероятностью Pc к каждой паре хромосом. Исходная хромосома называется родительской, а хромосомы, полученные после операторов ГА – потомки.
Алгоритм применения ОК реализуется следующим образом:
Шаг 1. i=0
Шаг 2. Выбрать хромосом с наилучшим значением целевой функции как первого родителя.
Шаг 3. Выбрать произвольно второго родителя.
Шаг 4. Сгенерировать случайное число .
Шаг 5. Если RND<Pc, то применить оператор кроссовера к выбранным хромосомам и добавить получившихся потомков к популяции.
Шаг 6. i=i+1.
Шаг 7. Если i<Mm, переход к шагу 2 (Mm – различные популяции).
Под оператором кроссовера подразумевается обмен, скрещивание генетического материала между двумя различными хромосомами (потенциальными родителями). После окончания оператора кроссовера полученные потомки подвергаются мутации. В большинстве случаев может быть выбран стандартный двухточечный оператор кроссовера. Первая и вторая точки разрыва в таком операторе кроссовера выбираются случайно.
Часть первого родителя перед первой и после второй точки разреза копируется в аналогичные места в потомке 1. Место между первой и второй точкой разреза во втором родителе копируется в аналогичное место первого потомка. Второй потомок строится аналогично.
Рассмотрим пример реализации оператора кроссовера. Пусть вертикальная волнистая линия означает точку разреза оператора кроссовера.
Родитель 1 |
0 |
1 |
0 |
F(A)=72 (рис.7) |
Родитель 2 |
1 |
0 |
1 |
F(A)=7 |
Потомок 1 |
0 |
0 |
0 |
F(A)=70 (рис.1) |
Потомок 2 |
1 |
1 |
1 |
F(A)=77 |
Потомок 2 аналогичен родителю 2. В данном случае получен потомок 1 с лучшим значением целевой функции, чем значение целевой функции (72,77).
Мутация произвольно изменяет 1 ген выбранной хромосомы случайно изменяя значение гена с вероятностью РМ равной норме мутации. Алгоритм применения операции мутации выглядит следующим образом:
Шаг 1. i=i+1.
Шаг 2. Сгенерировать случайное число RND [0,1]
Шаг 3. Если RND< РМ, то применить ОМ к i-ой хромосоме М.
Шаг 4. i=i+1.
Шаг 5 если i<M, то к шагу 1.
Смысл ОМ введение добавочных изменений в популяцию. В простейшем случае может быть выбрана точечная мутация, она заключается в изменении произвольного гена в хромосоме с вероятностью РМ. Это происходит следующим образом: один из генов хромосомы выбирается случайно, а затем меняет свое значение на противоположное. Пример хромосомы (до применения ОМ): 0,(1),0. Значение целевой функции – 72.
Хромосома после применения ОМ: 0,(0),0, значение целевой функции – 70 – min. Выбранная точка мутации показана в скобках. После применения ОМ получается хромосома с лучшим значением целевой функции. Дальнейшее улучшение работы генетического алгоритма можно получить за счет сортировки гена в хромосоме или путем использования более сложной целевой функции. Кроме того, можно анализировать параллельные и последовательно – параллельные методы генетического поиска.
Теоретическая временная сложность рассмотренного генетического алгоритма составляет t*(M*Pc*2)*2*PM*O(N2)
O(N2) – временная сложность декодирования хромосомы;
M – число цепей;
t – число поколений.