Page 55 - 4521

4.5 Будівельні блоки
Будівельні блоки — це шими, що володіють:
 високою придатністю;
 низьким порядком;
 короткою певною довжиною.
Придатність шими визначається як середнє значення при-
стосованостей рядків-особин, які її містять. Після процедури
відбору залишаються тільки рядки з вищою придатністю. От-
же, рядки, які є прикладами шим з високою придатністю, ви-
бираються частіше. Кросинговер рідше руйнує шими з корот-
шою певною довжиною, а мутація рідше руйнує шими з низь-
ким порядком. Тому, такі шими мають більше шансів перехо-
дити з покоління в покоління. Холланд показав, що в той час,
як ГА явним чином обробляє n рядків на кожному поколінні,
3
неявно обробляються порядку n таких коротких шим низького
порядку із високою пристосованістю (корисних шим – useful
schemata (див. [8]) ). Він називав це явище неявним паралеліз-
мом (implicit parallelism). Для вирішення реальних завдань,
присутність неявного паралелізму означає, що велика популя-
ція має більше можливостей локалізувати рішення експоненці-
ально швидше за популяцію з меншим числом особин.

4.6 Теорема шим
Теорема шим (The schema theorem) показує, яким чином
проста ГА експоненціально збільшує число прикладів корис-
них шим або будівельних блоків, що приводить до знаходжен-
ня рішення початкової задачі.
Нехай m(H,t) — число прикладів шими H в t-ому поко-
лінні. Обчислимо очікуване число прикладів H в наступному
поколінні або m(H,t + 1) в термінах m(H,t). Проста ГА кожно-
му рядку при відборі ставить у відповідність вірогідність її
«виживання» пропорційно її пристосованості (наприклад, як в
методі рулетки). Очікується, що шима H може бути вибрана
m(H,t)(f(H) /fср) разів, де fср — середня придатність популяції,
а f(H) — середня придатність тих рядків в популяції, які є при-
54