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

Пример 5
В условиях примера 2 рассмотрим схему
S
1
=
1**** 

---

А.Е. Кононюк Дискретно-непрерывная математика 
138 
и проследим ее обработку при выполнении генетического алгоритма.
В этом случае 
L=
5, а охват и порядок схемы S
1
, составляют d(S
1
) = 0 и 
o
(S
1
) = 1 соответственно. В исходной популяции из примера 2 этой 
схеме соответствуют три хромосомы
ch
1
=[10011]
ch
4
=[10101]
ch
6
=[11101]
Приспособленность схемы S
1
, в исходной популяции
F(S
1,
 
0)=1096 и превышает среднюю приспособленность особей этой 
популяции 
F
(0) = 589, что следует из выражений (3.6) - (3.8). На основе 
формулы (3.9) легко рассчитать ожидаемое количество хромосом роди-
тельского пула, соответствущих схеме S
1
. Оно составит 3 * 1096/589 = 
5,58. В примере 2 по результатам селекции в родительский пул 
включены 6 таких хромосом: ch
6
, ch
4
, ch
6
, ch
1
, ch
4
, ch
6
. Ожидаемое ко-
личество хромосом, соответствущих схеме 
S
1,
 
после скрещивания с 
вероятностью р
с
=1 (вероятность мутации 
р
т
=
0), как легко рассчитать 
по формуле (3.10), должно превышать 5,58. В новую популяцию 
включены 6 представителей схемы S
1.
Это все хромосомы данной по-
пуляции.
Пример 6
В условиях примера 2 рассмотрим схему
S
2
= 11***
и проследим ее обработку при выполнении генетического алгоритма.
Длина 
L = 
5, а охват и порядок схемы S
2
составляют 
d(S
2
)= 
1 и 
o(S
2
)=
2 
соответственно. В исходной популяции из примера 2 этой схеме 
соответствует одна хромосома
ch
6
= [11101].
Поэтому приспособленность схемы S
2
в исходной популяции равна 
функции приспособленности хромосомы ch
6
и составляет 1683. Она 
превышает среднюю приспособленность особей исходной популяции, 
равную 589. По формуле (3.9) рассчитываем ожидаемое количество 
хромосом родительского пула, соответствущих схеме S
2
. Оно составит 
1683/589 = 2,86. В примере 2 по результатам селекции в родительский 
пул включены 3 одинаковых хромосомы [11101], соответствущих 
схеме S
2
. Ожидаемое количество хромосом в новой популяции, 
соответствущих схеме S
2
, после скрещивания с вероятностью
р
с
 
= 1 (вероятность мутации 
р
т
= 
0), должно превышать 5,58. В при-
мере 2 в новую популяцию включены 3 хромосомы, соответствущих 
схеме S
2
. Это
Ch
4
=Ch
5
= Ch
6
= [11101]. 

---

А.Е. Кононюк Дискретно-непрерывная математика 
139