Hollandova veta o schéme
Hollandova veta o schéme, nazývaná aj základná veta genetických algoritmov, je nerovnosť, ktorá vyplýva z hrubého zrnenia rovnice evolučnej dynamiky. Veta o schéme hovorí, že krátke schémy nízkeho rádu s nadpriemernou zdatnosťou sa v nasledujúcich generáciách exponenciálne zvyšujú. Vetu navrhol John Holland v 70. rokoch 20. storočia. Spočiatku bola všeobecne považovaná za základ pre vysvetlenie sily genetických algoritmov. Táto interpretácia jej dôsledkov však bola kritizovaná vo viacerých publikáciách, ktorých prehľad je uvedený v , kde sa ukazuje, že veta o schéme je špeciálnym prípadom Priceovej rovnice s funkciou indikátora schémy ako makroskopickým meradlom.
Schéma je šablóna, ktorá identifikuje podmnožinu reťazcov s podobnosťami na určitých pozíciách reťazca. Schémy sú špeciálnym prípadom valcových množín, a preto tvoria topologický priestor.
Popis
Uvažujme binárne reťazce dĺžky 6. Schéma 1*10*1 opisuje množinu všetkých reťazcov dĺžky 6 s 1 na pozíciách 1, 3 a 6 a 0 na pozícii 4. Znak * je zástupný symbol, čo znamená, že pozície 2 a 5 môžu mať hodnotu 1 alebo 0. Poradie schémy o ( H ) {\displaystyle o(H)}
je definované ako počet pevných pozícií v šablóne, zatiaľ čo definičná dĺžka δ ( H ) {\displaystyle \delta (H)}
je vzdialenosť medzi prvou a poslednou konkrétnou pozíciou. Poradie 1*10*1 je 4 a jeho definičná dĺžka je 5. Fitness schémy je priemerná fitness všetkých reťazcov, ktoré vyhovujú schéme. Fitness reťazca je mierou hodnoty zakódovaného riešenia problému, vypočítanou vyhodnocovacou funkciou špecifickou pre daný problém. Pri použití zavedených metód a genetických operátorov genetických algoritmov veta o schéme hovorí, že krátke schémy nízkeho rádu s nadpriemernou fitness exponenciálne rastú v nasledujúcich generáciách. Vyjadrené ako rovnica:
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]. } ![{\displaystyle \operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p].}](https://www.alegsaonline.com/image/37ac2d707cc2a474ad365dd53141be94ecad43de.svg)
Tu m ( H , t ) {\displaystyle m(H,t)}
je počet reťazcov patriacich do schémy H {\displaystyle H}
v generácii t {\displaystyle t}. 
, f ( H ) {\displaystyle f(H)}
je pozorovaná priemerná fitness schémy H {\displaystyle H} a a t {\displaystyle a_{t}}
je pozorovaná priemerná fitness v generácii t {\displaystyle t} . Pravdepodobnosť narušenia p {\displaystyle p}
je pravdepodobnosť, že kríženie alebo mutácia zničí schému H {\displaystyle H} . Možno ju vyjadriť ako:
p = δ ( H ) l - 1 p c + o ( H ) p m {\displaystyle p={\delta (H) \over l-1}p_{c}+o(H)p_{m}} 
kde o ( H ) {\displaystyle o(H)} je poradie schémy, l {\displaystyle l}
je dĺžka kódu, p m {\displaystyle p_{m}}
je pravdepodobnosť mutácie a p c {\displaystyle p_{c}}
je pravdepodobnosť kríženia. Takže schéma s kratšou definičnou dĺžkou δ ( H ) {\displaystyle \delta (H)} má menšiu pravdepodobnosť narušenia.
Často nepochopeným bodom je, prečo je veta o schéme nerovnosťou, a nie rovnosťou. Odpoveď je v skutočnosti jednoduchá: veta zanedbáva malú, ale nenulovú pravdepodobnosť, že reťazec patriaci do schémy H {\displaystyle H} vznikne "od nuly" mutáciou jedného reťazca (alebo rekombináciou dvoch reťazcov), ktorý v predchádzajúcej generácii nepatril do H {\displaystyle H} .
Obmedzenie
Veta o schéme platí za predpokladu genetického algoritmu, ktorý udržiava nekonečne veľkú populáciu, ale nie vždy sa prenáša do (konečnej) praxe: v dôsledku chyby výberu vzorky v počiatočnej populácii môžu genetické algoritmy konvergovať k schémam, ktoré nemajú žiadnu selektívnu výhodu. Stáva sa to najmä pri multimodálnej optimalizácii, kde funkcia môže mať viacero vrcholov: populácia môže driftovať tak, aby uprednostňovala jeden z vrcholov a ignorovala ostatné.
Dôvodom, prečo veta o schéme nedokáže vysvetliť silu genetických algoritmov, je to, že platí pre všetky prípady problémov a nedokáže rozlíšiť medzi problémami, v ktorých genetické algoritmy fungujú slabo, a problémami, v ktorých genetické algoritmy fungujú dobre.
Graf multimodálnej funkcie v dvoch premenných.
