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

3. 
Основы теории ГА 
Рассмотрим несколько теоретических фактов, которые помогут более 
чётко понять природу генетических алгоритмов и примерно объяснить, 
почему же они работают. 
3.1. Шаблоны 
Шаблоном
(
schema
) называется строка длины 
L
(т. е. той же длины, что 
и любая строка популяции), состоящая из символов {0, 1, *} (где * — 
«don't care» символ). Будем говорить, что строка является 
представителем данного шаблона, если в позициях, где знак шаблона 

---

А.Е. Кононюк Дискретно-непрерывная математика 
105 
равен 0 или 1, она имеет тот же символ. Например, у шаблона 01*0*110 
следующие представители:

01
0
0
0
110 

01
0
0
1
110 

01
1
1
0
110 

01
1
1
1
110 
Порядком
(
order
) шаблона называется количество фиксированных 
битов в нем. 
Определяющей длиной
(
defining length
) шаблона называется 
расстояние между его крайними фиксированными битами. Например, 
для шаблона *1***01* порядок 
o
= 3, а определяющая длина Δ = 5.
Очевидно, что количество представителей шаблона 
H
равно 2
L
−
o
(
H
)
, а 
количество шаблонов равно 3
L
(действительно, шаблоны — это строки, 
у которых на каждой позиции может находиться один из трех 
символов).
Если представить пространство поиска в виде гиперкуба, то строки это 
его вершины, а шаблон определяет в нем гиперплоскость. К примеру, 
шаблон **1 определяет правую грань этого трехмерного куба:
Поэтому термины «гиперплоскость» и «шаблон» взаимозаменяемы. 
Следующий рисунок изображает другое представление шаблонов:

---

А.Е. Кононюк Дискретно-непрерывная математика 
106 
На нем видно, что некоторые шаблоны имеют с среднем по всему 
пространству поиска большую приспособленность, чем другие.
Приспособленностью
шаблона называется средняя приспособленность 
строк из популяции, являющихся его представителями. Следует 
заметить, что эта величина зависит от популяции, и поэтому меняется 
со временем.

---

А.Е. Кононюк Дискретно-непрерывная математика 
107 
Внешне кажется, что генетический алгоритм при отборе выбирает 
строку, однако при этом неявным образом происходит выборка 
шаблонов, представителем которых она является. Это означает, что на 
каждом поколении количество представителей шаблона изменяется в 
соответствии с текущей приспособленностью этого шаблона. У 
«хороших» шаблонов представители в среднем более приспособленные, 
а значит, они чаще будут выбираться в промежуточную популяцию. 
«Плохие» шаблоны имеют много шансов вымереть. Одна строка 
является представителем сразу многих шаблонов (а именно 2
L
: на 
каждой позиции мы либо оставляем бит строки, либо заменяем его на 
«*»). Поэтому при отборе одной строки отбирается сразу целое 
множество шаблонов. Это явление получило название 
неявный 
параллелизм
(
implicit parallelism
).