Введение в эволюционное моделирование. Каширина И.Л. - 30 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

30
Создаются два потомка H
1
= (h
1
1
,…,h
n
1
), H
2
= (h
1
2
,…,h
n
2
), где h
k
1
=
w*c
k
1
+ (1-w)*c
k
2
, h
k
2
= w*c
k
2
+(1-w)*c
k
1
, k=1,…,n, w либо константа (рав-
номерный арифметический кроссовер) из интервала [0;1], либо изменяется с
увеличением эпох (неравномерный арифметический кроссовер).
Геометрический кроссовер (geometrical crossover)
Создаются два потомка H
1
= (h
1
1
,…,h
n
1
), H
2
= (h
1
2
,…,h
n
2
), где h
k
1
=
(с
k
1
)
w
(c
k
2
)
1-w
, h
k
2
= (c
k
2
)
w
(c
k
1
)
1-w
, w – случайное число из интервала [0;1].
(Применяется только если векторы C
1
и C
2
неотрицательны)
Смешанный кроссовер (alpha crossover)
Генерируется потомок H = (h
1
,…,h
k
,…,h
n
), где h
k
– случайное число из
интервала [c
k
min
-I
k
*alpha, c
k
max
+I
k
*alpha], c
k
min
=min(c
k
1
,c
k
2
), c
k
max
=max(c
k
1
,c
k
2
),
I
k
=c
k
max
–c
k
min
. При alpha =0 кроссовер превращается в плоский.
Линейный кроссовер (linear crossover)
Создаются три потомка H
q
=(h
1
q
,…,h
k
q
,…,h
n
q
), q=1,2,3, где
h
k
1
=0.5*c
k
1
+0.5*c
k
2
, h
k
2
=1.5*c
k
1
-0.5*c
k
2
, h
k
3
=–0.5*с
k
1
+1.5*c
k
2
. На этапе селек-
ции в этом кроссовере отбираются два наиболее приспособленных потомка.
Дискретный кроссовер (discrete crossover)
Каждый ген h
k
выбирается случайно по равномерному закону из ко-
нечного множества {c
k
1
,c
k
2
}.
Расширенный линейный кроссовер (extended line crossover)
Ген h
k
=c
k
1
+w*(c
k
2
–c
k
1
), w – случайное число из интервала [-0.25;1.25].
Эвристический кроссовер (Wright’s heuristic crossover)
Пусть C
1
– один из двух родителей с лучшей приспособленностью. То-
гда h
k
= w*|c
k
1
-c
k
2
|+c
k
1
, w – случайное число из интервала [0;1].
В качестве оператора мутации наибольшее распространение получила
случайная мутация. При случайной мутации ген, подлежащий изменению,
принимает случайное значение из интервала своего изменения.
Рассмотренные кроссоверы исторически были предложены первыми,
однако во многих задачах их эффективность оказывается невысокой. Ис-
ключение составляет смешанный кроссовер с параметром alpha=0.5 – он
превосходит
по эффективности большинство простых кроссоверов. Позднее
были разработаны улучшенные операторы скрещивания, аналитическая
формула которых и эффективность обоснованы теоретически. Рассмотрим
подробнее один из таких кроссоверов – SBX.
SBX кроссовер 
                                       30
      Создаются два потомка H1 = (h11, ,hn1), H2 = (h12, ,hn2), где hk1 =
w*ck1 + (1-w)*ck2, hk2 = w*ck2+(1-w)*ck1, k=1, ,n, w либо константа (рав-
номерный арифметический кроссовер) из интервала [0;1], либо изменяется с
увеличением эпох (неравномерный арифметический кроссовер).
Геометрический кроссовер (geometrical crossover)
       Создаются два потомка H1 = (h11, ,hn1), H2 = (h12, ,hn2), где hk1=
(сk1)w(ck2)1-w, hk2 = (ck2)w(ck1)1-w, w – случайное число из интервала [0;1].
(Применяется только если векторы C1 и C2 неотрицательны)
Смешанный кроссовер (alpha crossover)
      Генерируется потомок H = (h1, ,hk, ,hn), где hk – случайное число из
интервала [ckmin-Ik*alpha, ckmax+Ik*alpha], ckmin=min(ck1,ck2), ckmax=max(ck1,ck2),
Ik=ckmax–ckmin. При alpha =0 кроссовер превращается в плоский.
Линейный кроссовер (linear crossover)
      Создаются три потомка Hq=(h1q, ,hkq, ,hnq), q=1,2,3, где
hk1=0.5*ck1+0.5*ck2, hk2=1.5*ck1-0.5*ck2, hk3=–0.5*сk1+1.5*ck2. На этапе селек-
ции в этом кроссовере отбираются два наиболее приспособленных потомка.
Дискретный кроссовер (discrete crossover)
     Каждый ген hk выбирается случайно по равномерному закону из ко-
нечного множества {ck1,ck2}.
Расширенный линейный кроссовер (extended line crossover)
      Ген hk=ck1+w*(ck2–ck1), w – случайное число из интервала [-0.25;1.25].
Эвристический кроссовер (Wright’s heuristic crossover)
      Пусть C1 – один из двух родителей с лучшей приспособленностью. То-
гда hk = w*|ck1-ck2|+ck1, w – случайное число из интервала [0;1].
     В качестве оператора мутации наибольшее распространение получила
случайная мутация. При случайной мутации ген, подлежащий изменению,
принимает случайное значение из интервала своего изменения.
     Рассмотренные кроссоверы исторически были предложены первыми,
однако во многих задачах их эффективность оказывается невысокой. Ис-
ключение составляет смешанный кроссовер с параметром alpha=0.5 – он
превосходит по эффективности большинство простых кроссоверов. Позднее
были разработаны улучшенные операторы скрещивания, аналитическая
формула которых и эффективность обоснованы теоретически. Рассмотрим
подробнее один из таких кроссоверов – SBX.
SBX кроссовер

Страницы