Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

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

---

А.Е. Кононюк Дискретно-непрерывная математика 
72 
дополнительный элемент неопределенности в процесс поиска решения. 
В данном случае, неопределенность не подразумевает негативный 
фактор, а является своебразной "степенью свободы" работы 
генетического алгоритма.
Здесь описываются только два самых распространенных и 
необходимых оператора. Существуют и другие генетические операторы 
(например, 
инверсия
), но они применяются очень редко и поэтому мы о 
них говорить не будем.
Оператор кроссинговера
Оператор кроссинговера (crossover operator)
, также называемый 
кроссовером, является основным генетическим оператором, за счет 
которого производится обмен генетическим материалом между 
особями. Оператор моделирует процесс скрещивания особей. Пусть 
имеются две родительские особи с хромосомами Х={x
i
, i=1,L} и Y={y
i
, 
i=1,L}. Случайным образом определяется точка внутри хромосомы, в 
которой обе хромосомы делятся на две части и обмениваются ими. 
Назовем эту точку точкой разрыва. Вообще говоря, в англоязычной 
литературе она называется 
точкой кроссинговера
(crossover point), 
просто, точка разрыва более образное название и к тому же позволяет в 
некоторых случаях избежать тавтологии. Описанный процесс 
изображен на рис.2.3.
Рис.2.3. Кроссинговер
Данный тип кроссинговера называется 
одноточечным
, т.к. при нем 
родительские хромосомы разрезаются только в одной случайной точке. 
Также существует 
2-х
и 
n-точечный
операторы кроссинговера. В 2-х 
точечном кроссинговере точек разрыва 2, а n-точечный кроссинговер 

---

А.Е. Кононюк Дискретно-непрерывная математика 
73 
является своебразным обобщением 1- и 2-точечного кроссинговеров для 
n > 2.
Кроме описанных типов кроссинговера есть ещё 
однородный 
кроссинговер
. Его особенность заключается в том, что значение каждого 
бита в хромосоме потомка определяется случаным образом из 
соответствующих битов родителей. Для этого вводится некоторая 
величина 0<
p
0
<1, и если случайное число больше 
p
0
, то на 
n
-ю позицию 
первого потомка попадает 
n
-й бит первого родителя, а на 
n
-ю позицию 
второго - 
n
-й бит второго родителя. В противном случае к первому 
потомку попадает бит второго родителя, а ко второму - первого. Такая 
операция проводится для всех битов хромосомы.
Вероятность кроссинговера самая высокая среди генетических 
операторов и равна обычно 60% и больше.