|
||
Obecně se dá říci, že evoluční algoritmy mohou být použity na „jakoukoliv“ funkci. Problémy může mít evoluční algoritmus tehdy, jestliže průběh účelové funkce je typu „jehla v kupce sena“ - jsou to ploché funkce, jejichž extrém je jen „dírou“ v této rovině. Žádné další přídavné informace jako gradient atd. nejsou obvykle nutné.
Podstatou evolučních výpočetních technik (EVT) je evoluční princip uplatňovaný v přírodě. Principem je tzv. přírodní výběr, který lze vyjádřit jako „přežití nejlépe přizpůsobeného jedince“.
Poznámka: V případu evolučních algoritmů se namísto pojmu „prvek“ využívá termín „jedinec“ (Individual). Skupina jedinců pak přestavuje populaci - generaci (Population).
Aby byla zachována autetičnost citace, v některých případech bude namísto pojmu prvek, použit termín jedinec.
Snahou tedy je napodobit přírodní výběr, kde přežívá silnější jedinec a tento výběr využít v oblasti optimalizace. Mírou přizpůsobení je tzv. „fitness“ jedince.
Jedinci s vyšší fitness mají větší pravděpodobnosti přežití a větší pravděpodobnost reprodukce svých genů do generace potomků. Kromě reprodukce se v populačním vývoji uplatňuje i tzv. mutace, což je náhodná změna genetické informace některých jedinců v populaci. [11]
Klasické genetické algoritmy používají operací, jako jsou selekce, křížení a mutace pro simulaci procesu reprodukce. Evoluční algoritmy nejsou vhodné pro aplikace, kdy lze snadno zjistit gradienty účelové funkce nebo účelová funkce je výpočtově velice náročná.
Evoluční strategie obvykle vytvářejí potomky pouze modifikací (např. mutací) jednoho rodiče, tj. nemusí ale mohou používat operaci křížení.
Na obrázku (viz 
) je zobrazen základní cyklus evolučních algoritmů, vyjadřující myšlenky Darwinova přírodního (přirozeného) výběru jedinců v populaci.
Všichni jedinci jsou v populaci implementováni pomocí téže datové struktury, ve které je zaznamenána reprezentace každého jednotlivce (v případech simulační aplikace zakódování vektorového argumentu kriteriální funkce). [17]
Ve stádiu inicializace populace je vývojový čas nastaven na hodnotu nula. Obvykle se při inicializaci populace využívá generátoru náhodného rozdělení, pomocí kterého se vytvoří populace počátečních jedinců. Počáteční populace může být také sestavena z jedinců určených na základě znalosti úlohy - pokud máme tyto informace.
Operace vyhodnocení v sobě skrývá výpočet kvality všech jedinců v populaci. Navíc se obvykle vyhledá nejlepší jedinec a vypočtou se i jisté statistické vlastnosti populace, jako její průměr (tj. průměrné ohodnocení jedinců), rozptyl a podobně.
Selekce simuluje v EVT proces přírodního výběru - zápasu o přežití - a vybírá jedince z předchozí populace do nové populace, obvykle na základě jejich hodnocení. Jedinci jsou v rámci selekce vybíráni zpravidla pravděpodobnostním mechanismem, přičemž lepší jedinci mají vyšší šanci být vybráni do následující generace. Již z tohoto náznaku selekčního operátoru je vidět, že průměrné ohodnocení následující populace by mělo být lepší ve srovnání s populací původní. Průměrní jedinci se totiž objeví v nové populaci přibližně ve stejném počtu jako v populaci původní, nadprůměrní v počtu vyšším, podprůměrní v počtu nižším. [6]
Inovativním prvkem v celém vývojovém procesu je změna realizovaná pomocí tzv. rekombinačních operátorů. Ty pracují nad reprezentací prvků prostřednictvím struktur a jsou obvykle dvou typů:
1. Mutace - vytvářející nové individuum „malou“ změnou původního jedince. Mutace je tedy operací unární upravující konkrétního prvek.
2. Křížení - generování jednoho či více jedinců z několika (dvou či více) jedinců - rodičů. Zpravidla vstupují do operace křížení dva rodiče - binární křížení. Eibenova studie (Eiben A. E. a kol.: Genetic Algorithms with Multiparent Recombination, New York, 1994) však ukázala pozitivní vliv „orgií“ na chování algoritmů EVT.
Změnových či rekombinačních operátorů v EVT existuje vedle křížení a mutace více. Podstatné však je, že jsou vždy těsně svázány s konkrétní reprezentací jedinců (se strukturami) a na ní také závisí jejich skutečná implementace.
Předpokládá se, že čím déle evoluční algoritmus běží, tím lepší výsledek bude reprezentován nejlepším jedincem v populaci. Selekce může způsobit takovou homogenizaci populace, že změnové operátory nemohou již vnést do evolučního procesu nic zásadně nového. Všechny tyto jevy mohou být zahrnuty do formulace “zastavovacího pravidla”. [8]