Обобщенная линейная рекомбинация

Потомки вычисляются по следующим формулам:

O₁ = P₁ + RecM_x∙ range ∙ ∆ ∙ diff

O₂ = P₂ + RecM_x∙ range ∙ ∆ ∙ (-diff),

где RecM_x = 1,

range = 0,5,

diff = P₁-B/P₁,

∆ = ∑a(i) – 2ⁱ,

        1, если P₁=1/M

a(i) =

        0, если P₀=(m-1)/m

       

 

Оператор мутации

После выполнения операторов рекомбинации (скрещивания) полученные потомки с вероятностью P_m  подвергаются мутации, которая может быть выполнена различными способами:

1. Классическая мутация;

2. Оператор инверсий.

Оператор инверсий

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

Выполненный путем сложения особей с небольшими случайными значениями, которые называются шагом мутации. Шаг может изменяться в процессе решения задачи. Мутация с постоянным шагом и с постоянной вероятностью называется однородной. Однородная мутация выполняется следующим образом:

V_m = v ± r ∙ ∆,

где V, V_m – значения вещественной переменной до и после мутации;

r = 0,5(область определения переменной);

∆ - шаг мутации.

Целесообразно уменьшать вероятность случайной мутации. Обычно на начальном этапе Р =0.05...0.1, а на последующем этапе вероятность мутации уменьшают.. Для реализации этой процедуры иногда используют метод моделирования отжига (simulation annealing), который дает следующий закон изменения вероятности мутации:

P_m = P_m⁰ ∙ ,

где t – номер поколения.

Неоднородная мутация

Здесь изменяется шаг мутации. Этот тип оператора для векторного случая

S^t_v = (V₁, V₂,…,V_k,…,V_m)

V_k  [1,…n]

        V_k + ∆(t, U_k - V_k) при случ. число = 0

V_k^′  =                                                                    ,

        V_k - ∆(t, V_k - l_k) при случ. число = 1

 

 ∆(t, y)  [0,y] и ∆(t, y) определяет шаг мутации, который с увеличением номера поколения t уменьшается.

Один из вариантов реализации функции, определяющей шаг ∆(t, y)  следующий:

∆(t, y)  = y∙ ,

где Т – максимальное число поколений,

b=2 – параметр, определяющий степень неоднородности.

График изменения шага мутации:

 

Глобальная редукция

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

  R^t+1 = r^t +r^t_cr + r^t_m,                                        

где r^t - число особей предыдущей популяции;

  r^t_cr - численность особей, полученных путем скрещивания;

   r^t_m - число «мутантов».

Обычно в стационарных ГА мощность популяции поддерживается постоянной N = |P(t)|.Поскольку  R^t+1 > N,то необходимо устранить неудачные решения. Для этого существуют различные методы редукции.

 

Чистая замена

В простейшем случае с помощью скрещивания и мутации генерируются столько потомков, сколько было родителей. Далее родители устраняются, а потомки формируют следующее поколение P^t+1. При этом каждая особь живет лишь одно поколение. Такая схема часто используется в простом ГА. Однако при этом очевидно возможно, что некоторые очень хорошие решения могут быть заменены худшими, и лучшее решение будет потеряно.

 

Элитарная схема

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