Prírodou inšpirované algoritmy

Úvod

Na týchto stránkach vítame všetkých priaznivcov genetických algoritmov. Všetkých, ktorí majú záujem sa dozvedieť niečo viac o GA alebo vidieť GA v akcii. Vo všeobecnosti rozdeľujeme algoritmy na silné a slabé.Silné algoritmy sa vyznačujú vysokým výkonom, ale sú určené pre riešenie len určitého okruhu úloh, väčšinou ide o konkrétny problém. Naproti tomu slabé algoritmy v ideálnom prípade riešia každú úlohu za cenu nižšieho výkonu. Genetické algoritmy patria do skupiny slabých algoritmov, nie sú špecializované na konkrétny typ príkladu, stačí ho vyjadriť ako zložky. Otázkou je kedy použiť GA? Ide hlavne o riešenie takých problémov, ktoré nemajú vysoké požiadavky na výsledok, riešenie úlohy. Iný prípad použitia GA je vtedy, ak neexistuje silná metóda.

Predstavte si, že potrebujete optimalizovať nejakú funkciu na nejakej množine prípustných riešení, pritom ale o tejto funkcii veľa neviete. Neviete napríklad povedať ani ako sa na danej množine správa, neviete zistiť, či je vôbec spojitá, či má v danom bode extrém a aký. Predpokladajte tiež, že množina všetkých prístupných riešení je vo všeobecnosti veľmi rozsiahla. To je situácia, v ktorej väčšina konvenčných optimalizačných techník zlyhá. V tejto situácii by ste mali pomaly začať uvažovať o použití genetických algoritmov. To zázračné, čo genetické algoritmy ponúkajú, je v podstate aplikácia princípov, ktoré príroda úspešne používa už po tisícročia. Hlavná myšlienka spočíva v tom, že na jednotlivé prvky množiny prístupných riešení sa pozeráme ako na nejaké živé organizmy v nejakom umelom životnom prostredí. Pritom to, ako sa týmto organizmom v tomto prostredí vedie, t.j. ich schopnosť prežiť a schopnosť reprodukcie, zodpovedá tomu, o ako "dobré" riešenia ide. Vlastné hľadanie potom spočíva vo výbere nejakej počiatočnej populácie týchto organizmov a následnej simulácii jej vývoja pod kontrolou evolučných mechanizmov, zahrňujúcich prirodzený výber, reprodukciu, atď. Ako sa táto populácia od generácie ku generácii vyvíja, "zlé" riešenia majú tendenciu vymierať, a naopak "dobré" riešenia sa medzi sebou hojne krížia a produkujú riešenia ešte lepšie.

Genetické algoritmy (GA) sú typickým predstaviteľom prehľadávacích algoritmov. Prehľadávajú priestor riešení problému, pričom 1 bod priestoru predstavuje konkrétnu n-ticu hodnôt parametrov riešenia problému - konkrétne riešenie. (n+1)-vý rozmer určuje kvalitu riešenia, vhodnosť (fitness). Priradením vhodností jednotlivým bodom priestoru riešení vzniká plocha vhodností, funkcia, ktorú chceme optimalizovať, teda nájsť bod s najväčšou vhodnosťou. Využívajú populačný princíp, to znamená, že naraz prehľadávajú niekoľko bodov priestoru. Prehľadávanie prebieha pseudonáhodným spôsobom, teda smerovane, na základe funkcie vhodnosti. Do určitej miery kopírujú evolučný princíp v prírode. Pričom evolúcia je jednak nástrojom na riešenie úloh a jednak cieľom (modelujú evolúciu za účelom pochopiť ju).