Теорема схем

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

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

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