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

Пример 7
В условиях примера 2 рассмотрим схему
S
3
= ***11
и проследим ее обработку при выполнении генетического алгоритма. 
Длина 
L= 
5, а охват и порядок схемы S
3
составляют d(S
3
) = 1 и 
o(S
3
) = 
2 
соответственно. В исходной популяции из примера 2 этой схеме 
соответствуют три хромосомы
ch
1
= [10011] 
ch
2
= [00011]
ch
3
= [00111]
В отличие от примеров 5 и 6 приспособленность схемы S
3 
в исходной 
популяции оказывается меньше средней приспособленности особей 
этой популяции 
F
(0)=589 и составляет F(S
3
, 0)=280. Ожидаемое 
количество хромосом родительского пула, соответствующих схеме S
3
и 
рассчитанное по формуле (3.9), равно 3 * 280/589 = 1,426. В примере 2
в родительский пул была включена одна хромосома [10011], 
соответствующая схеме S
3
. На основе формулы (3.10) получаем 
значение 1,068, определяющее количество представителей схемы S
3
в 
новой популяции. В примере 2 после скрещивания с вероятностью
р
с
= 
1 (вероятность мутации 
р
т
= 
0) в новую популяцию была 
включена одна хромосома, соответствующая схеме S
3
, т.е.
Ch
2 
= [10111]. 
Пример 8 
В условиях примера 2 рассмотрим схему
S
4
= *10**
и проследим ее обработку при выполнении генетического алгоритма. 
Длина 
L 
= 5, а охват и порядок схемы S
4
составляют 
d(S
4
)=
1 и 
o(S
A
) = 2 
соответственно. В исходной популяции из примера 2 этой схеме 
соответствует только одна хромосома ch
5
= [01000]
Поэтому приспособленность схемы S
4
в исходной популяции равна 
значению функции приспособленности хромосомы ch
5
и составляет 
129. Аналогично примеру 7, она меньше средней приспособленности 
особей начальной популяции, которая равна 589. Ожидаемое 
количество представителей схемы S
4
в родительском пуле составляет 
129/589 = 0,22, что следует из формулы (3.9). В примере 2 
родительский пул (после селекции) не содержит ни одной хромосомы, 
соответствующей схеме S
4
. При расчете ожидаемого количества 

---

А.Е. Кононюк Дискретно-непрерывная математика 
140 
представителей схемы S
4
в новой популяции по формуле (3.10) для 
вероятности скрещивания 
р
с
= 
1 и вероятности мутации 
р
т
 
= 0 по-
лучаем значение 0,165. В примере 2 после скрещивания в новую 
популяцию не была включена ни одна хромосома, соответствующая 
схеме S
4
.
Из примеров 4-8, посвященных обработке схем, можно сделать 
следующие выводы. Эти примеры иллюстрируют основную теорему 
генетических алгоритмов - теорему о схемах. Они затрагивают 
обработку схем низкого (малого) порядка с малым охватом. Примеры 
4-6 демонстрируют увеличение количества представителей данной 
схемы в следующем поколении для случая, когда приспособленность 
этой схемы превышает среднюю приспособленность всех особей 
популяции. Примеры 7 и 8 показывают ситуацию, когда 
приспособленность схемы оказывается меньше средней при-
способленности особей популяции. Количество представителей таких 
схем в следующих поколениях не увеличивается, а наоборот - наблю-
дается уменьшение количества соответствующих им хромосом.
При анализе подобных примеров для схем большего порядка и 
большего охвата также не регистрируется увеличение количества их 
представителей в следующем поколении, что согласуется с теоремой о 
схемах.
Графическая интерпретация схем, обсуждавшихся в примерах 5 и 8, 
представлена 
на 
рис.4; 
аналогичным 
образом 
можно 
проиллюстрировать схемы из примеров 6 и 7, равно как и любые 
другие. 

---

А.Е. Кононюк Дискретно-непрерывная математика 
141 
Рис.4. Графическое представление схем для целочисленных значений 
х 
от 0 до 
31, закодированных в форме 5-битовых двоичных последовательностей для 
оптимизации функции 
f(x) 
= 2х
2
+ 1 (примеры 1, а также 5 и 8).

---

А.Е. Кононюк Дискретно-непрерывная математика 
142 
На рис. 4 видно, что к схеме 1*** (пример 5) в исходной популяции из 
примера 2 принадлежат хромосомы ch
1,
ch
4
и ch
6 
с фенотипами 19, 21, 
29 соответственно, а после селекции и скрещивания к этой схеме уже 
принадлежат все включенные в новую популяцию хромосомы, т.е. Ch
1,
 
Ch
2
, Ch
3
, Ch
4
, Ch
5
, и Ch
6
с фенотипами 17, 23, 21, 29, 29, 29 
соответственно. В то же время к схеме *10** (пример 8) в исходной 
популяции из примера 2 принадлежит только одна хромосома ch
5
, 
фенотип которой равен 8; в следующей популяции уже нет ни одной 
хромосомы, принадлежащей этой схеме. Обратим внимание (рис. 4), 
что оптимальное решение, которое максимизирует функцию, заданную 
выражением (3.1), принадлежит к схеме 1**** и не соответствует 
схеме *10**.
Выполнение генетических алгоритмов основано на обработке схем. 
Схемы малого порядка, с малым охватом и приспособленностью выше 
средней выбираются, размножаются и комбинируются, в результате 
чего формируются все лучшие кодовые последовательности. Поэтому 
оптимальное решение строится (в соответствии с гипотезой 
кирпичиков) путем объединения наилучших из полученных к 
текущему моменту частичных решений. Простое скрещивание не 
слишком часто уничтожает схемы с малым охватом, однако ликвиди-
рует схемы с достаточно большим охватом. Однако невзирая на 
губительность операций скрещивания и мутации для схем высокого 
порядка и охвата, количество обрабатываемых схем настолько велико, 
что даже при относительно низком количестве хромосом в популяции 
достигаются весьма неплохие результаты выполнения генетического 
алгоритма.
Количество эффективно обрабатываемых схем, рассчитанное 
Холландом , составляет 
O
(N
3
). Это означает, что для популяции 
мощностью 
N 
количество обрабатываемых в каждом поколении схем 
имеет порядок N
3
.