Методы скрещивания в генетических алгоритмах

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

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

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

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

Генетические алгоритмы: точечное скрещивание

Двухточечное скрещивание – отличается от точечного скрещивания тем, что родительские хромосомы обмениваются участком генетического кода, который находится между двумя случайно выбранными точками скрещивания.

Генетические алгоритмы: двухточечное скрещивание

Многоточечное скрещивание представляет собой обобщение предыдущих операций и характеризуется соответственно большим количеством точек скрещивания. Например, для трех точек скрещивания, равных 4, 6 и 9, и для тех же родителей, что на рисунке выше, результаты будут следующие.

Генетические алгоритмы: трехточечное скрещивание

Для четырех точек скрещивания, равных 4, 6, 9 и 11 можно привести такой пример.

Генетические алгоритмы: четырехточечное скрещивание

Аналогично производится скрещивание для пяти или большего количества точек. Очевидно, что одноточечное скрещивание может считаться частным случаем многоточечного скрещивания.

Равномерное скрещивание, иначе называемое монолитным или одностадийным, выполняется в соответствии со случайно выбранным эталоном, который указывает, какие гены должны наследоваться от первого родителя (остальные гены берутся от второго родителя). Допустим, что выбран эталон $010110111011$ , в котором $1$ означает принятие гена на соответствующей позиции от первого родителя, а $0$ – от второго родителя. Таким образом, сформируется первый потомок. Для второго потомка эталон необходимо считывать аналогично, причем $1$ означает принятие гена на соответствующей позиции от второго родителя, а $0$ – от первого родителя. Пример равномерного скрещивания представлен на рисунке ниже.

Генетические алгоритмы: равномерное скрещивание

Оператор инверсии. Холланд предложил три технологии для получения потомков, отличающихся от родительских хромосом. Это уже известные операции скрещивания и мутации, а также операция инверсии. Инверсия выполняется на одиночной хромосоме; при ее осуществлении изменяется последовательность аллелей (последний ген меняется местами с первым, предпоследний – со вторым и т.д.) между двумя случайно выбираемыми позициями в хромосоме. Несмотря на то, что этот оператор был определен по аналогии с биологическим процессом хромосомной инверсии, он не слишком часто применяется в генетических алгоритмах. Пример инверсии проиллюстрирован ниже.