Введение в эволюционное моделирование. Каширина И.Л. - 15 стр.

                                    15
      бями и потомками.
  •   Используется половинный однородный кроссовер (HUX).
  •   Макромутация при перезапуске.
                 3. Теорема схем (шим, шаблонов)
      Схемой (шимой) называется строка вида (s1, s2, ..., si, ..., sn), si ∈
{0,1,*}. Символом "*" в некотором разряде обозначается то, что там может
быть как 1, так и 0. Например, для двух бинарных строк "111000111000" и
"110011001100"     схема     будет    выглядеть   следующим       образом:
"11*0****1*00". Т.е. с помощью схем можно как бы выделять общие участ-
ки двоичных строк и маскировать различия. Имея в составе схемы m симво-
лов "*" можно закодировать (обобщить) 2m двоичных строк. Так, например,
схема "01*0*1" описывает набор строк {"010001", "010011", "011001",
"011011"}.
Опеределяющей длиной схемы называется расстояние между двумя край-
ними символами "0" и/или "1". Для схемы "01*0*1" определяющая длина
равна 5, а для схемы "**0**1*" определяющая длина равна 3. Порядок схе-
мы � � это ещё одна характеристика схемы, она равна числу фиксирован-
ных позиций в строке, т.е. общему числу "0" и "1". Для схем "01*0*1" и
"**0**1*" порядки равны 4 и 2 соответственно.
Хотя внешне кажется, что ГА обрабатывает строки, на самом деле при этом
неявно происходит обработка схем, которые представляют шаблоны подо-
бия между строками (Гольдберг, 1989; Холланд, 1992). ГА практически не
может заниматься полным перебором всех представлений в пространстве
поиска. Однако он может производить выборку значительного числа гипер-
плоскостей в областях поиска с высокой приспособленностью. Каждая такая
гиперплоскость соответствует множеству похожих строк с высокой приспо-
собленностью.
Строящие блоки (Goldberg, 1989) � � это схемы, обладающие:
   • высокой приспособленностью,
   • низким порядком,
   • короткой определяющей длиной.
Приспособленность схемы определяется как среднее приспособленностей
строк, которые ее содержат. После процедуры отбора остаются только стро-
ки с более высокой приспособленностью. Следовательно, строки, которые
являются примерами схем с высокой приспособленностью, выбираются ча-
ще. Кроссовер реже разрушает схемы с более короткой определенной дли-
ной, а мутация реже разрушает схемы с низким порядком. Поэтому такие
схемы имеют больше шансов переходить из поколения в поколение. Хол-
ланд (1992) показал, что, в то время как ГА явным образом обрабатывает n
строк на каждом поколении, в то же время неявно обрабатываются порядка