Теорема шаблонов

Теорема шаблонов (The Schema Theorem), приведённая Холландом, показывает, как изменяется доля представителей шаблона в популяции, являясь первой попыткой объяснить правильность работы генетических алгоритмов. Следует заметить, что она верна только для классического ГА с его пропорциональным отбором и одноточечным кроссовером.

M (H, t) — число представителей шаблона H в поколении t.

Количество представителей шаблона H в промежуточном поколении:

где f(H, t) — приспособленность шаблона H в поколении t, а <f(t)> — средняя приспособленность поколения t.

Особи промежуточной популяции с вероятностью p_c подвергаются кроссоверу. Одноточечный кроссовер может разрушить шаблон – ни один из детей не является представителем рассматриваемого шаблона. Вероятность разрушения меньше, чем

 

где P(H, t) — доля представителей шаблона H в поколении t. Первый множитель произведения равен вероятности попадания точки раздела между фиксированными битами шаблона, а второй — вероятности выбрать в пару представителя другого шаблона.

Но даже в случае, когда второй родитель не является представителем данного шаблона, и точка раздела попадает между фиксированными битами, шаблон не обязательно разрушается. Например, рассматриваем шаблон 11***, кроссоверу подвергаются строки 11011 и 10100, точка раздела попадает между первыми двумя битами

1.1011 ->; 1. 1011 1.0100 1. 0100 Как видно, в этой ситуации шаблон не разрушается.

Переходя от количества представителей к их доле, получаем следующее неравенство:

Учтём влияние мутации. В шаблоне o(H) фиксированных битов, и каждый не будет инвертирован с вероятностью (1 − p_m). Откуда получаем итоговую формулу теоремы шаблонов:

 

· Полученное выражение не слишком удачно для анализа работы генетического алгоритма, т.к. в нём присутствует знак неравенства.

· Мы не учитывали случаи, когда рассматриваемый шаблон получается в результате кроссовера пары строк, не являющихся его представителями.

· Приспособленность шаблона и средняя приспособленность популяции быстро изменяются от поколения к поколению, поэтому полученное неравенство хорошо описывает ситуацию только для следующего поколения.

На данный момент существуют более точные версии этой теоремы и другие рассуждения, доказывающие целесообразность использования генетических алгоритмов.