Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

Вывод 3.4 (влияние мутации)
Вероятность того, что некоторая хромосома из 
М(k)

S 
будет 
принадлежать к схеме S после операции мутации, определяется вы-
ражением
(1-p
m
)
o
(S)
.
Эта величина называется 
вероятностью выживания схемы S после 
мутации. 
Вывод 3.5
Если вероятность мутации 
р
т
 
мала 
(р
т
« 
1), то можно считать, что 
вероятность выживания схемы S после мутации, определенная в 
выводе 3.4, приближенно равна
1 - 
р
т
 o
(S).
Эффект совместного воздействия селекции, скрещивания и мутации 
(выводы 3.1 - 3.4) с учетом факта, что если хромосома из множества 
М(k)

S 
дает потомка, соответствующего схеме S, то он будет 
принадлежать к 
Р(k+
1)

S, ведет к построению следующей схемы 
репродукции :
E[c(S,k + 1)]≥c(S,k) 
)
k
(
F
)
k
,
S
(
F
(
1-
p
c
1

L
)
S
(
d
)
(1-p
m
)
o
(s)
. (3 10)
Зависимость (3.10) показывает, как изменяется от популяции к 
популяции количество хромосом, соответствующих данной схеме. Это 
изменение вызывается тремя факторами, представленными в правой 
части выражения (3.10), в частности: 
F(S,k)IF(k) 
отражает роль 
среднего значения функции приспособленности, 1
-p
c
d(S)/(L-
1) 
показывает влияние скрещивания и (1-p
m
)
o
(S)
- влияние мутации. Чем 

---

А.Е. Кононюк Дискретно-непрерывная математика 
135 
больше значение каждого из этих факторов, тем большим оказывается 
ожидаемое количество соответствий схеме S в следующей популяции. 
Вывод 3.5 позволяет представить зависимость (3.10) в виде
E[c(S,
k
+1)] ≥c(S,k) 
)
k
(
F
)
k
,
S
(
F
(
1-
p
c
1

L
)
S
(
d
-p
m
o
(s)
)
. (3.11)
Для больших популяций зависимость (3.11) можно аппроксимировать 
выражением 
c(S,
k
+1)≥c(S,k) 
)
k
(
F
)
k
,
S
(
F
(
1-
p
c
1

L
)
S
(
d
-p
m
o
(s)
)
. (3.12)
Из формул (3.11) и (3.12) следует, что ожидаемое количество 
хромосом, соответствующих схеме S в следующем поколении, можно 
считать функцией от фактического количества хромосом, принадле-
жащих этой схеме, относительной приспособленности схемы, а также 
порядка и охвата схемы. Заметно, что схемы с приспособленностью 
выше средней и с малым порядком и охватом характеризуются возра-
станием количества своих представителей в последующих популяциях. 
Подобный рост имеет показательный характер, что следует из вы-
ражения (3.9). Для больших популяций эту формулу можно заменить 
рекуррентной зависимостью вида 
c(S,k + 1) = c(S,k) 
)
k
(
F
)
k
,
S
(
F
(3.13)
Если допустить, что схема