Evolučný výpočet

Evolučné výpočty (EV) patria k biologicky motivovaným metódam riešenia problémov. Predstavujú prístup k riešeniu optimalizačných problémov, založený na Darwinovej evolučnej teórii. V [53] sú uvedené tieto 3 ich základné zložky evolučného výpočtu:

1. Prirodzený výber - zásada, že v prírode jedince, ktoré majú väčšiu schopnosť prežiť, vstupujú do reprodukčného procesu častejšie ako menej schopné jedince. Tým pádom majú i viac potomkov. Schopnosť prežiť je v EV nahradená vhodnosťou (fitness) riešenia, kódovaného daným jedincom.
2. Náhodný genetický drift - populácia je v čase ovplyvňovaná náhodnými udalosťami, ktoré ovplyvňujú život jedincov. Takýmito udalosťami môžu byť napr. mutácia genetického materiálu jedinca, alebo smrť jedinca pred tým, ako vstúpi do reprodukčného procesu.
3. Reprodukčný proces - vznik nových jedincov populácie kombináciou genetického materiálu rodičovských jedincov.

Obrázok: Bloková schéma EV

Ako bolo vyššie uvedené, EV slúžia na riešenie optimalizačných problémov. Optimalizačný problém by sme mohli vo všeobecnosti definovať ako proces zdokonaľovania a vylepšovania parametrov $p_{1},\ldots,p_{n}$ určitej cieľovej funkcie. Každej n-tici parametrov môžeme priradiť vhodnosť $F(p_{1},\ldots,p_{n}) = f$. Takto sme získali n-rozmerný prehľadávací priestor, v ktorom sa snažíme nájsť kombináciu parametrov s maximálnou vhodnosťou. $maxF(p_{1_{i}},\ldots,p_{n_{i}})$. Častokrát je však nájdenie samotného optima príliš náročné. Vtedy sa cieľom optimalizácie stáva priblíženie k nemu. Existuje viacero metód riešenia optimalizačných metód (napr. metódy založené na matematickej analýze, stochastické optimalizačné algoritmy, či slepé prehľadávanie, a pod.). EV sa od nich odlišujú najmenej v jednom z nasledujúcich bodov :

• EV pracujú s kódovaním optimalizovaných parametrov, nie so samotnými parametrami.
• Prehľadávanie priestoru je paralelné, každý jedinec populácie predstavuje potenciálne riešenie.
• Prechod z jedného bodu prehľadávaného priestoru do iného je riadený stochastickými pravidlami.
• EV pracujú s cieľovou funkciou, predstavujúcou abstrakciu riešeného problému. Vo všeobecnosti nepoužívajú žiadne pomocné odvodené znalosti, čo im umožňuje obsiahnuť široký záber problémov. Cenou za túto vlastnosť je však ich nižšia úspešnosť v porovnaní s úzko špecializovanými metódami.

V súčastnosti je používaných viacero druhov EV, odlišné sú najmä v:

• reprezentácii jedincov,
• spôsobe ohodnotenia jedincov - výpočtu fitness,
• genetických operátoroch.

Štrukturálne sa EV skladá z niekoľkých blokov (obr. 4.1).