Olando schemos teorema

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)} tvarka apibrėžiama kaip fiksuotų šablono pozicijų skaičius, o apibrėžiantis ilgis δ ( H ) {\displaystyle \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]. }

Čia m ( H , t ) {\displaystyle m(H,t)} yra eilutės, priklausančios schemai H {\displaystyle H} kartos t {\displaystyle t} skaičius. f ( H ) {\displaystyle f(H)} - stebimas vidutinis schemos H {\displaystyle H} tinkamumas, o a t {\displaystyle a_{t}} - stebimas vidutinis tinkamumas kartos t {\displaystyle t} . Sutrikimo tikimybė p {\displaystyle p} - tai tikimybė, kad kryžminimas arba mutacija sunaikins schemą H {\displaystyle 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}}

kur o ( H ) {\displaystyle o(H)} yra schemos eiliškumas, l {\displaystyle l} yra kodo ilgis, p m {\displaystyle p_{m}} yra mutacijos tikimybė, o p c {\displaystyle p_{c}} yra kryžminimo tikimybė. Taigi schema, kurios apibrėžimo ilgis δ ( H ) {\displaystyle \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} , bus sukurta "nuo nulio" mutuojant vienai eilutei (arba rekombinuojant dvi eilutes), kuri ankstesnėje generacijoje nepriklausė H {\displaystyle 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.