Holland's skema-sætning

Beskrivelse

Betragt binære strenge af længde 6. Skemaet 1*10*1 beskriver mængden af alle strenge af længde 6 med 1'er på positionerne 1, 3 og 6 og et 0 på position 4. * er et wildcard-symbol, hvilket betyder, at positionerne 2 og 5 kan have værdien 1 eller 0. Ordningen af et skema o ( H ) {\displaystyle o(H)} er defineret som antallet af faste positioner i skabelonen, mens den definerende længde δ ( H ) {\displaystyle \delta (H)} er afstanden mellem den første og den sidste specifikke position. Ordningen af 1*10*1 er 4, og den definerende længde er 5. Et skemas egnethed er den gennemsnitlige egnethed af alle strenge, der passer til skemaet. En strengs egnethed er et mål for værdien af den kodede problemløsning, som beregnes af en problemspecifik evalueringsfunktion. Ved hjælp af de etablerede metoder og genetiske operatører i genetiske algoritmer fastslår skema-sætningen, at korte, lavtordnede skemaer med en fitness over gennemsnittet stiger eksponentielt i de efterfølgende generationer. Udtrykt som en ligning:

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

Her er m ( H , t ) {\displaystyle m(H,t)} antallet af strenge, der tilhører skema H {\displaystyle H} ved generation t {\displaystyle t} , f ( H ) {\displaystyle f(H)} er den observerede gennemsnitlige fitness for skema H {\displaystyle H} og a t {\displaystyle a_{t}} er den observerede gennemsnitlige fitness ved generation t {\displaystyle t} . Sandsynligheden for forstyrrelse p {\displaystyle p} er sandsynligheden for, at krydsning eller mutation vil ødelægge skemaet H {\displaystyle H} . Den kan udtrykkes som:

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

hvor o ( H ) {\displaystyle o(H)} er rækkefølgen af skemaet, l {\displaystyle l} er kodens længde, p m {\displaystyle p_{m}} er sandsynligheden for mutation og p c {\displaystyle p_{c}} er sandsynligheden for crossover. Så et skema med en kortere definerende længde δ ( H ) {\displaystyle \delta (H)} er mindre tilbøjeligt til at blive forstyrret.
Et ofte misforstået punkt er, hvorfor skema-sætningen er en ulighed snarere end en lighed. Svaret er faktisk enkelt: Sætningen negligerer den lille, men ikke-nul, sandsynlighed for, at en streng, der tilhører skemaet H {\displaystyle H} , vil blive skabt "fra bunden" ved mutation af en enkelt streng (eller rekombination af to strenge), der ikke tilhørte H {\displaystyle H} i den foregående generation.

Begrænsning

Teoremet om skemaer gælder under forudsætning af en genetisk algoritme, der opretholder en uendelig stor population, men det overføres ikke altid til (endelig) praksis: på grund af fejl i den oprindelige population kan genetiske algoritmer konvergere mod skemaer, der ikke har nogen selektiv fordel. Dette sker især i multimodal optimering, hvor en funktion kan have flere toppe: populationen kan drive til at foretrække en af toppene og ignorere de andre.

Grunden til, at skemateoremet ikke kan forklare de genetiske algoritmers styrke, er, at det gælder for alle probleminstanser og ikke kan skelne mellem problemer, hvor genetiske algoritmer klarer sig dårligt, og problemer, hvor genetiske algoritmer klarer sig godt.

Plot af en multimodal funktion i to variabler.