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

 
S имеет приспособленность на 
ε
% выше
 
средней, т.е.
F(S,k) = 
F
(k) + ε
F
(k),
(3.14)

то при подстановке выражения (3.12) в неравенство (3.11) в предпо-
ложении, что 
ε
не изменяется во времени, при старте от
k 
= 0 получаем
c(S, k) = c(S, 
0)(1 
+ ε)
к
,
ε = (F(S,k)- 
F
(k))/ 
F
(k),
(3.15)
т.е. 
ε
> 0 для схемы с приспособленностью выше средней и 
ε
< 0 - в 
противном случае.
Равенство (3.15) описывает геометрическую прогрессию. Из этого 
следует, что в процессе репродукции схемы, оказавшиеся лучше (хуже) 
средних, выбираются на очередных итерациях генетического 
алгоритма в показательно возрастающих (убывающих) количествах. 
Обратим внимание, что зависимости (3.9) - (3.13) основаны на 

---

А.Е. Кононюк Дискретно-непрерывная математика 
136 
предположении, что функция приспособленности 
F 
принимает только 
положительные значения. При использовании генетических алгорит-
мов для решения оптимизационных задач, в которых целевая функция 
может принимать и отрицательные значения, необходимы некоторые 
дополнительные соотношения между оптимизируемой функцией и 
функцией приспособленности. Конечный результат, получаемый из 
выражений (3.10) - (3.12), можно сформулировать в форме теоремы. 
Это основная теорема генетических алгоритмов, иначе называемая 
теоремой о схемах 
.
Теорема 3.1
Схемы малого порядка, с малым охватом и с приспособленностью 
выше средней формируют показательно возрастающее количество 
своих представителей в последующих поколениях генетического 
алгоритма.
В соответствии с приведенной теоремой важным вопросом становится 
кодирование, которое должно обеспечивать построение схем малого 
порядка, с малым охватом и с приспособленностью выше средней. 
Косвенным результатом теоремы 3.1 (о схемах) можно считать 
следующую гипотезу, называемую 
гипотезой о кирпичиках 
(либо о 
строительных блоках)
.