Prírodou inšpirované algoritmy

História

GA sú súčasťou širšej skupiny algoritmov, tzv. evolučných algoritmov, založených na heuristických technikách vychádzajúcich z evolučného princípu v prírode. Pričom

na evolúciu sa môžme pozerať z dvojakého hľadiska, buď ako na cieľ, so snahou ju namodelovať a pochopiť, alebo ako nástroj slúžiaci na riešenie úloh.

Spočiatku sa myšlienkou simulácie evolučných systémov na počítači zaoberali hlavne biológovia.

V 50-tych rokoch 20. storočia sa zaujímali zväčša o nasimulovanie počítačovej evolúcie aby viac pochopili tú prírodnú. Postupom rokov sa objavili prístupy využitia evolučných algorimov so zámerom riešenia úloh v technických problémoch, tieto začiatky sa datujú do 50-tych a 60-tych rokov, i keď boli publikované oveľa neskôr.

"Ak evolúcia funguje tak dobre pre organizmy v prírode, prečo by nefungovala v počítačových programoch ?"

Evolučné algoritmy, postupy a smery ktoré prežili "evolúciu" sa delia do 3 hlavných skupín, ktoré sa vyvíjali nezávisle a skoro súčasne. Rozdelenie nevyplýva z nejakých veľkých rozdieloch týkajúcich sa ich funkčnosti, ale je založené skôr na historických faktoch a detailoch implementácie základnej schémy algoritmu. Ich biologická báza je v skutočnosti rovnaká.

Evolučná rovnica

Prvý z nich reprezentoval Rechenberg, ktorý navrhol evolučnú stratégiu - ES (Rechenberg, 1973), metódu optimalizácie reálnych parametrov zariadení, napr. profilu krídla

Najväčšiu popularitu získali genetické algoritmy - GA (Holland, 1975). Uvedená práca predstavovala GA ako abstrakciu biologickej evolúcie a položila teoretické základy adaptácie prostredníctvom GA.

Špeciálnym prípadom GA je genetické programovanie - GP (Koza, 1992), v ktorom - na rozdiel od klasických GA - evolúcii nepodlieha lineárna štruktúra ale strom reprezentujúci „evolvujúci“ program.

Iný prístup predstavovalo evolučné programovanie - EP (Fogel et al., 1966), kde kandidát, organizmus na riešenie predstavoval konečný automat. Organizmy, ktoré najlepšie vyriešili nejakú cieľovú funkciu, tak získali možnosť reprodukcie, a zmutovaním rodičov vznikali potomkovia.

Od GA sa líšia aj rekombinačnými operátormi, ako sú napríklad operátory spriemerňovania parametrov, keďže ES pracujú s reálnymi číslami.

John Holland, autor myšlienky genetických algoritmov pôsobil ako profesor na MIT a snažil sa o nájdenie formálnej teórie adaptácie, ktorá by pokryla všetky adaptívne procesy. Inšpiráciou mu bola predovšetkým kniha (R.A.Fischer,1958). Je prvým pokusom o matematickú teóriu evolúcie. Hovorí sa v nej, že evolúcia, podobne ako učenie, je formou adaptácie na prostredie, pričom rozdiel je v tom, že pôsobí počas generácii a nie vrámci jedného života. Jeho výhodou oproti iným výskumníkom bola myšlienka stavebných blokov. Do skúmania detailov GA Holland zapojil aj svojich študentov, ktorí v jeho práci pokračovali. Experimentovali s parametrami GA a snažili sa štandardizovať tvar algoritmu. Prvými aplikáciami genetických algoritmov sú práve práce Hollandových študentov:

• Zjednodušená verzia šachu
• Simulácia funkcií jednobunkového organizmu
• Alokácia zásob zemného plynu (experiment navrhol David Goldberg. Holland sa ho snažil odhovoriť, pretože to považoval za príliš náročný problém, ale Goldberg do roka prišiel s výsledkami, s funkčnou verziou GA.)

Prvým krokom pri zasväťovaní sa do novej problematiky je získanie a pochopenie používanej terminológie. Genetické algoritmy si ju zväčša požičali od biológov.

Chromozóm je tvorený jednotlivými génmi, každý z génov kóduje jednu vlastnosť, napríklad farbu vlasov. Konkrétny spôsob kódovania génov môže byť v rôznych EA značne rozdielny (binárny reťazec, reálne číslo, strom, ...). Možné „hodnoty“ daného génu reprezentujú alely, napr. hnedé, blond, čierne ... Každý gén zaujíma na chromozóme istú pozíciu (locus). Živá bunka obvykle obsahuje viacero chromozómov. Kompletný súbor génov (zo všetkých chromozómov) tvorí genóm daného organizmu. Genotyp predstavuje súbor vlastností, zakódovaný v genóme. Genotyp sa v procese rastu a formovania organizmu prejaví charakteristickými vlastnosťami, ktoré potom tvoria fenotyp. Vhodnosť (fitness) organizmu je vlastne nástrojom prirodzeného výberu - selekcie, predstavuje konkrétne jeho schopnosť dožiť sa reprodukčného veku a mať čo najviac potomkov.