Кроссовер и мутация

Согласно структуре ГА все хромосомы (случайно полученные решения) оцениваются целевой функцией F(A). Далее, согласно процедуре селекции (отбора) производится построение списка упорядоченных хромосом. На основе анализа этого списка производится подбор пар хромосом на основе элитной селекции(хромосома с наилучшим значением целевой функции и случайно выбранной хромосомой).

После подбора пар применяется оператор кроссовера – ОК с вероятностью P_c к каждой паре хромосом. Исходная хромосома называется родительской, а хромосомы, полученные после операторов ГА – потомки.

Алгоритм применения ОК реализуется следующим образом:

Шаг 1. i=0

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

Шаг 3. Выбрать произвольно второго родителя.

Шаг 4. Сгенерировать случайное число .

Шаг 5. Если RND<P_c, то применить оператор кроссовера к выбранным хромосомам и добавить получившихся потомков к популяции.

Шаг 6. i=i+1.

Шаг 7. Если i<Mm, переход к шагу 2 (Mm – различные популяции).

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

Часть первого родителя перед первой и после второй точки разреза копируется в аналогичные места в потомке 1. Место между первой и второй точкой разреза во втором родителе копируется в аналогичное место первого потомка. Второй потомок строится аналогично.

Рассмотрим пример реализации оператора кроссовера. Пусть вертикальная волнистая линия означает точку разреза оператора кроссовера.

Потомок 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*P_c*2)*2*P_M*O(N₂)

O(N₂) – временная сложность декодирования хромосомы;

M – число цепей;

t – число поколений.