Операторы рекомбинации (скрещивания, кроссинговера)
Автор: Скобцов Ю.А.
Источник: Ю.О.Скобцов Основи еволюційних обчислень
.– Навчальний посібник.–Донецьк: ДонНТУ,2008.–326с. Мова–російська. стр. 117–120
Рекомбинация действительных значений
При этом хромосома представляется действительными (вещественными) числами.
Дискретная рекомбинация
Этот вид скрещивания определен над векторами, компонентами которых являются вещественные числа. Рассмотрим на примере двух особей, соответствующие вектора которых имеют три целых значения. Для каждой переменной (позиции) значение переменной выбирается из 118 первого или второго родителя с равной вероятностью. Пример выполнения этого оператора показан на рис.4 .14. Здесь образцы (маски) показывают принадлежность данной компоненты потомка определенному родителю. Отметим, что этот тип рекомбинации применим к значениям любого типа.
Промежуточная рекомбинация
Этот метод применим только для особей, представленных только вещественными значениями. Здесь значения потомков строятся в окрестности или между значениями родителей.
Рис. 4.14 – Дискретная рекомбинация
В случае промежуточной рекомбинации потомок O1 формируется
следующим образом:
O1=P1+α1*(P2-P1), O2=P1+α2*(P2-P1)
где P1, P2 – вещественные значения, представляющие первого и
второго родителя;
Oi– вещественное значение, представляющее потомка;
αi - масштабирующий множитель, который выбирается случайно из
отрезка [-d, 1+d].
При обычной промежуточной рекомбинации d = 0 и αi[0,1]. Для обобщенной промежуточной рекомбинации d > 0 , обычно принимают d = 0,25. Значение каждой переменной, в том числе и для векторов формируется по приведенному выражению. Отметим, что здесь используются чисто арифметические операции (сложение и умножение). Заметим, что при d=0 потомки принадлежат отрезку [P1, P2]. Эти операторы совершенно не похожи на классический кроссинговер. Фактически, этот оператор заимствован из другого направления эволюционных вычислений «эволюционные стратегии». На рис. 4.15 показан пример выполнения этого оператора для тех же данных, которые использовались в предыдущем примере.
Рис. 4.15 – Промежуточная рекомбинация
Для примера подробно рассмотрим выполнение оператора для 1–ой компоненты O1=P1+α1*(P2-P1)=12+0.5*(123-12)=67.5
Линейная рекомбинация
Этот вид оператора аналогичен предыдущему, за исключением того, что значение масштабирующего множителя одинаково для всех переменных (компонент) векторов. Пример выполнения этого оператора представлен на рис. 4.16.
Рис. 4.16 – Линейная рекомбинация