Оператор кроссинговера (скрещивания)

Одноточечный или простой оператор кросинговера (ОК) с заданной вероятностью выполняется в три этапа:

1-й этап. Две хромосомы (родители) выбираются случайно (или одним из методов, рассмотренных далее) из промежуточной популяции, сформированной при помощи оператора репродукции (ОР).

2-й этап. Случайно выбирается точка скрещивания - число из диапазона , где – длина хромосомы (число бит в двоичном коде).

Две новых хромосомы A', B' (потомки) формируются из A и B путем обмена подстрок после точки скрещивания:

Например, рассмотрим выполнение кроссинговера для хромосом 1 и 2 из промежуточной популяции:

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

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

Сравнение с предыдущей таблицей показывает, что в промежуточной популяции после скрещивания улучшились все показатели популяции (среднее и максимальное значения целевой функции - ЦФ).

Мутация

Далее согласно схеме классического ГА с заданной вероятностью выполняется оператор мутации. Иногда этот оператор играет вторичную роль. Обычно вероятность мутации мала -

Оператор мутации (ОМ) выполняется в два этапа:

1-й этап. В хромосоме случайным образом выбирается -ая позиция (бит) .

2-й этап. Производится инверсия значения гена в -й позиции:

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

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