Операторы рекомбинации (скрещивания, кроссинговера)
Автор: Скобцов Ю.А.
Источник: Ю.О.Скобцов Основи еволюційних обчислень
.– Навчальний посібник.–Донецьк: ДонНТУ,2008.–326с. Мова–російська. стр. 113–117
Операторы рекомбинации (скрещивания, кроссинговера)
Различают операторы двоичной и вещественной рекомбинации (скрещивания). Рассмотрим сначала более привычную (и уже знакомую нам), применяемую в простом ГА двоичную рекомбинацию.
Двоичная рекомбинация
Одноточечный кроссинговер
Здесь случайно выбирается точка скрещивания с вероятностью Pc≈0.5 и производится обмен фрагментами хромосом после точки скрещивания. Пример показан на рисунке 4.8
Рисунок 4.8 – Одноточечный кроссинговер
Многоточечный кроссинговер
Разработаны различные обобщения классического одноточечного кроссинговера, которые наиболее полно представлены в [23]. При двухточечном кроссинговере потомки наследуют фрагменты хромосом родителей между двумя случайно выбранными точками скрещивания, как это, например, показано на рисунке 4.9
Рисунок 4.9 – Пример двухточечного кроссинговера
Графически это пример удобно представить в виде, показанном на рис. 4.10.
Рисунок 4.10 – Пример двухточечного кроссинговера
Многоточечный кроссинговер является обобщением предыдущих операторов на случай большего числа точек скрещивания. Например, трехточечный кроссинговер представлен на рис. 4.11.
Рисунок 4.11 – Пример трехточечного кроссинговера
Многоточечный кроссинговер с большим четным количеством точек скрещивания графически удобно представить для хромосом в виде «колец», что показано на рис. 4.12.[23] При этом хромосома рассматривается как замкнутое кольцо, а точки скрещивания выбираются с равной вероятностью по всей его окружности.
Рисунок 4.12 – Пример четырехточечного кроссинговера
Кроссинговер с нечетным количеством точек скрещивания можно представить таким же способом, если добавить дополнительную точку скрещивания в нулевой позиции.
Однородный кроссинговер
Этот вид скрещивания радикально отличается от предыдущих видов. Здесь каждый ген потомка создается путем копирования соответствующего гена из первого или второго родителя, то есть каждая позиция потенциально является точкой кроссинговера. Для этого случайным образом генерируется двоичная маска кроссинговера той же длины (с тем числом бит), что у хромосом родителей. Четность бита маски показывает родителя, из которого копируется ген потомка. Для определенности допустим, что 1 соответствует первому родителю, а 0 – второму. На рис. 4.13 показана схема выполнения этого типа кроссинговера на конкретном примере. Каждый бит потомка копируется из 1–го или 2–го родителя в соответствии со значением этого бита маски.
Рисунок 4.13 – Однородный кроссинговер
Таким образом, потомок содержит смесь генов из каждого родителя
Ограниченный кроссинговер
В этом виде скрещивания точки кроссинговера могут выбираться только там, где значения генов у родителей различны.