www.wikidata.uk-ua.nina.az

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

Теорема схем

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

Схеми Редагувати

Під схемою розумітимемо підмножину простору генотипів . Якщо елементами є бінарні рядки , тоді дозволивши приймати деяким компонентам рядка довільні значення, а решті тільки 0 або 1, отримуємо схему або шаблон. Наприклад: . Елементами підмножини, яку представляє цей шаблон тоді будуть , , та . Довільну схема може бути описана за допомогою трьох показників: визначальної довжини , порядку та значення функції пристосованості. Припустімо, що (відповідно ) - функція, що повертає номер позиції у схемі першого (відповідно останнього) фіксованого елемента . Тоді визначальна довжина дорівнює . Порядком називається кількість фіксованих елементів у схемі.

Неформальне формулювання Редагувати

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

Теорема Редагувати

Голланд у своїй книзі «Adaptation in Natural and Artificial Systems» подає зв'язок між часткою популяції, що представляє схему у поточному поколінні та часткою у наступному поколінні у такому вигляді:

,

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

Див. також Редагувати

Посилання Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Teorema shem angl Schema Theorem inshi nazvi teorema shabloniv shemi shim fundamentalna teorema genetichnih algoritmiv persha teorema yaka obgruntovuvala efektivnist genetichnih algoritmiv Zaproponovana Dzhonom G Gollandom Cya teorema poyasnyuye chomu dlya pevnih zadach pevnij klas genetichnih algoritmiv ye efektivnim U danij moment vidomo dekilka teorem shem yaki obgruntovuyut efektivnist inshih klasiv algoritmiv zokrema teoremi shem dlya genetichnogo programuvannya Zmist 1 Shemi 2 Neformalne formulyuvannya 3 Teorema 4 Div takozh 5 PosilannyaShemi RedaguvatiPid shemoyu 3 displaystyle xi nbsp rozumitimemo pidmnozhinu prostoru genotipiv G displaystyle G nbsp Yaksho elementami G displaystyle G nbsp ye binarni ryadki x displaystyle x nbsp todi dozvolivshi prijmati deyakim komponentam ryadka dovilni znachennya a reshti tilki 0 abo 1 otrimuyemo shemu abo shablon Napriklad 1 0 displaystyle 1 0 nbsp Elementami pidmnozhini yaku predstavlyaye cej shablon todi budut 1000 displaystyle 1000 nbsp 1010 displaystyle 1010 nbsp 1100 displaystyle 1100 nbsp ta 1110 displaystyle 1110 nbsp Dovilnu shema mozhe buti opisana za dopomogoyu troh pokaznikiv viznachalnoyi dovzhini l 3 displaystyle l xi nbsp poryadku ta znachennya funkciyi pristosovanosti Pripustimo sho l i 3 displaystyle li xi nbsp vidpovidno h i 3 displaystyle hi xi nbsp funkciya sho povertaye nomer poziciyi u shemi pershogo vidpovidno ostannogo fiksovanogo elementa 3 displaystyle xi nbsp Todi viznachalna dovzhina dorivnyuye l 3 h i 3 l i 3 displaystyle l xi hi xi li xi nbsp Poryadkom nazivayetsya kilkist fiksovanih elementiv u shemi Neformalne formulyuvannya RedaguvatiKorotki malogo poryadku ta vishim za serednij u potochnij populyaciyi pristosovanistyu fitnesom shemi vidomi takozh yak budivelni bloki zapovnyuyut u eksponencijno zrostayuchij kilkosti nastupni populyaciyi genetichnogo algoritmu Teorema RedaguvatiGolland u svoyij knizi Adaptation in Natural and Artificial Systems podaye zv yazok mizh chastkoyu P 3 t displaystyle P xi t nbsp populyaciyi sho predstavlyaye shemu 3 displaystyle xi nbsp u potochnomu pokolinni t displaystyle t nbsp ta chastkoyu P 3 t 1 displaystyle P xi t 1 nbsp u nastupnomu pokolinni t 1 displaystyle t 1 nbsp u takomu viglyadi P 3 t 1 1 P c l 3 l 1 1 P 3 t m 3 t m t P 3 t 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 nbsp de P c displaystyle P c nbsp chastka populyaciyi sho piddayetsya krosoveru l 3 displaystyle l xi nbsp viznachalna dovzhina shemi 3 displaystyle xi nbsp m 3 t displaystyle widehat mu xi t nbsp serednye znachennya funkciyi pristosovanosti dlya binarnih ryadkiv zi shemoyu viglyadu 3 displaystyle xi nbsp m t displaystyle widehat mu t nbsp serednye znachennya funkciyi pristosovanosti dlya vsiyeyi populyaciyi binarnih ryadkiv Div takozh RedaguvatiLiles W C Introduction to Schema Theory A survey lecture of pessimistic amp exact schema theory W C Liles Wiegand R P 2002 Summer Lecture Series EC lab Activities Computer Science Department George Mason University tekst lekciyi Arhivovano 7 zhovtnya 2008 u Wayback Machine slajdi do lekciyi Arhivovano 24 sichnya 2011 u Wayback Machine Posilannya RedaguvatiJ 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 Otrimano z https uk wikipedia org w index php title Teorema shem amp oldid 35081755