Page 53 - 4521

льову довжину. Наприклад, шина S = (* * *001 * 110) має по-
рядок о(S) = 6 і довжину δ(S) = 10 - 4 = 6.
Порядок і довжина шим використовуються для визна-
чення ймовірності мутації і кросинговера відповідно.
У зв'язку з тим, що більш пристосовані особини (хромо-
соми) описуються шимою з більшою пристосованістю, сенс
роботи ГА полягає в пошуку двійкового рядка певного виду зі
всієї безлічі бінарних рядків довжини m. Тоді простір пошуку
m
складає 2 рядків, а його розмірність рівна m. Шима відповідає
деякій гіперплощині в цьому просторі. Дане твердження мож-
на проілюструвати таким чином. Нехай розрядність хромосо-
3
ми рівна 3, тоді всього можна закодувати 2 = 8 рядків. Пред-
ставимо куб в тривимірному просторі. Позначимо вершини
цього куба трьохрозрядними бінарними рядками так, щоб міт-
ки сусідніх вершин відрізнялися рівно на один розряд, причо-
му вершина з міткою "000" знаходилася б на початку коорди-
нат (див. рис.4.3).
Якщо взяти шиму виду "**0", то вона опише ліву грань
куба, а шима "*10" — верхнє ребро цієї грані. Очевидно, що
шима "* * *" відповідає всьому простору. Якщо узяти двійкові
рядки довжиною 4 розряди, то розбиття простору шимами
можна зобразити на прикладі чотиривимірного куба з поіме-
нованими вершинами (див.рис.4.4). Тут шимі "*1**" відпові-
дає гіперплощина, що включає задні грані зовнішнього і внут-
рішнього куба, а шимі " ** 10" — гіперплощина з верхніми
ребрами лівих граней обох кубів. Таким чином терміни «гі-
перплощина» і «шима» взаємозамінні.

Рисунок 4.3 – Трьохмірний куб
52