|
||
Algoritmus a teorie k tomuto algoritmu je převzata z literatury [11]. Text i samotný algoritmus je modifikován pro potřeby tohoto kurzu.
Původní nejjednodušší verzi algoritmu navrhli v šedesátých létech Schwefel a Rechenberg. Základní myšlenka je podobná slepému náhodnému prohledávání, ale rozdíl je v tom, že nový jedinec se generuje jako mutace původního jedince tak, že jednotlivé složky jedince se změní přičtením hodnot normálně rozdělených náhodných veličin:
kde:
• 
… Zmutovaný jedinec na základě normálního rozdělení.
• 
… Původní jedinec.
• 
… Vektor náhodný čísel.
• 
… Náhodné číslo vygenerované na základě normálního rozdělení = prvek vektoru (prvky jsou navzájem nezávislé).
• 
… Index dimenze - rozhodovací proměnné 
.
• 
… Počet dimenzí - rozhodovacích proměných simulačního modelu.
• 
… Normální rozdělení s definovanou střední hodnotou 0 a rozptylem 
.
• 
… Velikost populace určené k páření 
.
K popisu evolučních strategií se v literatuře obvykle používá notace 
, která značí počet rodičů (
) a 
, jenž značí počet zplozených potomků (
, > ).
V případě generační vývojové strategie je tato strategie popsána jako evoluční strategie 
, kde generace potomků je tvořena jedinci s nejlepšími hodnotami účelové funkce (fitness funkce) z jedinců populace potomků. Rodičovská generace je tedy kompletně nahrazena nejlepšími jedinci z populace potomků.
V druhém případě postupné vývojové strategie, označení 
je generace potomků tvořena jedinci s nejlepšími funkčními hodnotami ze všech jedinců jak rodičovské populace, tak populace potomků.
V literatuře se doporučuje, aby velikost populace potomků byla volena několikanásobně větší než velikost rodičovské populace . Také se uvádí, že varianta obvykle konverguje pomaleji než varianta , ale s menší tendencí ukončit prohledávání v lokálním extrému.
Operátorem selekce je výběr lepšího jedince z dvojice (tzv. turnajový výběr).
Jak ale volit hodnoty směrodatných odchylek pro mutaci? V předchozí rovnici byly použity shodné a konstantní směrodatné odchylky. Z vývojového diagramu je patrné, že hodnoty směrodatných odchylek se v každém iteračním kroku mohou měnit v závislosti na výsledcích optimalizačního procesu. Tyto odchylky jsou uloženy v seznamu 
(viz 
). Přístup k prvkům každé dimenze (rozhodovací proměnné) v tomto seznamu je pomocí hranatých závorek.
Rechenberg studoval vliv velikosti mutace při generování potomka, tj. hodnot na rychlost konvergence algoritmu a na dvou jednoduchých funkcích a odvodil tzv. pravidlo jedné pětiny úspěšnosti. Empiricky pak byla ověřena užitečnost tohoto pravidla i pro jiné funkce. Hodnoty směrodatných odchylek se v k-té iteraci optimalizačního algoritmu hledání upravují podle pravidla vyjádřeného rovnicí:
kde:
• 
… Směrodatná odchylka j-té dimenze - prvek v seznamu směrodatných odchylek.
• … Index dimenze - rozhodovací proměnné.
• 
… Vstupní parametr, který určuje zmenšování nebo zvětšování hodnot směrodatných odchylek podle relativní četnosti úspěchu 
v předchozích 
iteračních krocích algoritmu. Obvykle se volí hodnota 
.
• 
… Vstupní parametr, který určuje zmenšování nebo zvětšování hodnot směrodatných odchylek podle relativní četnosti úspěchu. Obvykle se volí hodnota 
.
• 
… Iterační krok algoritmu.
• … Počet předchozích iteračních kroků algoritmu, ve kterých se měří relativní četnost úspěchu - . Úspěchem v případě minimalizace je, když 
.
• … Původní jedinec.
- algoritmus evoluční strategie (viz , 
, celý algoritmus 
) - varianta postupné vývojové strategie - na začátku algoritmu je vytvořen prázdný seznam relativních četností úspěchů (viz řádek 1). Tento seznam bude sloužit pro ukládání hodnoty 1 (řádek 16) pokud byl vygenerován lepší jedinec, než je jedinec ze starší populace. Vyhodnocení, zda je jedinec lepší, je uskutečněno na základě porovnání hodnot účelové funkce obou jedinců (řádek 15). V opačném případě bude do seznamu relativních četností úspěchu uložena 0 (řádek 17). Nový jedinec vznikl na základě mutace původního jedince (řádek 11), který byl pro tento účel vybrán. Mutace byla provedena pomocí normálního rozdělení (řádek 11). Výběr jedinců - jejich indexů - je postupný (řádek 10) až do té doby, dokud nedojde k naplnění nové populace, jejíž velikost je dána. Poněvadž jedinců v nové populaci může být více, než jedinců ve staré populaci, je použit trik, který zajišťuje, že pokud bude index větší, než je velikost staré populace, je tento index zkrácen o hodnotu násobku velikosti staré populace - v algoritmu je využita funkce mod - zbytek po celočíselném dělení (řádek 11). Protože mohl nastat případ, že takto vygenerovaný jedinec mohl padnout do množiny nepřípustných řešení - dostal se mimo prohledávaný prostor, je použit opravný algoritmus perturbace (řádek 12). Jak již bylo řečeno, seznam relativních četností úspěchů je postupně plněn - přidávána na konec seznamu buď 1, nebo 0, podle toho, zda je jedinec lepší, nebo horší. Seznam má zachovávat konstantní definovanou délku, tj. je řečeno, kolik kroků zlepšení nebo zhoršení má být zapamatováno. Pokud seznam četností úspěchů překročil specifikovanou délku (řádek 13), bude umazán první prvek s indexem 0 (řádek 14). Toto umazání prvku je prováděno proto, aby mohla být na konec seznamu přidána další informace, zda nový jedinec byl lepší nebo horší. Výpočet relativní četnosti úspěchů je prováděn tak, že jsou sečteny všechny prvky seznamu relativní četnosti úspěchů a tato suma je podělena délkou tohoto seznamu (řádek 21). Pokud relativní četnost úspěchů je menší než specifikovaná konstanta (řádek 21), dochází ke zmenšení směrodatných odchylek pro všechny směry - rozhodovací proměnné v prohledávaném prostoru, které jsou uloženy v seznamu směrodatných odchylek. Algoritmus prohledává menší prostor okolo starého jedince tím způsobem, že generuje - mutuje jedince v populaci (prvky, body v prohledávaném prostoru), které pak zkoumá, tzn., zjišťuje jejich kvalitu pomocí hodnot účelové funkce. Směrodatné odchylky v seznamu jsou použity při mutaci starého jedince na nového (řádek 11). Tím je určována rychlost konvergence algoritmu - jemnost prohledávaní definovaného prohledávaného prostoru. V případě, že vypočtená relativní četnost úspěchů je menší, než specifikovaná konstanta, bude uskutečněno jemnější prohledávání prostoru - tzv. exploatace (Exploiation) - intenzifikace - snaha zlepšovat dosavadní známé řešení pomocí malých změn, které vedou k novým podobným zlepšeným prvkům. Pokud vypočtená relativní četnost úspěchů byla větší než definovaná konstanta, dochází k širšímu prohledávání prostoru - explorace (Exploration) - diverzifikace. Pokud vypočtená relativní četnost úspěchů byla shodná s definovanou konstantou, směrodatné odchylky se nemění.
Až je nová populace naplněna, jsou do staré populace přidány prvky z nové populace (řádek 29) a je provedeno ohodnocení fitness na základě vzestupného setřídění populace (minimalizace cíle) podle hodnot účelové funkce - procedura AssignFitnessRank (řádek 30). Dalším krokem je provedení turnajové selekce (řádek 31) se substitucí - jedinci se mohou v další populaci vyskytovat i několikrát. V literatuře [11], ze které je použit daný algoritmus, je namísto turnajové selekce použita TruncationSelect - výběr několika nejlepších prvků z populace, i když v textu se radí použít turnajovou selekci.
Jako výsledek algoritmu při splnění některé z definovaných kritérií ukončení jsou poskytnuti jedinci - množina optim, kteří byly extrahováni z poslední známé populace (řádek 33).