Olando schemos teorema: apibrėžimas ir reikšmė genetiniuose algoritmuose

Olando schemos teorema, dar vadinama pagrindine genetinių algoritmų teorema, aprašo, kaip tam tikros bitų eilutės (ar kitos genotipo reprezentacijos) struktūros — vadinamos schemos — keičiasi per kartas atliekant atranką, kryžminimą ir mutaciją genetiniame algoritme. Teoremą XX a. aštuntajame dešimtmetyje pasiūlė Johnas Hollandas. Jos intencija buvo paaiškinti, kodėl trumpi, žemos eilės ir aukšto tinkamumo schemos gali daugintis populiacijoje ir taip sudaryti sudėtingus sprendimus iš paprastų fragmentų. Teorija ilgą laiką buvo laikoma pagrindine genetinių algoritmų galiai paaiškinti, tačiau vėlesnės analizės parodė, kad jos interpretacija turi ribotumų ir gali būti suprasta tik kaip apibūdinimas, o ne griežtas priežasties įrodymas.

Kas yra schema?

Schema — tai šablonas, apibrėžiantis genotipo pozicijų kombinaciją, kur tam tikrose pozicijose reikšmės yra užfiksuotos, o kitose paliekama „nepaisoma“ (dažnai žymima simboliu *). Pavyzdžiui, binarinėje eilutėje schema 1*0* reiškia visas eilutes, kurių pirmas bitas yra 1, trečias bitas — 0, o antras ir ketvirtas bet kokie. Schema apibrėžia tam tikrą eilučių aibę (poaibis), ir, taikant simbolinę topologiją, schemos dažnai laikomos cilindrinių aibių atveju, todėl jos gali būti analizuojamos kaip sudedamoji topologinė erdvė.

Matematinė išraiška (supaprastinta forma)

Schemas teorema pateikia nelygybę, kuri apytiksliai prognozuoja schemos populiacijose gausėjimą arba mažėjimą po vienos kartos, kai veikia atranka, kryžminimas ir mutacija. Tipinė supaprastinta forma rašoma taip:

m(H, t+1) ≥ m(H, t) * (f(H)/f̄) * (1 - p_c * (δ(H)/(l-1)) - p_m * o(H)),

m(H, t) — schemos H individų skaičius arba dažnis laike t,
f(H) — vidutinis schemos H tinkamumas,
f̄ — visos populiacijos vidutinis tinkamumas,
p_c — kryžminimo tikimybė,
p_m — vieno geno mutacijos tikimybė,
o(H) — schemos eilė (fiksuotų pozicijų skaičius),
δ(H) — apibrėžimo ilgis (tarpas tarp pirmos ir paskutinės fiksuotos pozicijos),
l — viso genotipo ilgis.

Ši nelygybė rodo, kad, esant didesniam nei vidutinis tinkamumui (f(H) > f̄), trumpų (mažas δ(H)) ir žemos eilės (mažas o(H)) schemų lūkesčiu didėjimas yra palankesnis. Tačiau formulė yra apytikslė ir grindžiama tam tikromis prielaidomis (pvz., atranka proporcinga tinkamumui, nepriklausomi operatorių poveikiai), todėl realiose situacijose gali būti nukrypimų.

Reikšmė genetiniuose algoritmuose

Schemos teorema suteikia intuityvų paaiškinimą, kodėl genetiniai algoritmai gali „sudėlioti“ gerus sprendimus iš mažesnių fragmentų (vadinamųjų building blocks): trumpi, informatyvūs fragmentai, kurie užtikrina aukštą tinkamumą, turėtų išlikti ir daugintis. Tai padeda formuoti praktinius principus, pvz., kodavimo ir operatorių (kryžminimo, mutacijos) parinkimą taip, kad būtų saugomos naudingos lokalinės struktūros.

Apribojimai ir kritika

Nors Schemos teorema yra galingas analitinis įrankis, svarbu suprasti jos ribotumus:

Ji yra nelygybė, o ne tiksli lygtis — pateikiamas lūkestis, o ne garantija.
Daroma keletas supaprastinančių prielaidų (pvz., nepriklausomi operatorių poveikiai, proporcionalios atrankos sąlyga), kurios ne visada tenkinamos praktikoje.
Teorema nenurodo, kaip greitai ar kokiu mastu schemos derėsis tarpusavyje arba kaip susiformuos pilni sprendimai — ji nurodo tik fragmentų gausėjimo linkmę.
Vėlesnės studijos, įskaitant rodymą, kad Schemos teorema yra Price'o lygties specialus atvejis (kai schemos indikatoriaus funkcija yra makroskopinis matas), pabrėžė, jog teoremos interpretacija kaip pagrindinio „building-block“ mechanizmo įrodymo yra pernelyg supaprastinta.

Praktiniai patarimai

Remiantis schemos idėja, praktikoje rekomenduojama:

Parinkti tokią genotipo reprezentaciją, kad svarbios savybės būtų suspaustos į trumpus fragmentus (sumažinti δ(H)).
Naudoti operatorius, kurie nesunaikina trumpų naudingų fragmentų (pavyzdžiui, tinkamas kryžminimo tipas arba reguliuoti p_c ir p_m reikšmes).
Analizuoti ne tik vidutinius tinkamumus, bet ir dispersiją bei koreliacijas tarp genų — realus elgesys gali skirtis nuo paprastų prognozių.

Išvados

Schemos teorema išlieka svarbus konceptualus įrankis, suteikiantis įžvalgų apie tai, kaip genetiniai algoritmai gali konstruoti sudėtingas sprendimų dalis iš paprastų fragmentų. Tačiau ją reikėtų naudoti atsargiai: tai apibūdinamojo pobūdžio rezultatas su aiškiais apribojimais, o jos pastangos paaiškinti GA sėkmę turi būti derinamos su kitomis teorijomis ir empiriniu testavimu.

Aprašymas

Nagrinėkime 6 ilgio dvejetaines eilutes. 1*10*1 schema apibūdina aibę visų 6 ilgio eilučių, kurių 1, 3 ir 6 pozicijose yra 1, o 4 pozicijoje - 0. * yra simbolis, kuris reiškia, kad 2 ir 5 pozicijose gali būti 1 arba 0. Schemos o ( H ) {\displaystyle o(H)} $o(H)$ tvarka apibrėžiama kaip fiksuotų šablono pozicijų skaičius, o apibrėžiantis ilgis δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ yra atstumas tarp pirmos ir paskutinės konkrečios pozicijos. Eilės tvarka 1*10*1 yra 4, o jos apibrėžiantis ilgis - 5. Schemos tinkamumas yra visų schemą atitinkančių eilučių vidutinis tinkamumas. Eilutės tinkamumas yra užkoduoto problemos sprendimo vertės matas, apskaičiuojamas pagal konkrečiai problemai skirtą vertinimo funkciją. Naudojant nustatytus genetinių algoritmų metodus ir genetinius operatorius, schemos teoremoje teigiama, kad trumpos, mažos eilės schemos, kurių tinkamumas yra didesnis už vidutinį, didėja eksponentiškai sekančiose kartose. Išreikšta lygtimi:

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

Čia m ( H , t ) {\displaystyle m(H,t)} $m(H,t)$ yra eilutės, priklausančios schemai H {\displaystyle H} $H$ kartos t {\displaystyle t} skaičius. $t$ f ( H ) {\displaystyle f(H)} $f(H)$ - stebimas vidutinis schemos H {\displaystyle H} $H$ tinkamumas, o a t {\displaystyle a_{t}} $a_{t}$ - stebimas vidutinis tinkamumas kartos t {\displaystyle t} $t$ . Sutrikimo tikimybė p {\displaystyle p} $p$ - tai tikimybė, kad kryžminimas arba mutacija sunaikins schemą H {\displaystyle H} $H$ . Ją galima išreikšti taip:

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}$

kur o ( H ) {\displaystyle o(H)} $o(H)$ yra schemos eiliškumas, l {\displaystyle l} $l$ yra kodo ilgis, p m {\displaystyle p_{m}} $p_{m}$ yra mutacijos tikimybė, o p c {\displaystyle p_{c}} $p_{c}$ yra kryžminimo tikimybė. Taigi schema, kurios apibrėžimo ilgis δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ yra mažesnė tikimybė, kad ji bus sutrikdyta.
Dažnai neteisingai suprantama, kodėl schemos teorema yra nelygybė, o ne lygybė. Atsakymas iš tikrųjų paprastas: teoremoje neatsižvelgiama į nedidelę, tačiau nenulinę tikimybę, kad eilutė, priklausanti schemai H {\displaystyle H} $H$ , bus sukurta "nuo nulio" mutuojant vienai eilutei (arba rekombinuojant dvi eilutes), kuri ankstesnėje generacijoje nepriklausė H {\displaystyle H} . $H$

Apribojimas

Schemos teorema galioja, jei genetinis algoritmas palaiko be galo didelę populiaciją, tačiau ne visada galioja (baigtinėje) praktikoje: dėl pradinės populiacijos atrankos klaidos genetiniai algoritmai gali konverguoti prie schemų, kurios neturi jokio atrankinio pranašumo. Taip ypač atsitinka daugiamodalinio optimizavimo atveju, kai funkcija gali turėti kelias viršūnes: populiacija gali dreifuoti ir teikti pirmenybę vienai iš viršūnių, ignoruodama kitas.

Schemos teorema negali paaiškinti genetinių algoritmų galios dėl to, kad ji galioja visiems problemų atvejams ir negali atskirti problemų, kuriose genetiniai algoritmai veikia prastai, nuo problemų, kuriose genetiniai algoritmai veikia gerai.

Dviejų kintamųjų daugiamodalės funkcijos grafikas.

Klausimai ir atsakymai

Klausimas: Kas yra Olando schemos teorema?

A: Olando schemos teorema - tai teorema apie genetinius algoritmus, kurioje teigiama, kad individai, kurių tinkamumas yra didesnis už vidutinį, turi didesnę tikimybę nugalėti.

K: Kas ir kada pasiūlė Olando schemos teoremą?

A: Johnas Hollandas pasiūlė Hollando schemos teoremą aštuntajame dešimtmetyje.

K: Kas yra schema genetinių algoritmų kontekste?

A.: Genetinių algoritmų kontekste schema - tai šablonas, kuris identifikuoja eilutės, turinčios panašumų tam tikrose eilutės pozicijose, poaibį.

K: Kaip interpretuojama Hollando schemos teorema, kuria remiantis buvo aiškinama genetinių algoritmų galia?

A: Hollando schemos teoremos, kuria buvo grindžiamas genetinių algoritmų galios aiškinimas, interpretacija yra ta, kad individai, kurių fizinis pajėgumas yra aukštesnis už vidutinį, turi didesnę tikimybę nugalėti.

K: Ką parodė Hollando schemos teoremos kritika?

A: Hollando schemos teoremos kritika parodė, kad ji yra specialus Price'o lygties atvejis, kai schemos indikatoriaus funkcija yra makroskopinis matas.

K: Kas yra cilindrinių aibių specialusis atvejis?

A: Schemos yra specialusis cilindrinių aibių atvejis.

K: Kokią erdvę sudaro schemos?

A: Schemos sudaro topologinę erdvę.