4.8.3. Генетические операторы

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

Двухточечное скрещивание (two-point crossover), как следует из его названия, отличается от точечного скрещивания тем, что потомки наследуют фрагменты родительских хромосом, определяемые двумя случайно выбранными точками скрещивания. Для пары хромосом из примера 4.4 скрещивание в точках 4 и 6 показано на рис. 4.12. Обратим внимание, что такое скрещивание не приводит к уничтожению схемы 1**********1, которую представляет родитель 2.

Рис. 4.12. Пример двухточечного скрещивания.

Многоточечное скрещивание (multiple-point crossover) представляет собой обобщение предыдущих операций и характеризуется соответственно большим количеством точек скрещивания. Например, для трех точек скрещивания, равных 4, 6 и 9, и такого же количества родителей, как на рис. 4.12, результаты скрещивания показаны на рис. 4.13.

Рис. 4.13. Пример трехточечного скрещивания.

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

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

Рис. 4.14. Двухточечное скрещивание с точками скрещивания 4 и 6.

Многоточечное скрещивание для четырех точек, равных 1, 4, 6, 9 и 4, 6, 9, 11 для той же пары родителей из предыдущих примеров иллюстрируется на рис. 4.15.

Рис. 4.15. Многоточечное скрещивание с четырьмя точками скрещивания, равными 1, 4, 6, 9 и 4, 6, 9, 11.

Многоточечное скрещивание с большим четным количеством точек скрещивания протекает аналогично показанному на рис. 4.15.

Скрещивание с нечетным количеством точек можно представить таким же образом, если добавить еще одну точку скрещивания в позиции, равной 0. Приведенный выше пример для трех точек можно представить также, как на рис. 4.15, с точками скрещивания 0, 4, 6, 9. При четном количестве точек хромосома рассматривается как замкнутое кольцо (см. рис. 4.14 и 4.15), а точки скрещивания выбираются с равной вероятностью по всей его окружности.

Равномерное скрещивание (uniform crossover), иначе называемое монолитным или одностадийным, выполняется в соответствии со случайно выбранным эталоном, который указывает, какие гены должны наследоваться от первого родителя (остальные гены берутся от второго родителя). Допустим, что для пары родителей из примеров на рис. 4.12-4.15 выбран эталон 010110111011, в котором 1 означает принятие гена на соответствующей позиции (locus) от родителя 1, а 0 - от родителя 2. Таким образом, формируется первый потомок. Для второго потомка эталон необходимо считывать аналогично, причем 1 означает принятие гена на соответствующей позиции от родителя 2, а 0 - от родителя 1. В этом случае равномерное скрещивание протекает так, как показано на рис. 4.16.

Рис. 4.16. Пример равномерного скрещивания.

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