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

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

---

А.Е. Кононюк Дискретно-непрерывная математика 
137 
обеспечивает генетическим алгоритмам явное преимущество перед 
другими традиционными методами, несомненно заключается в 
обработке большого количества различных схем.
Обратимся снова к примерам 1 и 2 и на их основе проанализируем 
обработку схем генетическим алгоритмом.
Пример 4.
В условиях примера 1 рассмотрим схему
S
0
= **********11
и покажем, как изменяется количество представителей этой схемы и 
приспособленность в процессе выполнения генетического алгоритма. 
Длина 
L 
= 12, а охват и порядок схемы S
0
составляют соответственно 
d(S
0
)=
1 и 
o(S
0
)
=2. В исходной популяции из примера 1 схеме S
0
соответствуют две следующие хромосомы:
сh
3
= [011101110011]
ch
7
= [101011011011]
Из формулы (3.10) следует, что после селекции и скрещивания 
количество хромосом, соответствующих схеме S
o
, должно быть больше 
или равно 2,5. Напомним, что вероятности скрещивания и мутации 
считаются равными соответственно р
с
= 1 и 
р
т
 = 
0. Приспособленность 
схемы S
o
в исходной популяции, обозначаемая 
F(S
0
, 
0), равна 8 и 
превышает среднюю приспособленность всех хромосом этой 
популяции F = 5,75, что легко рассчитать по формулам (3.6) - (3.8).
В примере 1 после селекции и скрещивания в новой популяции 
получены четыре хромосомы, соответствующие схеме S
o
:
Ch
1
= [001111011011]
Ch
3
= [111011011011]
Ch
7
= [011101011011]
Ch
8
= [101011110011]
Приспособленность схемы S
o
в новой популяции, т.е. 
F(S
0
, 
1), составит 
8,25, тогда как средняя приспособленность хромосом этой популяции 
F(1)=7, что также следует из формул (3.6) - (3.8). Новая популяция 
характеризуется 
большим 
средним 
значением 
функции 
приспособленности особей по сравнению с предыдущей (исходной) 
популяцией, что уже отмечалось в примере 1. Кроме того, в новой 
популяции приспособленность схемы S
o
оказывается лучшей, а коли-
чество представителей этой схемы - большим по сравнению с преды-
дущей популяцией.