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

Теорема шаблонов 
Теорема шаблонов
(
The Schema Theorem
) была приведена в упомянутой 
выше работе Холланда и является первой попыткой объяснить, почему 
генетические алгоритмы работают. Она показывает, как изменяется 
доля представителей шаблона в популяции.
Пусть 
M
(
H
, 
t
) — число представителей шаблона 
H
в 
t
-ом поколении. В 
силу того, что при построении промежуточной популяции используется 
пропорциональный отбор, в ней количество представителей данного 
шаблона будет
M
(
H
, 
t
+ 
intermediate
) = 
M
(
H
, 
t
) 
f
(
H
, 
t
) ⁄ <
f
(
t
)>
где 
f
(
H
, 
t
) — приспособленность шаблона 
H
в 
t
-ом поколении, а <
f
(
t
)> 
— средняя приспособленность 
t
-го поколения.
Особи промежуточной популяции с вероятностью 
p
c
подвергаются 
кроссоверу. Одноточечный кроссовер может разрушить шаблон, что 
означает, что один из родителей был представителем рассматриваемого 
шаблона, но ни один из детей уже таковым являться не будет. 
Вероятность разрушения меньше, чем
Δ(
H
) (1 − 
P
(
H
, 
t
) 
f
(
H
, 
t
) ⁄ <
f
(
t
)>) ⁄ (
L
−1)

---

А.Е. Кононюк Дискретно-непрерывная математика 
108 
где 
P(H, t)
— доля представителей шаблона 
H
в 
t
-ом поколении. Первый 
множитель произведения равен вероятности точки раздела попасть 
между фиксированными битами шаблона, а второй — вероятности 
выбрать в пару представителя другого шаблона.
Действительно, кроссовер разрушает шаблон не чаще, чем когда второй 
родитель (а он выбирается в промежуточной популяции) не является 
представителем этого шаблона, и при этом точка раздела попадает 
между фиксированными битами шаблона. Даже в этих ситуациях он не 
обязательно разрушается, например, если мы рассматриваем шаблон 
11****, а кроссоверу подвергаются строки 110101 и 100000, и точка