Hollandi skeemiteoreem
Hollandi skeemiteoreem, mida nimetatakse ka geneetiliste algoritmide fundamentaalseks teoreemiks, on ebavõrdsus, mis tuleneb evolutsioonilise dünaamika võrrandi jämedakujundamisest. Skeemiteoreem ütleb, et lühikesed, madalama astme skeemid, mille sobivus on üle keskmise, suurenevad järjestikuste põlvkondade jooksul eksponentsiaalselt. Teoreemi pakkus välja John Holland 1970. aastatel. Algselt peeti seda laialdaselt geneetiliste algoritmide võimsuse selgituste aluseks. Seda tõlgendust on siiski kritiseeritud mitmes publikatsioonis, mida on vaadatud dokumendis , kus näidatakse, et skeemiteoreem on Price'i võrrandi erijuhtum, kus makroskoopilise mõõdupuuna on skeemindikaatorfunktsioon.
Skeem on mall, mis identifitseerib teatud stringide positsioonidel sarnaste stringide alamhulga. Skeemid on silindriliste kogude erijuhtum ja moodustavad seega topoloogilise ruumi.
Kirjeldus
Vaatleme binaarsed stringid pikkusega 6. Skeem 1*10*1 kirjeldab kõikide stringide kogumit pikkusega 6, mille positsioonidel 1, 3 ja 6 on 1 ja positsioonil 4 on 0. * on jokersümbol, mis tähendab, et positsioonid 2 ja 5 võivad olla kas 1 või 0. Skeemi o ( H ) {\displaystyle o(H)}
järjekord on määratletud kui fikseeritud positsioonide arv šabloonis, samas kui defineeriv pikkus δ ( H ) {\displaystyle \delta (H)}
on esimese ja viimase konkreetse positsiooni vaheline kaugus. Järjekord 1*10*1 on 4 ja selle defineeriv pikkus on 5. Skeemi sobivus on kõigi skeemile vastavate stringide keskmine sobivus. Stringi sobivus on kodeeritud probleemilahenduse väärtuse mõõt, mis arvutatakse probleemispetsiifilise hindamisfunktsiooni abil. Kasutades geneetiliste algoritmide väljakujunenud meetodeid ja geneetilisi operaatoreid, väidab skeemiteoreem, et lühikesed, madalama järjestusega skeemid, mille sobivus on üle keskmise, kasvavad järjestikuste põlvkondade jooksul eksponentsiaalselt. Väljendatuna võrrandina:
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]. } ![{\displaystyle \operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p].}](https://www.alegsaonline.com/image/37ac2d707cc2a474ad365dd53141be94ecad43de.svg)
Siin m ( H , t ) {\displaystyle m(H,t)}
on skeemi H {\displaystyle H}
kuuluvate stringide arv põlvkonna t {\displaystyle t} juures. 
, f ( H ) {\displaystyle f(H)}
on skeemi H {\displaystyle H} täheldatud keskmine sobivus ja a t {\displaystyle a_{t}}
on täheldatud keskmine sobivus põlvkonnas t {\displaystyle t} . Katkestuse tõenäosus p {\displaystyle p}
on tõenäosus, et ristumine või mutatsioon hävitab skeemi H {\displaystyle H} . Seda saab väljendada järgmiselt:
p = δ ( H ) l - 1 p c + o ( H ) p m {\displaystyle p={\delta (H) \over l-1}p_{c}+o(H)p_{m}}} 
kus o ( H ) {\displaystyle o(H)} on skeemi järjestus, l {\displaystyle l}
on koodi pikkus, p m {\displaystyle p_{m}}
on mutatsiooni tõenäosus ja p c {\displaystyle p_{c}}
on ristumise tõenäosus. Seega on lühema määratluspikkusega δ ( H ) {\displaystyle \delta (H)} skeemi puhul väiksem tõenäosus, et see katkeb.
Tihti mõistetakse valesti, miks skeemiteoreem on ebavõrdsus, mitte võrdsus. Vastus on tegelikult lihtne: teoreem jätab tähelepanuta väikese, kuid mitte nullist tuleneva tõenäosuse, et skeemi H {\displaystyle H} kuuluv string luuakse "nullist" ühe stringi mutatsiooniga (või kahe stringi rekombinatsiooniga), mis eelmises põlvkonnas ei kuulunud skeemi H {\displaystyle H} . See tähendab, et skeemi H {\displaystyle H} ei ole võimalik luua.
Piirangud
Skeemiteoreem kehtib eeldusel, et geneetiline algoritm säilitab lõpmatult suure populatsiooni, kuid see ei kehti alati (piiratud) praktikas: algpopulatsiooni valimisvea tõttu võivad geneetilised algoritmid konvergeeruda skeemidele, millel puudub selektiivne eelis. See juhtub eelkõige multimodaalse optimeerimise puhul, kus funktsioonil võib olla mitu tippu: populatsioon võib triivida eelistama ühte tippu, ignoreerides teisi.
Põhjus, miks skeemiteoreem ei saa seletada geneetiliste algoritmide võimsust, on see, et see kehtib kõigi probleemiinstrumentide puhul ja ei suuda eristada probleeme, mille puhul geneetilised algoritmid töötavad halvasti, ja probleeme, mille puhul geneetilised algoritmid töötavad hästi.
Multimodaalse funktsiooni graafik kahes muutujas.
Küsimused ja vastused
K: Mis on Hollandi skeemiteoreem?
V: Hollandi skeemiteoreem on geneetiliste algoritmide kohta käiv teoreem, mis ütleb, et keskmisest kõrgema sobivusega isendid on tõenäolisemad.
K: Kes ja millal pakkus välja Hollandi skeemiteoreemi?
V: John Holland esitas Hollandi skeemiteoreemi 1970. aastatel.
K: Mis on skeem geneetiliste algoritmide kontekstis?
V: Geneetiliste algoritmide kontekstis on skeem malli, mis identifitseerib stringide alamhulga, millel on sarnasused teatud stringipositsioonidel.
K: Kuidas tõlgendatakse Hollandi skeemiteooriat, mida kasutati geneetiliste algoritmide võimsuse selgitamise alusena?
V: Holland'i skeemiteoreemi tõlgendus, mida kasutati geneetiliste algoritmide võimsuse seletuste alusena, on see, et keskmisest kõrgema sobivusega isendid on tõenäolisemalt ülekaalus.
K: Mida on Holland'i skeemiteoreemi kriitika näidanud?
V: Hollandi skeemiteoreemi kriitika on näidanud, et see on Price'i võrrandi erijuhtum, mille makroskoopiline mõõtühik on skeemindikaatorfunktsioon.
K: Mis on silindriliste kogude erijuhtum?
V: Skeemid on silindriliste hulkade erijuhtum.
K: Millise ruumi moodustavad skeemid?
V: Skeemid moodustavad topoloogilise ruumi.
