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

раздела попадает между первыми двумя битами, то, хотя вторая строка 
не является представителем нужного шаблона, все равно один из 
потомков окажется подходящим и шаблон не разрушится.
Таким образом, после кроссовера, переходя от количества 
представителей к их доле, получаем следующее неравенство:
P
(
H
, 
t
+ 1) ≥ 
P
(
H
, 
t
) 
f
(
H
, 
t
) [1 − 
p
c
Δ(
H
) (1 − 
P
(
H
, 
t
) 
f
(
H
, 
t
) ⁄ <
f
(
t
)>) ⁄ (
L
−1)] ⁄ 
<
f
(
t
)>
Теперь учтем влияние мутации. Для каждого фиксированного бита 
вероятность того, что он не будет инвертирован, равна (1 − 
p
m
). 
Поскольку всего в шаблоне фиксированных битов 
o
(
H
), то верна 
следующая итоговая формула теоремы шаблонов:
P
(
H
, 
t
+ 1) ≥ 
P
(
H
, 
t
) 
f
(
H
, 
t
) [1 − 
p
c
Δ(
H
) (1 − 
P
(
H
, 
t
) 
f
(
H
, 
t
) ⁄ <
f
(
t
)>) ⁄ (
L
−1)] 
(1 − 
p
m
)
o
(
H
)
⁄ <
f
(
t
)>
Полученное выражение не слишком удачно для анализа работы 
генетического алгоритма. Во-первых, в нем присутствует знак 
неравенства, связанный также с тем, что мы не учитывали случаи, когда 
рассматриваемый шаблон получается в результате кроссовера пары 
строк, не являющихся его представителями. Во-вторых, 
приспособленность шаблона и средняя приспособленность популяции 
быстро изменяются от поколения к поколению, поэтому полученное 
неравенство хорошо описывает ситуацию только для следующего 

---

А.Е. Кононюк Дискретно-непрерывная математика 
109 
поколения.
Тем не менее, теорема шаблонов является хоть каким-то теоретическим 
обоснованием работы классического генетического алгоритма (следует 
заметить, что она верна только для классического ГА с его 
пропорциональным отбором и одноточечным кроссовером). На данный 
момент существуют более точные версии этой теоремы, а также другие 
рассуждения, доказывающие целесообразность использования 
генетических алгоритмов.