Теорема схем
Теорема схем (англ. Schema Theorem) (інші назви: теорема шаблонів (схеми, шим), фундаментальна теорема генетичних алгоритмів) — перша теорема, яка обґрунтовувала ефективність генетичних алгоритмів. Запропонована Джоном Г. Голландом. Ця теорема пояснює, чому для певних задач певний клас генетичних алгоритмів є ефективним. У даний момент відомо декілька теорем схем, які обґрунтовують ефективність інших класів алгоритмів, зокрема теореми схем для генетичного програмування.
Схеми
Під схемою розумітимемо підмножину простору генотипів . Якщо елементами є бінарні рядки , тоді дозволивши приймати деяким компонентам рядка довільні значення, а решті тільки 0 або 1, отримуємо схему або шаблон. Наприклад: . Елементами підмножини, яку представляє цей шаблон тоді будуть , , та . Довільну схема може бути описана за допомогою трьох показників: визначальної довжини , порядку та значення функції пристосованості. Припустімо, що (відповідно ) - функція, що повертає номер позиції у схемі першого (відповідно останнього) фіксованого елемента . Тоді визначальна довжина дорівнює . Порядком називається кількість фіксованих елементів у схемі.
Неформальне формулювання
Короткі, малого порядку та вищим за середній у поточній популяції пристосованістю (фітнесом) схеми (відомі також як будівельні блоки) заповнюють у експоненційно зростаючій кількості наступні популяції генетичного алгоритму.
Теорема
Голланд у своїй книзі «Adaptation in Natural and Artificial Systems» подає зв'язок між часткою популяції, що представляє схему у поточному поколінні та часткою у наступному поколінні у такому вигляді:
,
де — частка популяції, що піддається кросоверу, — визначальна довжина схеми , — середнє значення функції пристосованості для бінарних рядків зі схемою вигляду , — середнє значення функції пристосованості для всієї популяції бінарних рядків.
Див. також
- 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.