Prírodou inšpirované algoritmy

Evolučná stratégia

Evolučná stratégia (ES) vznikla začiatkom 60-tych rokov spoluprácou troch študentov Technickej univerzity v Berlíne: Rechenberga, Bienerta a Schwefela. Ich cieľom bolo riešenie optimalizačných úloh z oboru hydrodynamiky. Základnou myšlienkou ich metódy bolo sledovanie vplyvu náhodných skokových mutácií parametrov na kvalitu navrhovaného systému. Keď mutácia viedla k lepšiemu riešeniu, tak mutant bol prijatý ako východisko k ďalšej optimalizácii, keď mutácia spôsobila zhoršenie, tak mutant bol zavrhnutý.Naznačený postup sa ukázal v mnohých aplikáciách ako úspešný. Podrobnejší teoretický rozbor však naznačil, že je výhodnejšie pracovať nie so skokovými náhodnými mutáciami parametrov ale so spojitými mutáciami každej z n reálnych zložiek vektora parametrov, pričom mutácie majú normálne rozloženie s nulovou strednou hodnotou a s adaptívne sa meniacou štandardnou odchýlkou. Vlastnosti vygenerovaného potomka a rodiča sa porovnali a lepší z nich prežil a stal sa rodičom pre ďalšiu generáciu. V (Rechenberg, 1973) je odvodené pravidlo „pätinového úspechu“, podľa ktorého je optimálna hodnota štandardnej odchýlky taká, ktorá zaručí, že v priemere každá piata mutácia bude úspešná. Keď je počet úspešných mutantov väčší ako 20%, je potrebné zvýšiť pravdepodobnosť mutácií, aby sa obsiahla väčšia časť prehľadávaného priestoru. Keď je naopak počet úspešných mutantov menší ako 20%, je potrebné znížiť pravdepodobnosť mutácií, inak hrozí, že hľadanie bude prebiehať úplne chaoticky a nebude konvergovať.

Jedinec je teda reprezentovaný vektorom reálnych čísel. Pôvodná koncepcie ES nepracovala s populáciou ale každú generáciu tvoril iba jediný jedinec. Neskôr už začali používať aj ES viacero jedincov v populácii. Tí vygenerovali jediného potomka, ktorý nahradil najhoršieho rodiča - samozrejme iba vtedy, keď bol od neho lepší. Najnovšie metódy ES už prešli na generovanie viacerých potomkov v každej generácii (v porovnaní s inými typmi EA býva ale veľkosť populácie pre ES relatívne malá). V tomto prípade sa použil buď sexuálny alebo panmiktický genetický operátor rekombinácie (v ES sa používa tento termín namiesto pojmu „kríženie“ pre analogický genetický operátor). V prvom prípade sa buď náhodne rozhodovalo, ktorá zložka vektora prejde do potomka z jedného, a ktorá z druhého rodiča alebo sa zložky vektora parametrov potomka vypočítali ako aritmetický priemer zložiek oboch rodičov (Schwefel, 1981). V prípade panmiktického operátora sa pre generovanie každej zložky vektora potomka vyberal iný rodič. Náhrada sa diala buď selekciou najúspešnejších jedincov spomedzi rodičov aj potomkov (plus stratégia), alebo iba spomedzi potomkov (čiarková stratégia - comma strategy). Aj v prípade použitia operátora rekombinácie však ostáva kľúčovým genetickým operátorom ES mutácia.

Výhodou ES je samoadaptácia, spočívajúca v možnosti zahrnúť charakteristické údaje stratégie (štandardnú odchýlku a korelačné koeficienty) do procesu prehľadávania, čo umožní zohľadniť lokálnu topológiu funkcie vhodnosti a zefektívniť tak tento proces. Jedinec si pritom buduje akýsi vnútorný model funkcie vhodnosti, ktorý využíva pre samoadaptáciu. ES chromozóm obsahuje totiž okrem vektora parametrov objektu aj parametre stratégie a obe časti chromozómu sú vystavené mutáciám (resp. rekombináciám). Prispôsobovanie sa jedinca tak prebieha na dvoch úrovniach: na úrovni genotypickej (zložiek vektora parametrov) a na úrovni fenotypickej (charakteristík modelu funkcie vhodnosti - štandardnej odchýlky a korelačných koeficientov). Prispôsobovanie na fenotypickej úrovni vtláča ES rysy lamarckizmu.