Hollandin skeemateoreema

Kuvaus

Tarkastellaan binäärisiä merkkijonoja, joiden pituus on 6. Skeema 1*10*1 kuvaa kaikkien sellaisten merkkijonojen joukkoa, joiden pituus on 6 ja joiden kohdissa 1, 3 ja 6 on 1 ja kohdassa 4 on 0. * on jokerimerkki, mikä tarkoittaa, että paikoissa 2 ja 5 voi olla arvo joko 1 tai 0. Skeeman o ( H ) {\displaystyle o(H)} järjestys määritellään mallin kiinteiden paikkojen lukumääräksi, kun taas määrittelypituus δ ( H ) {\displaystyle \delta (H)} on ensimmäisen ja viimeisen tietyn paikan välinen etäisyys. Järjestys 1*10*1 on 4 ja sen määrittelypituus on 5. Skeeman kunto on kaikkien skeemaa vastaavien merkkijonojen keskimääräinen kunto. Merkkijonon kunto on koodatun ongelman ratkaisun arvon mitta, joka lasketaan ongelmakohtaisella arviointifunktiolla. Geneettisten algoritmien vakiintuneiden menetelmien ja geneettisten operaattoreiden avulla skeemateorema toteaa, että lyhyet, matala-asteiset skeemat, joiden fitness on keskimääräistä parempi, kasvavat eksponentiaalisesti peräkkäisissä sukupolvissa. Yhtälönä ilmaistuna:

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]. }

Tässä m ( H , t ) {\displaystyle m(H,t)} on niiden merkkijonojen lukumäärä, jotka kuuluvat skeemaan H {\displaystyle H} sukupolvella t {\displaystyle t}. , f ( H ) {\displaystyle f(H)} on skeeman H {\displaystyle H} havaittu keskimääräinen kunto ja a t {\displaystyle a_{t}} on havaittu keskimääräinen kunto sukupolvella t {\displaystyle t} . Häiriötodennäköisyys p {\displaystyle p} on todennäköisyys sille, että risteytys tai mutaatio tuhoaa skeeman H {\displaystyle H} . Se voidaan ilmaista seuraavasti:

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

jossa o ( H ) {\displaystyle o(H)} on skeeman järjestys, l {\displaystyle l} on koodin pituus, p m {\displaystyle p_{m}} on mutaation todennäköisyys ja p c {\displaystyle p_{c}} on risteytyksen todennäköisyys. Siten skeema, jonka määrittelypituus δ ( H ) {\displaystyle \delta (H)} on lyhyempi, häiriintyy harvemmin.
Usein väärinymmärretty seikka on se, miksi skeemateoreema on epätasa-arvo eikä tasa-arvo. Vastaus on itse asiassa yksinkertainen: teoreema jättää huomiotta sen pienen, mutta nollasta poikkeavan todennäköisyyden, että skeemaan H {\displaystyle H} kuuluva merkkijono syntyy "tyhjästä" mutaation kautta yhdestä merkkijonosta (tai kahden merkkijonon rekombinaatiosta), joka ei edellisessä sukupolvessa kuulunut skeemaan H {\displaystyle H} .

Rajoitus

Skeemateoreema pätee olettaen, että geneettinen algoritmi ylläpitää äärettömän suurta populaatiota, mutta se ei aina siirry (äärelliseen) käytäntöön: alkupopulaation otantavirheen vuoksi geneettiset algoritmit voivat konvergoitua skeemoihin, joilla ei ole valikoivaa etua. Näin tapahtuu erityisesti multimodaalisessa optimoinnissa, jossa funktiolla voi olla useita huippuja: populaatio voi ajautua suosimaan yhtä huippua ja jättää muut huomiotta.

Syy siihen, että skeemateoreema ei voi selittää geneettisten algoritmien tehoa, on se, että se pätee kaikkiin ongelmatapauksiin eikä sillä voida erottaa toisistaan ongelmia, joissa geneettiset algoritmit suoriutuvat huonosti, ja ongelmia, joissa geneettiset algoritmit suoriutuvat hyvin.

Monimodaalisen funktion kuvaaja kahdella muuttujalla.