Генетические алгоритмы (ГА) выражают эволюцию популяции хромосом в направлении от начального поколения к окрестностям экстремума. Обоснование этого положения содержится в основной теореме генетического подхода – теореме шаблонов, называемой также schemata theorem, теоремой схем или теоремой Д.Холланда. Теорема шаблонов получена Д.Холландом применительно к условиям так называемого канонического ГА.
Канонический генетический алгоритм характеризуется следующими особенностями:
В теореме Д.Холланда вводится понятие шаблона (схемы), шаблон определяется как совокупность фиксированных значений генов в определенных локусах. Например, в хромосоме с десятью генами один из шаблонов , включающая единицы в 4-м и 8-м локусах и ноль в 7-м локусе, может быть записан в виде
= ***1**01** (1)
где * обозначает позиции, не входящие в шаблон.
Обозначим число экземпляров шаблона в поколении с номером через (, ). Введем также следующие обозначения:
— размер (число хромосом) популяции; — множество номеров членов популяции, в хромосомах которых имеется шаблон ; () — длина шаблона , т.е. расстояние (число позиций) между крайними локусами шаблона, так, в случае (1) имеем () = 4; () — порядок шаблона (число локусов в ), в примере (1) порядок равен 3; — длина хромосомы.
Тогда в задачах минимизации, если выбор родителей осуществляется по правилу колеса рулетки, то число шаблонов , усредненное по актам выбора родителей, в выбираемых родительских хромосомах равно
=
Очевидно, что
()=()/(, )
=)/
где () есть усредненная полезность экземпляров с шаблоном , а — усредненная полезность всех экземпляров популяции в поколении . Поэтому
= (, ) ()/.
При простом одноточечном кроссовере в хромосому потомка шаблон попадет (т.е. не будет разорвана) с вероятностью
()/(-1).
При мутации, происходящей с вероятностью для каждой позиции, вероятность сохранения схемы , определяемая как (1 — )u(H), приблизительно равна 1 — ().
Поэтому вероятность выживания схемы равна
= (1 — ()/(-1)) (1-()) = 1 — ()/(-1) — (),
где — вероятность кроссовера.
Окончательно имеем приближенное равенство
(, +1) = (, ) ()/.
Следовательно, число шаблонов из хромосом перспективных родителей (>), имеющих лучшие значения функции полезности, увеличивается в генотипах популяции от поколения к поколению по показательному закону
(, ) = (, 0) ( ()/)t, (2)
Скорость роста (, ) тем выше, чем больше () и чем меньше длина () и порядок () шаблона .
Отметим следующее:
1) Выражение (2) описывает лишь некоторую тенденцию к росту (, ), поскольку ()/ меняется от поколения к поколению. Рост (, ) прекращается, когда наступает стагнация, при которой () = .
2) В (2) кроссовер рассматривается как фактор, разрушающий шаблоны, и не учитывается возможность формирования в хромосомах потомков шаблонов, отсутствовавших в хромосомах родителей. Возможность формирования некоторого полезного шаблона у потомков при отсутствии такового у родителей называют потенцалом рекомбинации.
Список литературы
1. Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. — Addison-Welsey, 1989.