Теорема схем

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Теорема схем (англ. 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. текст лекції слайди до лекції

Посилання[ред.ред. код]