Prírodou inšpirované algoritmy

Evolučné programovanie

Evolučné programovanie (EP) aplikuje simuláciu evolučného procesu na populáciu súťažiacich algoritmov. Jedná sa pravdepodobne o najstarší ale tiež najmenej známy variant EA. Navrhol ho začiatkom 60-tych rokov Fogel, aj keď základná publikácia o EP (Fogel et al., 1966) vychádza oveľa neskôr. V pôvodnej verzii sa jednalo o konečný automat, určený na predikciu nestacionárnych časových radov. Automat sa vyvíjal prostredníctvom mutácií: potomok sa od svojho predka líšil v počte stavov, v jednom výstupnom symbole, v jednom prechode alebo v počiatočnom stave. Základom ďalšej evolúcie bol lepší z týchto dvoch jedincov (vhodnosťou bol počet konečným automatom správne predikovaných symbolov časového radu). Neskôr sa začalo pracovať nie s izolovanými jedincami ale s celými populáciami a postupne sa v EP objavili ďalšie prvky, pripomínajúce evolučné stratégie (aj keď sa tieto dva postupy vyvíjali až do roku 1992 prakticky nezávisle na sebe). Motiváciou pre evolučnú predikciu bolo poznanie, že schopnosť predikcie je základom inteligentného správania. Neskôr sa začalo EP používať aj na riešenie širšieho spektra optimalizačných úloh v oblasti celých aj reálnych čísel (Fogel, 1991).

Na formu reprezentácie nie sú v prípade EP kladené žiadne ohraničenia (nemusí sa jednať o lineárnu údajovú štruktúru). Napríklad pre evolúciu neurónovej siete sa kóduje zvlášť architektúra siete a zvlášť jednotlivé váhy (pričom obe reprezentácie podliehajú nezávisle na sebe mutáciám, prvá spravidla s Poissonovým rozdelením a druhá s Gaussovým rozdelením pravdepodobnosti).

Jednotlivé bloky základného algoritmu EA majú v prípade EP nasledujúce špecifiká:

• jediným genetickým operátorom je mutácia (kríženie sa nepoužíva - hovorí sa o evolúcii druhu, kde k medzidruhovému kríženiu nedochádza),
• používa sa široké spektrum mutácií od nepatrných až po veľmi drastické,
• veľkosť mutácií je adaptívna, s približovaním k hľadanému extrému klesá (niekedy sa používa aj metaevolúcia, pri ktorej disperzia mutácie parametrov objektu podlieha samostatnej paralelnej evolúcii)
• selekcia sa robí prostredníctvom turnajov (veľkosť populácie je v niektorých modifikáciách EP premenlivá).

Otázka kríženia v EP je silne diskutovanou otázkou. Obvykle sa argumentuje tým, že EP napodobňuje vývoj navzájom súťažiacich druhov, pri ktorom k medzidruhovému kríženiu spravidla nedochádza. Výrazná kritika (Atmar, 1991) sa sústreďuje na preceňovanie kríženia ako nástroja, generujúceho diverzitu. V EP komunite prevláda názor (opačný ako v GA komunite), že kríženie je na rozdiel od mutácie problémovo závislé a zmysel jeho použitia je často veľmi sporný. Naviac sa v súvislosti s EP zdôrazňuje selekcia na fenotypickej (hornej) úrovni, v podstate nezávislá na genetických zmenách na dolnej úrovni a vyčíta sa v tejto súvislosti genetickým algoritmom obmedzenie sa iba na túto dolnú úroveň a na zjednodušený spôsob kódovania (jeden úsek reťazca = jedna vlastnosť), čo vraj môže viesť v niektorých prípadoch k neschopnosti GA nájsť optimálne riešenie.