|
||
Downhill je jednoduchý a populární algoritmus pro hledání globálního extrému. Simplex S je množina bodů, která obsahuje minimálně n+1 bodů, kde n vyjadřuje rozměr prostoru rozhodovacích proměnných. Tyto body jsou nekomplanární tj. lineárně nezávislé body.
Verbálně lze metodu Downhill Simplex v případě minimalizace popsat jako jakýsi „píďalkovitý“ pohyb simplexu v prohledávaném prostoru 
směrem k oblasti s nižšími funkčními hodnotami. Mezi variantami metody existují i takové, kde simplex na počátku není generován náhodně, ale počáteční body simplexu se záměrně volí tak, aby zcela jistě splňovaly podmínku nekomplanarity (afinní nezávislosti), což volně řečeno znamená, že body simplexu neleží v podprostoru s menší dimenzí, než má prohledávaný prostor, např. při n=2 tři body tvořící simplex neleží na přímce. [11]
V algoritmu popisujícím princip metody Downhill Simplex (viz 
) jsou zachyceny jeho jednotlivé fáze.
Základní fáze algoritmu jsou:
Využití těchto základních fází v daném příkladu je popsáno v následujícím textu.
Jako první krok algoritmu (viz ) je vygenerování počáteční skupiny n+1 bodů simplexu (viz , řádek 2, dále budou značeny pouze indexy řádků tohoto algoritmu), které jsou uloženy v seznamu S představující simplex.
Dokud nebude dosaženo podmínky ukončení algoritmu (řádek 3), budou se provádět následující popsané kroky.
Seznam S (simplex) je setříděn (řádek 4) na základě funkční hodnoty každého jeho prvku (bod v simplexu), kde poslední prvek seznamu S[n+1] představuje nejhorší prvek seznamu (bod v simplexu s nejhorší - při minimalizaci nejvyšší - hodnotou účelové funkce). Dále je vypočteno těžiště ze všech prvků kromě nejhoršího prvku umístěného na konci seznamu - kromě nejhoršího prvku simplexu (řádek 5).
Reflexi si lze představit jako překlopení nejhoršího prvku (bodu) simplexu přes těžiště simplexu M - na obrázku (viz 
) nejhorší prvek představuje prvek S[2]. Jestliže tento nově získaný prvek R splňuje podmínku, že jeho hodnota účelové funkce (v případě minimalizace) je v intervalu účelové funkce nejlepšího prvku a nejhoršího prvku seznamu (řádek 7), je tento nový prvek R přijat namísto dosud nejhoršího prvku seznamu. Podmínka vypadá takto:
kde:
• 
… Hodnota účelové funkce nejlepšího prvku (bodu).
• 
… Hodnota účelové funkce prvku získaného pomocí reflexe.
• 
… Hodnota účelové funkce nejhoršího prvku.
Obvykle se koeficient reflexe volí 
. Tento jednoduchý pohyb byl poprvé prezentován v první verzi simplexového algoritmu definovaným Spendleyem a jeho kolektivem v roce 1962. Nealder a Mead předchozí algoritmus rozšířili o další speciální operátory, které byly navrženy pro zrychlení optimalizačního procesu. Operátory deformují simplex za účelem lepšího přizpůsobení účelové funkci.
Pokud je nový prvek R lepší než dosud nejlepší známé možné řešení S[0], pak je logické roztáhnout simplex do tohoto slibného směru. Tento přístup je zachycen na dalším obrázku (viz 
).
V dalším kroku (řádek 9) je vygenerován nový prvek E (obvykle se koeficient expanze volí 
). Jestliže nový bod E není lepší než předchozí bod R (řádek 10), pak je namísto dosud nejhoršího řešení dosazen bod R (řádek 11). Pokud je tomu ale naopak, nejhorší řešení je přepsáno novým bodem E (řádek 10).
V případě, že získané R není lepší než nejhorší bod simplexu S[n] (řádek 15), simplex se zkracuje do nového prvku C, vytvořeného mezi prvku R a těžištěm simplexu M (řádek 16).
Princip tzv. kontrakce je zachycený na dalším obrázku (viz 
). V tomto případě je koeficient kontrakce nastaven na hodnotu 
. K nahrazení nejhoršího prvku simplexu S[n] prvkem C dojde pouze tehdy, jestliže hodnota účelové funkce C je lepší než funkční hodnota R.
Pokud nebyla splněna ani jedna z předchozích podmínek porovnání hodnot účelové funkce u předchozích prvků, simplex se redukuje tak, že všechny jeho body, kromě nejlepšího S[0], se posunou ve směru současného optima S[0]. Koeficient redukce je běžně nastaven na hodnotu 
. Tak je tomu i v případě redukce nakreslené na dalším obrázku (viz 
).
Je zajímavé, že je jistá podobnost mezi evolučními algoritmy a metodou Downhill Simplex, což vede k její hybridizaci s evolučními a jinými algoritmy. V literatuře [18] se prokazuje, že metoda může být považována za evoluční algoritmus se speciálními operátory selekce a mutace. Každý prohledávací krok Nelderova a Meadova algoritmu by mohl být považován za n-rozměrnou reprodukci v prostoru prohledávání. Existuje také jistá podoba mezi operátorem reflexe a prohledáváním pomocí Diferenciální evoluce, PSO - optimalizace založená na rojení. Takové podobnosti jsou popsány i v literatuře [19]. [6]