Hollands schemateorem

Beskrivning

Betrakta binära strängar med längden 6. Schemat 1*10*1 beskriver mängden av alla strängar med längden 6 med 1:or på positionerna 1, 3 och 6 och en 0 på position 4. * är en jokertecken-symbol, vilket innebär att positionerna 2 och 5 kan ha värdet 1 eller 0. Ordningen i ett schema o ( H ) {\displaystyle o(H)} definieras som antalet fasta positioner i mallen, medan den definierande längden δ ( H ) {\displaystyle \delta (H)} är avståndet mellan den första och sista specifika positionen. Ordningen för 1*10*1 är 4 och dess definierande längd är 5. Ett schemas lämplighet är den genomsnittliga lämpligheten hos alla strängar som matchar schemat. En strängs lämplighet är ett mått på värdet av den kodade problemlösningen, som beräknas av en problemspecifik utvärderingsfunktion. Med hjälp av de etablerade metoderna och de genetiska operatörerna för genetiska algoritmer, säger schemateoremet att korta, lågt ordnade scheman med högre genomsnittlig lämplighet ökar exponentiellt i successiva generationer. Uttryckt som en ekvation:

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

Här är m ( H , t ) {\displaystyle m(H,t)} antalet strängar som tillhör schema H {\displaystyle H} vid generation t {\displaystyle t}. , f ( H ) {\displaystyle f(H)} är den observerade genomsnittliga lämpligheten för schema H {\displaystyle H} och a t {\displaystyle a_{t}} är den observerade genomsnittliga lämpligheten vid generation t {\displaystyle t} . Sannolikheten för störning p {\displaystyle p} är sannolikheten för att crossover eller mutation kommer att förstöra schemat H {\displaystyle H} . Den kan uttryckas som:

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

där o ( H ) {\displaystyle o(H)} är ordningen i schemat, l {\displaystyle l} är kodens längd, p m {\displaystyle p_{m}} är sannolikheten för mutation och p c {\displaystyle p_{c}} är sannolikheten för crossover. Ett schema med en kortare definierande längd δ ( H ) {\displaystyle \delta (H)} har alltså mindre sannolikhet att bli störd.
En ofta missförstådd punkt är varför schematsatsen är en ojämlikhet snarare än en jämlikhet. Svaret är i själva verket enkelt: teoremet försummar den lilla, men icke-noll, sannolikheten att en sträng som tillhör schemat H {\displaystyle H} kommer att skapas "från grunden" genom mutation av en enda sträng (eller rekombination av två strängar) som inte tillhörde H {\displaystyle H} i den föregående generationen.

Begränsning

Schematsatsen gäller under antagandet att en genetisk algoritm upprätthåller en oändligt stor population, men den överförs inte alltid till den (ändliga) praktiken: på grund av provtagningsfel i den ursprungliga populationen kan genetiska algoritmer konvergera mot scheman som inte har någon selektiv fördel. Detta händer särskilt vid multimodal optimering, där en funktion kan ha flera toppar: populationen kan driva till att föredra en av topparna och ignorera de andra.

Skälet till att schemateoremet inte kan förklara de genetiska algoritmernas styrka är att det gäller för alla probleminstanser och inte kan skilja mellan problem där genetiska algoritmer presterar dåligt och problem där genetiska algoritmer presterar bra.

Plott av en multimodal funktion i två variabler.