Теорема схем

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

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

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

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

${\displaystyle 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)}$,

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