Теорема схем англ Schema Theorem інші назви теорема шаблонів схеми шим фундаментальна теорема генетичних алгоритмів перш

Теорема схем (англ. 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. текст лекції [ 7 жовтня 2008 у Wayback Machine.] слайди до лекції [ 24 січня 2011 у Wayback Machine.]

Посилання

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.