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

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

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

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

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

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

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

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

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

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

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