Одноточечный или простой оператор кросинговера (ОК) с заданной вероятностью выполняется в три этапа:
1-й этап. Две хромосомы (родители) выбираются случайно (или одним из методов, рассмотренных далее) из промежуточной популяции, сформированной при помощи оператора репродукции (ОР).
2-й этап. Случайно выбирается точка скрещивания - число из диапазона , где – длина хромосомы (число бит в двоичном коде).
Две новых хромосомы A', B' (потомки) формируются из A и B путем обмена подстрок после точки скрещивания:
Например, рассмотрим выполнение кроссинговера для хромосом 1 и 2 из промежуточной популяции:
Следует отметить, что ОК выполняется с заданной вероятностью (отобранные два родителя не обязательно производят потомков). Обычно величина вероятности полагается равной .
Таким образом, операторы репродукции и скрещивания очень просты – они выполняют копирование особей и частичный обмен частей хромосом. Продолжение нашего примера представлено на рис.1.3 во второй таблице (кроссинговер).
|
|
Сравнение с предыдущей таблицей показывает, что в промежуточной популяции после скрещивания улучшились все показатели популяции (среднее и максимальное значения целевой функции - ЦФ).
Мутация
Далее согласно схеме классического ГА с заданной вероятностью выполняется оператор мутации. Иногда этот оператор играет вторичную роль. Обычно вероятность мутации мала -
Оператор мутации (ОМ) выполняется в два этапа:
1-й этап. В хромосоме случайным образом выбирается -ая позиция (бит) .
2-й этап. Производится инверсия значения гена в -й позиции:
Например, для хромосомы 11011 выбирается и после инверсии значения третьего бита получается новая хромосома – 11111. Продолжение нашего примера представлено в третьей таблице (мутация) рис.1.3 образом, в результате применения генетических операторов найдено оптимальное решение .
В данном случае, поскольку пример искусственно подобран, мы нашли оптимальное решение за одну итерацию. В общем случае ГА работает до тех пор, пока не будет выполнен критерий окончания процесса поиска и в последнем полученном поколении определяется лучшая особь, которая и принимается в качестве решения задачи.