Hollandova veta o schéme — základná veta genetických algoritmov
Prehľad Hollandovej vety o schéme: definícia schémy, znenie vety, historický kontext, praktické dôsledky pre genetické algoritmy a hlavné kritiky jej interpretácie.
Hollandova veta o schéme (často nazývaná aj základná veta genetických algoritmov) je teoretický výsledok z oblasti evolučných výpočtov, ktorý formuloval John Holland v 70. rokoch 20. storočia. V najčastejšej interpretácii hovorí, že krátke štruktúry s nízkym rádom (tzv. schémy) a s nadpriemernou zdatnosťou sa v populácii genetického algoritmu v priemere udržiavajú a ich počet sa môže v ďalších generáciách výrazne zvýšiť. Veta tým poskytla jazyk pre opis, prečo a ako sa v priebehu evolučného procesu objavujú a kombinujú „stavebné bloky“ riešení.
Galéria obrázkov
1 Obrázok
Čo je schéma
Schéma je šablóna alebo trieda reťazcov (napr. binárnych jedincov), ktorá špecifikuje hodnoty na niektorých pozíciách a ignoruje ostatné. V praxi sa často používa symbol „*“ (alebo iný zástupný znak) pre "nerozhodujúce" pozície. Príkladom môže byť schéma 1*0*1, ktorá zahŕňa všetky reťazce s jedničkami na prvom, treťom a piatom mieste bez ohľadu na druhé a štvrté miesto. Dôležité vlastnosti schemy sú:
- rád — počet pevne určených pozícií (fixácií) v schéme;
- definičná dĺžka — vzdialenosť medzi prvou a poslednou pevnou pozíciou, ktorá ovplyvňuje citlivosť na kríženie;
- počnosť — počet jedincov v populácii, ktorí zodpovedajú danej schéme.
Obsah vety a jej dôsledky
Formulácia Hollandovej vety ukazuje, že očakávaný počet exemplárov určitej schémy v nasledujúcej generácii je aspoň úmerný jej súčasnému počtu vynásobenému pomerom priemernej zdatnosti členov schémy ku priemernej zdatnosti celej populácie, pričom tento rast je potencionálne znížený pravdepodobnosťami, že schému rozruší operátory ako kríženie alebo mutácia. V zjednodušenom vyjadrení: krátke a nízkoradové schémy s vyššou priemernou zdatnosťou majú tendenciu byť zachované a skôr sa rozšíria, čo podporuje myšlienku kombinovania malých "stavebných blokov" k vytvoreniu lepších riešení.
Praktické použitie a význam
Tento pohľad poskytuje intuitívne vysvetlenie, prečo genetické algoritmy dokážu efektívne hľadať v rozsiahlych priestoroch riešení: priemerné zdatné fragmenty sa kopírujú a kombinujú, čo urýchľuje konvergenciu k dobrým riešeniam. V návrhu GA preto často volíme reprezentácie a operátory tak, aby podporovali udržiavanie krátkych a informatívnych schem.
Kritika a moderné pohľady
Hoci bola Hollandova veta pôvodne považovaná za kľúčové vysvetlenie sily genetických algoritmov, neskoršie práce poukázali na obmedzenia tejto interpretácie. Medzi bežné pripomienky patrí, že veta dáva len spodnú hranicu očakávaného počtu schem a nepredpovedá presnú dynamiku populácie; že sa jedná o tautologický výsledok očakáванí pod vplyvom selekcie, kríženia a mutácie; alebo že výsledky sú špecifické pre zvolenú reprezentáciu a nastavenia operátorov. Niektoré analýzy ukazujú, že Hollandova veta je špeciálnym prípadom všeobecnejších rovníc populačnej dynamiky, napríklad Priceovej rovnice, ak sa ako makroškála použije indikátor schémy.
Rozšírenia, poznámky a zdroje
V literatúre sa ku vete vyskytli rozličné formálne rozpracovania aj empirické skúmania. Diskusia často zahŕňa:
- prepojenie s teóriou genetických algoritmov a prácou Johna Hollanda o adaptívnych systémoch;
- matematické súvislosti s Priceovou rovnicou a s konceptami zo štatistiky a dynamických systémov;
- implikácie pre návrh reprezentácií a operátorov v praktikých algoritmoch.
Pre základné definície schémy a formálne vlastnosti množín, ktorými schémy tvoria topologický priestor, pozrite aj materiály o valcových množinách a teórii množín: topologické aspekty a popis schémy ako podmnožiny reťazcov. Tieto odkazy môžu poslúžiť ako východiskové body pre ďalšie štúdium a experimentálne overovanie správania heuristík založených na schémach.
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.
Súvisiace články
Autor
AlegsaOnline.com Hollandova veta o schéme — základná veta genetických algoritmov Leandro Alegsa
URL: https://sk.alegsaonline.com/art/44753
Zdroje
- books.google.com : An analysis of reproduction and crossover in a binary-coded genetic algorithm
- dynamics.org : The Schema Theorem and Price’s Theorem
- books.google.com : Adaptation in Natural and Artificial Systems