Классический генетический алгоритм. Часть IV. Скрещивание, мутация, создание популяции

Классический генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

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

Рассмотрим пятый и шестой этапы: применение генетических операторов и формирование новой популяции.

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

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

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

Оператор скрещивания. На первом этапе скрещивания выбираются пары хромосом из родительской популяции (родительского пула). Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания $p_{c}$ . Далее для каждой пары отобранных таким образом родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если хромосома каждого из родителей состоит из $L$ генов, то очевидно, что точка скрещивания $l_{k}$ представляет собой натуральное число, меньшее $L$ . Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала $delim{[}{1,L-1}{]}$ . В результате скрещивания пары родительских хромосом получается следующая пара потомков:

потомок, хромосома которого на позициях от до $l_{k}$ состоит из генов первого родителя, а на позициях от $l_{k}~+~1$ до $L$ – из генов второго родителя;
потомок, хромосома которого на позициях от до $l_{k}$ состоит из генов второго родителя, а на позициях от $l_{k}~+~1$ до $L$ – из генов первого родителя.

Действие оператора скрещивания проиллюстрировано следующим примером.

Оператор мутации с вероятностью $p_{m}$ , изменяет значение гена в хромосоме на противоположное (т.е. с на или наоборот). Например:

Как уже упоминалось выше, вероятность мутации обычно очень мала, и именно от нее зависит, будет данный ген мутировать или нет. Вероятность $p_{m}$ мутации может эмулироваться, например, случайным выбором числа из интервала $delim{[}{0,1}{]}$ для каждого гена и отбором для выполнения этой операции тех генов, для которых разыгранное число оказывается меньшим или равным значению $p_{m}$ .

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