Методы выбора пар для скрещивания

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

Случайный выбор (панмиксия) родительской пары, при котором оба родителя случайным образом выбираются из всей промежуточной популяции. Следует отметить, что при этом любая особь может входить в несколько пар. Этот метод является универсальным для решения различных задач, но достаточно критичен к численности популяции, поскольку его эффективность уменьшается с ростом мощности популяции

N.

Селективный выбор. Здесь родителями могут стать только те особи, значение целевой функции которых не меньше среднего значения по популяции при равной вероятности этих кандидатов составить родительскую пару. Такой подход обеспечивает более быструю сходимость алгоритма, но неприемлем для мультимодальных задач (имеющих несколько экстремумов), для которых этот метод, как правило, быстро сходится к одному из решений.

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

Для инбридингапервый член пары выбирается случайно, а вторым является максимально близкая к нему особь. Аутбридингформирует пары из максимально далеких особей.

Комбинация этих походов используется при решении многоэкстремальных задач.

 

Операторы рекомбинации (кроссинговера)

Различают операторы двоичной и вещественной рекомбинации. Рассмотрим двоичную рекомбинацию:

Многоточечный кроссинговер

В этом случае случайно выбирается r-позиций в диапазоне k

Затем родители обмениваются фрагментами, заключенными между соседями. При этом секции между первой позицией и первой точкой скрещиваются не обмениваются, а далее обмен производится через одну секцию.

 

Однородный кроссинговер

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

Для этого случайным образом генерируется двоичная маска кроссинговера той же длины (с тем числом бит), что у хромосом родителей. Четность бита маски показывает родителя, из которого копируется ген потомка. Для определенности допустим, что 1 соответствует первому родителю, а 0 - второму. На рисунке показана схема выполнения этого типа кроссинговера на конкретном примере.

 

 

Ограниченный кроссинговер

В этом виде скрещивания точки кроссинговера могут выбираться только там, где значения генов у родителей различны.

 

Рекомбинация

1. Дискретная рекомбинация - этот вид скрещивания определен над векторами, компонентами которых являются вещественные числа. Для каждой переменной значение переменной выбирается из первого или второго родителя с одинаковой вероятностью.

2. Промежуточная рекомбинация - значения потомков строятся в окрестности или между значениями родителей

 

 

В случае промежуточной рекомбинации потомок О₁ формируется следующим образом:

O₁ = P₁ + α₁ ∙ (P₂ – P₁), O₂ = P₁ + α₂ ∙ (P₂ – P₁),

где P₁, P₂ – вещественные значения, представляющие первого и второго родителя;

O_i – вещественное значение, представляющее потомка;

   α_i - масштабирующий множитель, который выбирается случайно из отрезка [-d, 1+d].

При обычной промежуточной рекомбинации d = 0 и α_i є [0,1]. Для обобщенной промежуточной рекомбинации d >0, обычно принимают d - 0,25. Этот оператор заимствован из другого направления эволюционных вычислений.

 

 

 

Рассмотрим выполнение оператора для первой компоненты:

O₁ = P₁ + α₁ ∙ (P₂ – P₁) = 12 + 0,5(123 – 12) = 67,5

Линейная рекомбинация

Этот вид оператора аналогичен предыдущему, но значения α одинаковы для всех переменных векторов.