Věta o obvodu

Scheme teorém , nebo šablona teorém - hlavní teorém teorie genetických algoritmů , dávat zdůvodnění pro jejich efektivitu. Poprvé formulován a ověřen J. Hollandem v roce 1975.

Koncept schématu

Schéma je podmnožinou množiny všech možných genotypů , které jsou možné v dané populaci , daný jako chromozom s pevnými hodnotami některých bitů . Zbytek bitů může mít libovolnou hodnotu a tvoří příklady schématu. Příklady schématu 00**1* jsou tedy chromozomy 000010, 000011, 000110, 000111, 001010, 001011, 001110 a 001111. Počet pevných bitů se nazývá pořadí mezi extrémními pozicemi a pevná vzdálenost tj. rozdíl mezi jejich čísly) se nazývá jeho definující délka. Pořadí výše uvedeného okruhu je 3 a definující délka je 5 - 1 = 4. Fitness funkce (FF) okruhu je průměrná hodnota fitness funkce všech jeho příkladů.

Věta

Věta o schématu ukazuje exponenciální šíření dobře adaptovaných schémat s malým řádem a definující délkou, ke kterému dochází při změně generací (taková schémata s FP vyšším než je průměr pro populaci se nazývají stavební bloky ). Matematicky je to vyjádřeno nerovností:

N(h,t+1)\geq N(h,t){f(h,t) \over f(t)}[1-p].

Zde je počet příkladů obvodu h v kroku t a je stejný v dalším kroku; je funkce vhodnosti obvodu v kroku t; je průměrná hodnota FF pro celou populaci ve stejném kroku; je pravděpodobnost zničení schématu působením genetických operátorů. Tato pravděpodobnost je: $N(h,t)$ $N(h,t+1)$ $f(h,t)$ $f(t)$ $p$

p={\delta (h) \over l-1}p_{c}+o(h)p_{m},

kde je definující délka schématu, je pořadí, je pravděpodobnost křížení a je pravděpodobnost mutace . Úplná forma věty tedy vypadá takto: $\delta(h)$ $Ach)$ $p_{c}$ $odpoledne}$

N(h,t+1)\geq N(h,t){f(h,t) \over f(t)}[1-{\delta (h) \over l-1}p_{ c}-o(h)p_{m}].

Věta o schématu nedává přesné hodnoty, ale pouze spodní hranici počtu instancí schématu po příští generační výměně. To je způsobeno skutečností, že existuje možnost vzniku nových příkladů schématu působením genetických operátorů na chromozomy, které s ním dříve nesouvisely.

Viz také

genetický algoritmus

Odkazy

JH Holandsko. Adaptace v přírodních a umělých systémech . The MIT Press, reprint vydání, 1992.
Liles WC Úvod do teorie schémat: Průzkumná přednáška pesimistické a exaktní teorie schémat / WC Liles, Wiegand RP - 2002 série letních přednášek, Laboratoř EC Activities, Katedra informatiky, Univerzita George Masona. přednáškový text přednáškové snímky