Page 56 - 4521

кладами H.
Вірогідність того, що одноточковий кросинговер зруй-
нує шиму рівна вірогідності того, що точка розриву потрапить
між певними бітами. Вірогідність же того, що H «переживає»
кросинговер не менша 1 p c  (H / ) J  , 1 де p — вірогід-
c
ність кросинговера. Ця вірогідність — нерівність, оскільки ши-
ма зможе вижити, якщо в кросинговері також брав участь при-
клад подібної шими.
Вірогідність того, що H переживе точкову мутацію —
1 p  o (H ) , де p m — вірогідність мутації. Цей вираз можна
m
апроксимувати як 1(  o (H )) для малих p m і о(H). Створення
очікуваного число відборів і вірогідності виживання відомо як
теорема шим:
f (H ) ,t   (H )
m  ,tH   1  m (H ) ,t 1 p 1 (  p ) o (H )

f ) (t  c l  1  m (4.3)

Теорема шим показує, що будівельні блоки ростуть по
експоненті, у той час шими з пристосованістю нижче серед-
ньою розпадаються з тією ж швидкістю. Голдберг в своїх до-
слідженнях теореми шим висуває гіпотезу будівельних блоків,
яка полягає в тому, що «будівельні блоки об'єднуються, щоб
сформувати кращі рядки» (див. [6]). Тобто рекомбінація і екс-
поненціальне зростання будівельних блоків веде до формуван-
ня кращих будівельних блоків.
Тоді як теорема шим передбачає зростання прикладів хо-
роших шим, сама теорема вельми спрощено описує поведінку
ГА. Перш за все, f(H) і fср не залишаються постійними від по-
коління до покоління. По-друге, теорема шим пояснює втрати
шим, але не появу нових. Нові шими часто створюються кро-
синговером і мутацією. Крім того, в результаті еволюції члени
популяції стають все більш і більш схожими один на одного
так, що зруйновані шими будуть відразу ж відновлені. Нареш-
ті, доведення теореми шим побудоване на елементах теорії
вірогідності і, отже, не враховує розкид значень. У багатьох

55