Теорема схем

Теорема схем (англ. Schema Theorem) (інші назви: теорема шаблонів (схеми, шим), фундаментальна теорема генетичних алгоритмів) — перша теорема, яка обґрунтовувала ефективність генетичних алгоритмів. Запропонована Джоном Г. Голландом. Ця теорема пояснює, чому для певних задач певний клас генетичних алгоритмів є ефективним. У даний момент відомо декілька теорем схем, які обґрунтовують ефективність інших класів алгоритмів, зокрема теореми схем для генетичного програмування.

Схеми

Під схемою $\xi$ розумітимемо підмножину простору генотипів $G$. Якщо елементами $G$ є бінарні рядки $x$, тоді дозволивши приймати деяким компонентам рядка довільні значення, а решті тільки 0 або 1, отримуємо схему або шаблон. Наприклад: $1**0$. Елементами підмножини, яку представляє цей шаблон тоді будуть $1000$, $1010$, $1100$ та $1110$. Довільну схема може бути описана за допомогою трьох показників: визначальної довжини $l(\xi )$ , порядку та значення функції пристосованості. Припустімо, що $li(\xi )$ (відповідно $hi(\xi )$) - функція, що повертає номер позиції у схемі першого (відповідно останнього) фіксованого елемента $\xi$. Тоді визначальна довжина дорівнює $l(\xi )=hi(\xi )-li(\xi )$. Порядком називається кількість фіксованих елементів у схемі.

Неформальне формулювання

Короткі, малого порядку та вищим за середній у поточній популяції пристосованістю (фітнесом) схеми (відомі також як будівельні блоки) заповнюють у експоненційно зростаючій кількості наступні популяції генетичного алгоритму.

Теорема

Голланд у своїй книзі «Adaptation in Natural and Artificial Systems» подає зв'язок між часткою $P(\xi ,t)$ популяції, що представляє схему $\xi$ у поточному поколінні $t$ та часткою $P(\xi ,t+1)$ у наступному поколінні $t+1$ у такому вигляді:

$P(\xi ,t+1)\geq [1-P_{c}\cdot (l(\xi )/(l-1))(1-P(\xi ,t))]({\widehat {\mu }}_{\xi }(t)/{\widehat {\mu }}(t))P(\xi ,t)$,

де $P_{c}$ — частка популяції, що піддається кросоверу, $l(\xi )$ — визначальна довжина схеми $\xi$, ${\widehat {\mu }}_{\xi }(t)$ — середнє значення функції пристосованості для бінарних рядків зі схемою вигляду $\xi$, ${\widehat {\mu }}(t)$ — середнє значення функції пристосованості для всієї популяції бінарних рядків.

Див. також

• Liles W. C. Introduction to Schema Theory : A survey lecture of pessimistic & exact schema theory / W. C. Liles, Wiegand R. P. - 2002 Summer Lecture Series, EC lab Activities, Computer Science Department, George Mason University. текст лекції слайди до лекції

Посилання

• J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 1975.
• J. H. Holland. Adaptation in Natural and Artificial Systems. The MIT Press, reprint edition, 1992.