Page 52 - 4521

4.4 Шима
Хоча зовні здається, що ГА обробляє рядки, насправді
при цьому неявно відбувається обробка шим, які представля-
ють шаблони подібності між рядками. ГА практично не може
займатися повним перебором всіх уявлень в просторі пошуку.
Проте він може проводити вибірку значного числа гіперпло-
щин в областях пошуку з високою пристосованістю. Кожна
така гіперплощина відповідає безлічі схожих рядків з високою
пристосованістю.
Шима (schema) — це рядок довжини J (що і довжина
будь-якого рядка популяції), що складається із знаків алфавіту
{0; 1; *}, де {*} — невизначений символ. Кожна шима визна-
чає безліч всіх бінарних рядків довжини J, що мають у відпо-
відних позиціях або 0, або 1, в залежності від того, який біт
знаходиться у відповідній позиції самої шими. Шима, що не
містить жодного невизначеного символу, є деяким рядком.
Шима з одним невизначеним символом описує два бінарні
рядки, а з двома — чотири рядки. Наприклад, шима, 10 * *1,
визначає собою множину з чотирьох п'ятибітових рядків
{10001; 10011; 10101; 10111}. Неважко відмітити, що шима з r-
r
невизначеними символами описує 2 бінарних рядків. З іншого
m
боку, кожний рядок довжини m описується 2 шимами. Отже,
в популяції з n таких рядків число можливих шим може дося-
m
гати n2 ! При цьому велика частина шим ймовірно буде менш
пристосована від інших, що може привести до епістазу. Тому
рекомендується створювати початкову популяцію з шим з
високою пристосованістю.
Всі шими різні між собою. Основними характеристика-
ми шин є порядок і довжина.
Порядок шими о(S) (order) — це число фіксованих бітів
(0 або 1) в шимі S.
Визначальна довжина δ(S) (defining length) — це від-
стань між першим і останнім фіксованими бітами в шимі S.
Довжина шими визначає концентрацію інформації в шимі.
Вважається, що шима з однією фіксованою позицією має ну-
51