Kretssats

Scheme theorem , eller mall theorem - huvudsatsen i teorin om genetiska algoritmer , vilket ger en motivering för deras effektivitet. Första formuleringen och bevisningen av J. Holland 1975.

Konceptet med ett schema

Ett schema är en delmängd av uppsättningen av alla möjliga genotyper som är möjliga i en given population , givet som en kromosom med fasta värden på några bitar . Resten av bitarna kan ta vilket värde som helst och utgöra exempel på schemat. Så, exempel på schema 00**1* är kromosomerna 000010, 000011, 000110, 000111, 001010, 001011, 001110 och 001111. Antalet fasta bitar kallas ordningen för schemat, och den fasta positionen dvs skillnaden mellan deras antal) kallas dess definierande längd. Ordningen på ovanstående krets är 3, och den definierande längden är 5 - 1 = 4. Konditionsfunktionen (FF) för kretsen är medelvärdet för fitnessfunktionen i alla dess exempel.

Sats

Schemasatsen visar den exponentiella spridningen av väl anpassade scheman med liten ordning och definierande längd som sker vid generationsskifte (sådana scheman med en FP högre än genomsnittet för befolkningen kallas byggstenar ). Matematiskt uttrycks detta av ojämlikheten:

N(h,t+1)\geq N(h,t){f(h,t) \över f(t)}[1-p].

Här är antalet exempel på krets h i steg t, och är detsamma i nästa steg; är kretslämplighetsfunktionen vid steg t; är medelvärdet av FF för hela befolkningen i samma steg; är sannolikheten för schemaförstörelse under inverkan av genetiska operatörer. Denna sannolikhet är: $N(h,t)$ $N(h,t+1)$ $f(h,t)$ $med)$ $sid$

p={\delta (h) \over l-1}p_{c}+o(h)p_{m},

där är den definierande längden av schemat, är ordningen, är överkorsningssannolikheten och är mutationssannolikheten . Således ser den fullständiga formen av satsen ut så här: $\delta(h)$ $åh)$ $p_{c}$ $p_{m}$

N(h,t+1)\geq N(h,t){f(h,t) \över f(t)}[1-{\delta (h) \över l-1}p_{ c}-o(h)p_{m}].

Schemasatsen ger inga exakta värden, utan endast en nedre gräns för antalet instanser av ett schema efter nästa generationsskifte. Detta beror på det faktum att det finns en möjlighet för uppkomsten av nya exempel på systemet under verkan av genetiska operatörer på kromosomer som inte tidigare var relaterade till det.

Se även

genetisk algoritm

Länkar

JH Holland. Anpassning i naturliga och artificiella system . The MIT Press, nyutgåva, 1992.
Liles WC Introduktion till Schema Theory: En översiktsföreläsning om pessimistisk och exakt schemateori / WC Liles, Wiegand RP - 2002 Summer Lecture Series, EC lab Activities, Computer Science Department, George Mason University. föreläsningstext föreläsningsbilder