Holland sématétele

Leírás

Tekintsük a 6 hosszúságú bináris karakterláncokat. Az 1*10*1 séma az összes olyan 6 hosszúságú karakterlánc halmazát írja le, amelynek 1., 3. és 6. pozíciójában 1-es, a 4. pozíciójában pedig 0 van. A * egy joker szimbólum, ami azt jelenti, hogy a 2. és az 5. pozíció 1 vagy 0 értékű is lehet. A séma o ( H ) {\displaystyle o(H)} sorrendjét a sablonban lévő rögzített pozíciók számaként határozzuk meg, míg a meghatározó hossz δ ( H ) {\displaystyle \delta (H)} az első és az utolsó konkrét pozíció közötti távolságot jelenti. Az 1*10*1 sorrendje 4, a meghatározó hossza pedig 5. Egy séma fitneszértéke a sémának megfelelő összes karakterlánc átlagos fitneszértéke. Egy karakterlánc alkalmassága a kódolt problémamegoldás értékének egy problémaspecifikus kiértékelő függvény által kiszámított mértéke. A genetikus algoritmusok bevált módszereit és genetikai operátorait alkalmazva a séma-tétel kimondja, hogy az átlagon felüli fitneszű rövid, alacsony rendű sémák exponenciálisan növekednek az egymást követő generációkban. Egyenletben kifejezve:

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

Itt m ( H , t ) {\displaystyle m(H,t)} a H sémához {\displaystyle H} tartozó karakterláncok száma a t generációban {\displaystyle t}. , f ( H ) {\displaystyle f(H)} a H {\displaystyle H} séma megfigyelt átlagos fitneszértéke és a t {\displaystyle a_{t}} a t {\displaystyle t} generációban megfigyelt átlagos fitneszértéke. A p {\displaystyle p} bomlás valószínűsége annak a valószínűsége, hogy a keresztezés vagy a mutáció elpusztítja a H {\displaystyle H} sémát. Ez a következőképpen fejezhető ki:

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

ahol o ( H ) {\displaystyle o(H)} a séma sorrendje, l {\displaystyle l} a kód hossza, p m {\displaystyle p_{m}} a mutáció valószínűsége és p c {\displaystyle p_{c}} a keresztezés valószínűsége. Tehát egy rövidebb definíciós hosszúságú δ ( H ) {\displaystyle \delta (H)} séma kisebb valószínűséggel bomlik meg.
Gyakran félreértik, hogy a sématétel miért egyenlőtlenség és nem egyenlőség. A válasz valójában egyszerű: a tétel elhanyagolja azt a kis, de nem nulla valószínűséget, hogy a H {\displaystyle H} sémához tartozó karakterlánc "nulláról" jön létre egy olyan karakterlánc mutációjával (vagy két karakterlánc rekombinációjával), amely az előző generációban nem tartozott a H {\displaystyle H} sémához.

Korlátozás

A sématétel egy végtelen nagy populációt fenntartó genetikai algoritmus feltételezése mellett érvényes, de nem mindig érvényesül a (véges) gyakorlatban: a kezdeti populáció mintavételi hibája miatt a genetikai algoritmusok olyan sémákhoz konvergálhatnak, amelyek nem rendelkeznek szelektív előnnyel. Ez különösen a multimodális optimalizálásban fordul elő, ahol egy függvénynek több csúcsa is lehet: a populáció sodródhat úgy, hogy az egyik csúcsot preferálja, a többit pedig figyelmen kívül hagyja.

A sématétel azért nem tudja megmagyarázni a genetikai algoritmusok erejét, mert minden problémapéldányra érvényes, és nem tud különbséget tenni olyan problémák között, amelyekben a genetikai algoritmusok rosszul teljesítenek, és olyanok között, amelyekben a genetikai algoritmusok jól teljesítenek.

Egy multimodális függvény ábrázolása két változóban.