Teorema schemei lui Holland

Se consideră șiruri binare de lungime 6. Schema 1*10*1 descrie ansamblul tuturor șirurilor de lungime 6 cu 1 în pozițiile 1, 3 și 6 și cu 0 în poziția 4. * este un simbol joker, ceea ce înseamnă că pozițiile 2 și 5 pot avea o valoare de 1 sau 0. Ordinea unei scheme o ( H ) {\displaystyle o(H)} este definită ca fiind numărul de poziții fixe din șablon, în timp ce lungimea definitorie δ ( H ) {\displaystyle \delta (H)} este distanța dintre prima și ultima poziție specifică. Ordinea lui 1*10*1 este 4, iar lungimea sa definitorie este 5. Fitness-ul unei scheme este fitness-ul mediu al tuturor șirurilor care corespund schemei. Fitness-ul unui șir este o măsură a valorii soluției codificate a problemei, calculată cu ajutorul unei funcții de evaluare specifice problemei. Utilizând metodele și operatorii genetici consacrați ai algoritmilor genetici, teorema schemelor afirmă că schemele scurte, de ordin inferior, cu o fitness peste medie, cresc exponențial în generații succesive. Exprimată sub forma unei ecuații:

E ( m ( 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) \ peste a_{t}}}[1-p]. }

Aici m ( H , t ) {\displaystyle m(H,t)} este numărul de șiruri aparținând schemei H {\displaystyle H} la generația t {\displaystyle t}. , f ( H ) {\displaystyle f(H)} este fitnessul mediu observat al schemei H {\displaystyle H} și a t {\displaystyle a_{t}} este fitnessul mediu observat la generația t {\displaystyle t} . Probabilitatea de întrerupere p {\displaystyle p} este probabilitatea ca încrucișarea sau mutația să distrugă schema H {\displaystyle H} . Ea poate fi exprimată astfel:

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

unde o ( H ) {\displaystyle o(H)} este ordinea schemei, l {\displaystyle l} este lungimea codului, p m {\displaystyle p_{m}} este probabilitatea de mutație și p c {\displaystyle p_{c}} este probabilitatea de încrucișare. Așadar, o schemă cu o lungime de definire mai mică δ ( H ) {\displaystyle \delta (H)} are mai puține șanse de a fi perturbată.
Un aspect adesea neînțeles este motivul pentru care teorema schemei este o inegalitate și nu o egalitate. Răspunsul este, de fapt, simplu: Teorema neglijează probabilitatea mică, dar diferită de zero, ca un șir aparținând schemei H {\displaystyle H} să fie creat "de la zero" prin mutația unui singur șir (sau recombinarea a două șiruri) care nu aparținea lui H {\displaystyle H} în generația anterioară.

Teorema schemelor este valabilă în ipoteza unui algoritm genetic care menține o populație infinit de mare, dar nu se aplică întotdeauna în practică (finită): din cauza erorilor de eșantionare din populația inițială, algoritmii genetici pot converge la scheme care nu au niciun avantaj selectiv. Acest lucru se întâmplă în special în optimizarea multimodală, unde o funcție poate avea mai multe vârfuri: populația poate derapa pentru a prefera unul dintre vârfuri, ignorându-le pe celelalte.

Motivul pentru care Teorema Schemei nu poate explica puterea algoritmilor genetici este că aceasta este valabilă pentru toate cazurile de probleme și nu poate face distincția între problemele în care algoritmii genetici au performanțe slabe și problemele în care algoritmii genetici au performanțe bune.