Hollandov teorem o shemi

Hollandov izrek o shemi, imenovan tudi temeljni izrek genetskih algoritmov, je neenakost, ki izhaja iz grobe graščine enačbe za evolucijsko dinamiko. Izrek o shemi pravi, da se kratke sheme nizkega reda z nadpovprečno dobrimi lastnostmi v zaporednih generacijah eksponentno povečujejo. Izrek je predlagal John Holland v sedemdesetih letih prejšnjega stoletja. Sprva so ga mnogi imeli za temelj razlag moči genetskih algoritmov. Vendar je bila ta razlaga njegovih posledic kritizirana v več publikacijah, pregledanih v , kjer je prikazano, da je izrek o shemi poseben primer Priceove enačbe s funkcijo indikatorja sheme kot makroskopsko meritvijo.

Shema je predloga, ki določa podmnožico nizov s podobnostmi na določenih mestih nizov. Sheme so poseben primer cilindričnih množic in zato tvorijo topološki prostor.

Opis

Upoštevajte binarne nize dolžine 6. Shema 1*10*1 opisuje množico vseh nizov dolžine 6 z 1 na položajih 1, 3 in 6 ter 0 na položaju 4. Znak * je nadomestni simbol, kar pomeni, da imata lahko položaja 2 in 5 vrednost 1 ali 0. Vrstni red sheme o ( H ) {\displaystyle o(H)} $o(H)$ je opredeljen kot število fiksnih položajev v predlogi, medtem ko je definicijska dolžina δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ razdalja med prvim in zadnjim določenim položajem. Vrstni red 1*10*1 je 4, njegova definicijska dolžina pa 5. Primernost sheme je povprečna primernost vseh nizov, ki ustrezajo shemi. Primernost niza je merilo vrednosti kodirane rešitve problema, kot jo izračuna za problem specifična ocenjevalna funkcija. Z uporabo uveljavljenih metod in genetskih operatorjev genetskih algoritmov izrek o shemi pravi, da se kratke sheme nizkega reda z nadpovprečnim fitnesom v zaporednih generacijah eksponentno povečujejo. Izražen kot enačba:

E ( m ( H , t + 1 ) ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] . {\displaystyle \operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p]. } $\operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p].$

Pri tem je m ( H , t ) {\displaystyle m(H,t)} $m(H,t)$ število nizov, ki pripadajo shemi H {\displaystyle H} $H$ v generaciji t {\displaystyle t} $t$ , f ( H ) {\displaystyle f(H)} $f(H)$ je opazovana povprečna primernost sheme H {\displaystyle H} $H$ in a t {\displaystyle a_{t}} $a_{t}$ je opazovana povprečna primernost v generaciji t {\displaystyle t} $t$ . Verjetnost prekinitve p {\displaystyle p} $p$ je verjetnost, da bosta križanje ali mutacija uničila shemo H {\displaystyle H} $H$ . Lahko jo izrazimo kot:

p = δ ( H ) l - 1 p c + o ( H ) p m {\displaystyle p={\delta (H) \over l-1}p_{c}+o(H)p_{m}} $p={\delta (H) \over l-1}p_{c}+o(H)p_{m}$

kjer je o ( H ) {\displaystyle o(H)} $o(H)$ vrstni red sheme, l {\displaystyle l} $l$ dolžina kode, p m {\displaystyle p_{m}} $p_{m}$ verjetnost mutacije in p c {\displaystyle p_{c}} $p_{c}$ verjetnost križanja. Zato je verjetnost, da bo shema s krajšo definicijsko dolžino δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ prekinjena, manjša.
Pogosto napačno razumljena točka je, zakaj je izrek o shemi neenakost in ne enakost. Odgovor je pravzaprav preprost: izrek zanemarja majhno, a ne ničelno verjetnost, da bo niz, ki pripada shemi H {\displaystyle H} $H$ , nastal "iz nič" z mutacijo enega samega niza (ali rekombinacijo dveh nizov), ki v prejšnji generaciji ni pripadal H {\displaystyle H} . $H$

Omejitev

Izrek o shemah velja ob predpostavki genetskega algoritma, ki vzdržuje neskončno veliko populacijo, vendar se ne prenese vedno na (končno) prakso: zaradi napake pri vzorčenju v začetni populaciji lahko genetski algoritmi konvergirajo k shemam, ki nimajo selektivne prednosti. To se zgodi zlasti pri multimodalni optimizaciji, kjer ima lahko funkcija več vrhov: populacija lahko začne dajati prednost enemu od vrhov, druge pa zanemarja.

Razlog, da teorem o shemi ne more pojasniti moči genetskih algoritmov, je v tem, da velja za vse primere problemov in ne more razlikovati med problemi, pri katerih genetski algoritmi delujejo slabo, in problemi, pri katerih genetski algoritmi delujejo dobro.

Graf multimodalne funkcije v dveh spremenljivkah.

Vprašanja in odgovori

V: Kaj je Hollandov teorem o shemi?

O: Hollandov teorem o shemi je teorem o genetskih algoritmih, ki pravi, da je večja verjetnost, da bodo prevladali posamezniki, katerih fitnes je višji od povprečja.

V: Kdo in kdaj je predlagal Hollandov teorem o shemi?

O: John Holland je Hollandov teorem sheme predlagal v sedemdesetih letih prejšnjega stoletja.

V: Kaj je shema v kontekstu genetskih algoritmov?

O: V kontekstu genetskih algoritmov je shema predloga, ki določa podmnožico nizov s podobnostmi na določenih pozicijah nizov.

V: Kakšna je razlaga Hollandovega teorema o shemi, ki je bil uporabljen kot temelj za razlage moči genetskih algoritmov?

O: Razlaga Hollandovega teorema o shemi, ki je bil uporabljen kot temelj za razlage moči genetskih algoritmov, je, da imajo posamezniki, katerih fitnes je višji od povprečja, večjo verjetnost, da bodo prevladali.

V: Kaj je pokazala kritika Hollandovega teorema o shemi?

O: Kritika Hollandovega teorema o shemi je pokazala, da je poseben primer Priceove enačbe s funkcijo indikatorja sheme kot makroskopsko meritvijo.

V: Kaj je poseben primer valjastih množic?

O: Sheme so poseben primer valjastih množic.

V: Kakšno vrsto prostora tvorijo sheme?

O: Sheme tvorijo topološki prostor.