|
||
Algoritmus a teorie k tomuto algoritmu je převzata z literatury [11]. Text i samotný algoritmus je modifikován pro potřeby tohoto kurzu.
Algoritmus diferenciální evoluce byl poprvé publikován v roce 1995 R. Storn a K. Price. Během několika let se stal velmi oblíbenou metodou uplatňovanou na optimalizační problém hledání globálního extrému u multimodálních funkcí. Metoda využívá tradiční evoluční operátory, jako je křížení, mutace a selekce. V algoritmu lze také využít princip adaptivity, který je uplatněn na parametr při výpočtu - mutaci - jedince (prvku - vektoru), se kterým se vybraný jedinec (rodič) bude křížit.
Experimentální výsledky i zkušenosti ukazují, že diferenciální evoluce konverguje rychleji než jiné stochastické algoritmy.
Princip diferenciální evoluce je založen na výběru lepšího jedince ze dvou jedinců - selekci. Těmito jedinci jsou - rodič a jeho potomek, který vznikl křížením rodiče s nově vytvořeným jedincem vzniklým mutací jedinců. Lepší jedinec z těchto dvou porovnávaných jedinců je následně zařazen do populace, která kompletně nahradí populaci rodičů.
Otázkou je, jak vytvořit jedince, který bude následně křížen s rodičem. Existuje několik způsobů tvorby takového jedince. Prvním způsobem označovaným jako RAND je generování jedince (mutace) za pomocí tří navzájem různých náhodně vybraných jedinců z populace rodičů. Tito jedinci musí dále splňovat podmínku, že musí být také různí od právě vybraného jedince z populace rodičů (viz 
).
kde:
• 
… Nově vytvořený - zmutovaný jedinec.
• 
… První, druhý, třetí náhodně vybraný jedinec ze staré populace - populace rodičů.
• 
… Parametr adaptivního pravidla, 
.
Druhým základním způsobem generování nového jedince pomocí mutace je metoda BEST. Tato metoda, na rozdíl od předchozí metody, využívá při generování nového jedince čtyři náhodně navzájem různé body a také nejlepšího jedince v populaci, který je různý od těchto jedinců. Dále platí, že nejlepší jedinec a vybraní čtyři jedinci musí být různí od právě vybraného jedince z populace rodičů. Rovnice, pomocí níž je vygenerován nový jedinec, má tvar:
kde:
• … Nově vytvořený - zmutovaný jedinec.
• 
… Nejlepší jedinec v populaci - nejmenší hodnota účelové funkce při minimalizaci cíle.
• 
… První, druhý, třetí, čtvrtý náhodně vybraný jedinec ze staré populace - populace rodičů.
• … Parametr adaptivního pravidla, .
Jak již bylo řečeno, nový potomek vzniká křížením nově vygenerovaného (vypočteného - zmutovaného) jedince a původního jedince (vybraného rodiče z populace rodičů). Takto vzniklý potomek je následně testován, zda je lepší nebo horší, než vybraný rodič.
Potomek při křížení vznikne tak, že potomek je kopií vybraného rodiče. Pokud je náhodné číslo Rj menší nebo rovno specifikované konstantě CR, pak souřadnice rozhodovací proměnné potomka 
je rovna souřadnici rozhodovací proměnné zmutovaného jedince 
. Pokud náhodné číslo je větší než specifikovaná konstanta CR, pak souřadnice rozhodovací proměnné potomka je rovna souřadnici rozhodovací proměnné 
-tého vybraného rodiče 
.
Druhou možností je nevytvářet kopii rodiče, ale postupně plnit (pomocí funkce AddListItem) na začátku prázdného jedince (vektor) souřadnicemi rozhodovacích proměnných rodiče, pokud je splněna podmínka pravděpodobnosti náhrady souřadnice. Pokud podmínka splněna není, pak se bude jedinec plnit souřadnicemi zmutovaného jedince.
Pokud žádná souřadnice potomka nebyla během tohoto procesu přepsána souřadnicí zmutovaného jedince , nebo při volbě CR = 0, pak se nahrazuje jedna náhodně vybraná r-tá souřadnice rozhodovací proměnné potomka (kde 
), souřadnicí rozhodovací proměnné zmutovaného jedince .
kde:
kde:
• 
… Potomek vzniklý křížením nově vytvořeného jedince a rodiče.
• … Souřadnice rozhodovací proměnné potomka.
• … Nově vytvořený jedinec pomocí mutace, který bude použit pro křížení.
• … Souřadnice rozhodovací proměnné nově vytvořeného jedince mutací.
• 
.
• … Souřadnice rozhodovací proměnné rodiče.
• 
… Náhodné reálné číslo pro j-tou rozhodovací proměnnou.
• CR … Pravděpodobnost nahrazení souřadnic rozhodovacích proměnných potomka.
• 
… Index rozhodovací proměnné.
• r … Náhodně zvolený index rozhodovací proměnné potomka, který bude přepsán souřadnicí rozhodovací proměnné nově vygenerovaným jedincem pro křížení.
• 
… Rozměr prohledávaného prostoru - počet rozhodovacích proměnných.
• 
… Obor reálných čísel.
• 
… Obor přirozených čísel.
V algoritmu může být uplatněna adaptivita pomocí mutačního parametru podle Ali a Törna, které bude přepočteno v každém iteračním kroku - vygenerování potomka. Pravidlo lze popsat takto:
kde:
• … Parametr adaptivního pravidla.
• 
… Konstanta adaptivního pravidla, která zabezpečuje aby 
, 
, doporučená hodnota 
.
• 
… Největší hodnota účelové funkce jedince, ze všech jedinců v populaci.
• 
… Nejmenší hodnota účelové funkce jedince, ze všech jedinců v populaci.
Předpokládá se, že adaptivní pravidlo udržuje v počátečním stádiu diverzitu prohledávání - diverzifikace a v pozdějším stádiu zvyšuje intenzitu prohledávání - intenzifikace. Díky tomu roste spolehlivost hledání a rychlost konvergence.
Výhodou algoritmu je jeho jednoduchost implementace a výpočetně nenáročné generování - křížení - nového potomka.
Nevýhodou diferenciální evoluce je poměrně vysoká citlivost na nastavení vstupních parametrů algoritmu a CR.
Storn a Price doporučují volit hodnoty:
• 
…Velikost populace rodičů
tj. délka seznamu 
, doporučená hodnota 
.
• … Parametr adaptivního pravidla, doporučená hodnota 
.
• CR … Pravděpodobnost nahrazení souřadnic rozhodovacích proměnných, doporučená hodnota CR = 0.5.
Je doporučeno, že tyto hodnoty se mají na základě empirických zkušeností během hledání modifikovat. Záleží zde především na zkušenosti a dobré intuici uživatele. Sami autoři ve svých testovacích úlohách užívají pro různé úlohy velmi odlišné hodnoty vstupních parametrů:
• 
.
• 
.
• 
.
DEBest - funkce (viz 
), která generuje nového jedince na základě mutace pomocí již popsané metody BEST. Nejprve je provedena kopie vstupní populace rodičů (viz řádek 2). To je provedeno z důvodu, že populace bude dále modifikována (tento krok je proveden kvůli odlišení originální původní populace, se kterou bude pracovat dále v další funkci v její nezměněné podobě před vstupem do funkce DEBest; samozřejmě, že tento krok z hlediska programátora není nutný, protože jde o lokální proměnnou, ale tento kurz zaměřen pro veřejnost, která nemusí mít s programováním žádné zkušenosti). Kopie vstupní populace je vzestupně (minimalizace cíle) setříděna podle hodnot účelové funkce jedinců (řádek 3). Vzestupné třídění populace je provedeno proto, aby bylo možné provést mutaci na základě principu metody označované jako BEST. K výpočtu totiž potřebujeme nejlepšího jedince v populaci (řádek 4). Tento jedinec je nyní umístěn v populaci jako první. Protože je podmínkou metody, že vybraní čtyři jedinci musí být různí od nejlepšího jedince, provedeme odstranění nejlepšího prvku z populace - první položka v seznamu tj. index i = 0 (řádek 5). Další podmínkou je, že vybraní čtyři jedinci musí být různí od vybraného rodiče. Proto pokud již tento rodič nebyl odstraněn (byl nejlepší v populaci), je vyhledán v populaci (řádek 6) a bude vymazán (řádek 7).
Nyní je možné vybrat čtyři navzájem různé jedince. To je provedeno pomocí selekce bez substituce - jedinci se neopakují - RandomSelectw (řádek 8). Následně je provedeno dosazení těchto prvků do rovnice pro vytvoření nového jedince (řádek 14), který bude použit při křížení s rodičem v hlavním programu. Protože se jedná o součin vektorů, musí být proveden výpočet pro každý prvek těchto vektorů - pro všechny souřadnice rozhodovacích proměnných jednotlivých jedinců (řádek 13). V rovnici je použit parametr adaptivního pravidla, který ovlivňuje vzdálenost nově vytvořeného jedince od nejlepšího jedince (řádek 14). Parametr se může při každém výpočtu nového jedince pro křížení měnit. To závisí na vyhodnocení podmínky adaptivního pravidla umístěného v jiné části programu.
Při generování jedince pro následné křížení mohlo dojít k tomu, že jedinec se dostal mimo prohledávaný prostor. Proto je tato situace ošetřena pomocí metody perturbace - zrcadlení, která zajišťuje přepočet jednotlivých souřadnic rozhodovacích proměnných tak, aby ležely uvnitř prohledávaného prostoru (řádek 15). Jako výsledek funkce je navrácení vygenerovaného jedince pro následné křížení s vybraným rodičem (řádek 16).
DE - algoritmus (viz 
, 
, celý algoritmus 
) popisuje podstatu diferenciální evoluce. Prvním krokem algoritmu je specifikování, že velikost populace rodičů a potomků je stejná (řádek 2). Následuje počáteční nastavení parametru adaptivního pravidla hodnotou, jakou nastavil uživatel (řádek 3). V průběhu optimalizace bude tento parametr měněn na základě vyhodnocení podmínky uvnitř adaptivního pravidla. Dále je získána dimenze prohledávaného prostoru (řádek 4). Tento parametr bude s největší pravděpodobností zadávat uživatel v závislosti na počtu rozhodovacích proměnných v simulačním modelu. Dalším krokem je vytvoření počáteční populace o m jedincích (řádek 5). Tito jedinci jsou generování náhodně na základě rovnoměrného rozdělení. Je na uživateli, jestli má přibližnou představu o průběhu účelové funkce a je schopen specifikovat počáteční populaci sám. Uvnitř smyčky (řádek 6), jejíž ukončení je závislé na splnění kritéria ukončení, bude probíhat postupné vytváření populace potomků (řádek 7). Pro vytvoření nového potomka je zapotřebí vybrat jeho rodiče (řádek 8). Lze říci, že každý potomek má odlišného rodiče, protože dochází k postupnému výběru všech rodičů a vytváření jejich potomků (řádek 7a 8). Za pomoci předchozí popsané funkce je vygenerován nový jedinec (řádek 9), jenž bude křížen s vybraným rodičem za účelem vytvoření jejich nového potomka. Jak již bylo řečeno, nový potomek vznikne křížením rodiče a nově vytvořeného jedince pro křížení (dá se říci druhého rodiče). Protože křížení může probíhat jen s jistou pravděpodobností (řádek 12), musí být zaznamenáno, zda takové křížení proběhlo. Proto je v algoritmu používána jako informace o uskutečnění křížení zavedena logická proměnná, která je na začátku na hodnotu False - křížení neproběhlo (řádek 10). Křížení za účelem vygenerování potomka je prováděno tak, že nejprve je vytvořena kopie původního rodiče (řádek 8). U této kopie pak dochází k postupnému přepisování souřadnic rozhodovacích proměnných souřadnicemi rozhodovacích proměnných nově vygenerovaného jedince vzniklého mutací (řádek 13), pokud je náhodné číslo menší nebo rovno specifikované konstantě CR (řádek 12). Protože k tomuto jevu dochází pouze s jistou pravděpodobností, mohlo se také stát, že žádná souřadnice rozhodovacích proměnných jedince nebyla přepsána. Pokud se tak stalo (řádek 16), je náhodně zvolena jedna ze souřadnic rozhodovacích proměnných (řádek 17) a ta je přepsána hodnotou souřadnice rozhodovací proměnné jedince určeného pro křížení (řádek 18). U nově vytvořeného potomka je následně porovnána kvalita oproti svému rodiči - pomocí hodnoty účelové funkce. Pokud je potomek lepší (řádek 20), je zařazen do populace (řádek 21), která přejde do dalšího kola algoritmu (řádek 29). Po každém zařazení nového jedince do populace je vhodné přepočítat parametr adaptivního pravidla. Ten je závislý na vyhodnocení podmínky (řádek 25), která určuje poměr hodnot maxima a minima hodnoty účelové funkce v populaci. Parametr pak určuje, na kolik bude vzdálen nově vytvořený jedinec od nejlepšího jedince v populaci. Po naplnění populace potomků je stará generace rodičů nahrazena novou populací potomků (řádek 29). Všechny dosud popsané operace se provádějí do té doby, dokud není splněna některá z podmínek kritéria ukončení. Pokud dojde k ukončení algoritmu, je jako výsledek poskytnuta množina optim (řádek 31) z poslední již konvergované populace - v průběhu algoritmu byly totiž horší jedinci nahrazováni lepšími.