|
||
V kapitole jsou vytýčeny základní prvky globální optimalizace, které využívá většina metod globální optimalizace. Takovými prvky jsou:
Minimalizace (maximalizace)
Základním prvkem globální optimalizace je bezesporu nalezení globálního minima (maxima) na celém definičním oboru (prostor není omezen) nebo na množině přípustných řešení.
Některé algoritmy jsou ve své originální formě definovány pro jednoúčelovou optimalizaci. Takový algoritmus může být ale také definován jak pro maximalizaci nebo minimalizaci cíle, bez toho aniž by ztratil svoji všeobecnost (univerzálnost). V oblasti optimalizace je proto běžně užíván termín minimalizační proces.
Algoritmus hledající maximum dané účelové funkce:
může být transformován na úlohu hledání minima:
. [2]
Tedy minimum funkce:
je ve stejném bodě jako maximum funkce:
a naopak.
U optimalizačních metod proto postačí algoritmy, které hledají jen maximum nebo jen minimum (pokud nemají inverzi znaménka zabudovanou uvnitř algoritmu). [15]
Tento princip je zachycen na následujícím obrázku (viz 
).
Poznámka: V našem případě budou popisované algoritmy porovnávat kvalitu nově vygenerovaného prvku 
pomocí hodnoty účelové funkce daného prvku tj. 
. Hodnota účelové funkce bude získána na základě informací z proběhnutého simulačního experimentu - vyhodnocení simulačního modelu s konkrétním nastavením hodnot rozhodovacích proměnných - parametrů simulačního modelu. Takové algoritmy mohou být definovány jak pro maximalizaci tak minimalizaci cíle (nějaké funkce, hodnoty prvků v seznamu atd.), bez toho aniž by ztratily svoji univerzálnost. V dalším popisu optimalizačních metod proto budeme obecně používat minimalizaci účelového funkce.
CF - komparační funkce - (
), jejíž výstup poskytuje informaci, zda je hodnota účelové funkce prvku 
tj. 
lepší (horší, nebo stejná) než hodnota účelové funkce druhého prvku 
.
Princip je popsán v následujícím algoritmu (viz 
). Pokud je účelová funkce prvního prvku lepší než hodnota účelové funkce druhého prvku (viz , řádek 2 - dále bude uváděno jen číslo řádku), bude výstupem funkce číslo (-1).
Pokud je tomu naopak, tedy hodnota účelové funkce prvního prvku je horší než hodnota účelové funkce druhého prvku, výstupem funkce je číslo (1), (řádek 3). V ostatních případech, tj. když se hodnoty účelových funkcí obou prvků se rovnají, je výstupem funkce číslo (0). Jak již bylo řečeno, jedná se o minimalizaci jedné účelové funkce, která může využívat další metody pro převod vícekriteriální optimalizace na jednoúčelovou optimalizaci např. pomocí váženého součtu.
Pro maximalizaci hodnot účelové funkce dvou prvků tedy platí:
Iterace
Optimalizační algoritmy zpravidla iteračně ohodnocují prvky, aby bylo možné dosáhnout optima. Základním principem iterace je opakování určitého procesu v měnícím se kontextu, tedy opakované volání funkce v počítačovém programu. Jinými slovy lze říci, že hlavní iterací rozumíme proběhnutí jednoho hlavního kola algoritmu, tj. opakování specifické sekvence instrukce uvnitř algoritmu.
V rámci tohoto kurzu budeme pohlížet na iterační krok v optimalizačním algoritmu, jako na proces kdy je pracováno s jedním nebo několika prvky:
kde:
• 
… Iterační krok (kolo) algoritmu.
• 
… Počet hlavních kol algoritmu - konstanta definovaná uživatelem.
• 
… i-tý prvek.
• 
… Index prvku (značené od nuly - index položky v seznamu).
• 
… Počet vygenerovaných prvků v jednom kole algoritmu.
Optimalizační algoritmus obvykle na začátku vygeneruje jedno nebo více počátečních přípustných řešení (Initial Possible Solution). Druhou možností je, že počáteční přípustná řešení jsou zadána uživatelem, který může mít alespoň základní představu o průběhu účelové funkce a tím může ovlivnit průběh hledání optima. Počáteční přípustné/á řešení musí náležet množině přípustných řešení. Generování prvku v počáteční fázi optimalizačního algoritmu je možné na základě rovnoměrného rozdělení pomocí funkce 
- viz studijní článek "Metody práce s omezujícími podmínkami". Prvky je také možné generovat na základě normálního rozdělení pomocí funkce - 
- viz studijní článek "Metody práce s omezujícími podmínkami".
Prvek představuje z pohledu grafu účelové funkce bod (vektor), jehož jednotlivé pozice souřadnic na osách (tj. hodnot rozhodovacích proměnných) v n-dimensionálním prostoru jsou uloženy jako seznam. Přístup k jednotlivé souřadnici prvku na dané ose je realizován pomocí indexace - hranaté závorky (viz Algoritmus 1-2, řádek 5 - dále bude uváděn jen řádek).
Následující algoritmus (viz 
) popisuje vytvoření prvku na základě rovnoměrného rozdělení, jehož hodnoty rozhodovacích proměnných jsou náhodná čísla generované v rozsahu dolní meze a horní meze (řádek 5). Dolní mez náhodného čísla představuje dolní mez prohledávaného intervalu dané rozhodovací proměnné. Horní mez představuje horní mez prohledávaného intervalu.
Pokud prvek náleží množině nepřípustných řešení, musí být použita některá z metod práce s omezujícími podmínkami, např. opravný algoritmus, která prvek transformuje na prvek z množiny přípustných řešení.
V některých optimalizačních algoritmech se iterací rozumí generace - populace. Takovými algoritmy jsou zejména evoluční algoritmy, kde se v jednom iteračním kole algoritmu pracuje s několika (ve většině případů se všemi) prvky - populace.
Definujme tzv. relaci sousedství (Neighborhood Relation), která umožňuje pro každé přípustné řešení (prvek ) pomocí množiny transformací 
stanovit množinu přípustných bodů (prvků) s ním „sousedících“. Pro definici relace sousedství je důležitá podmínka dosažitelnosti, která požaduje, aby každé přípustné řešení bylo dosažitelné z libovolného jiného přípustného řešení postupnou aplikací relace sousedství.
Pro spojité úlohy můžeme sousedství definovat například jako m bodů na n -rozměrné kouli se středem v bodě 
. [16]
V oblasti evoluční algoritmů lze množinu transformací pojmout jako tzv. mutaci prvku (u evolučních algoritmů je prvku nazýván jedincem). Jedná se vlastně o transformaci jednotlivých složek původního prvku (hodnoty souřadnic jednotlivých rozhodovacích proměnných lze v oblasti evolučních algoritmů pojmout jako jednotlivé geny jedince), které jsou uloženy jako nový zmutovaný prvek 
. Proto následující algoritmus bude pojmenován jako mutace (viz 
).
Je samozřejmé, že takto získaný nový jedinec musí splňovat podmínku přípustnosti - musí patřit do množiny přípustných řešení.
Příkladem transformace (mutace) je vygenerování prvního prvku v sousedství původního prvku v nultém iteračním kole algoritmu. Tento princip je ilustrován na příkladu iterací v algoritmu na dalším obrázku (viz 
).
V každé iteraci jsou vygenerovány čtyři prvky v sousedství nejlepšího prvku (bodu) z předchozího kola algoritmu. Sousedství v tomto případě představuje obdélník, jehož délky hran jsou uloženy v seznamu délek intervalů 
.
V matematickém zápisu je uveden identický způsob generování prvku v okolí pomocí algoritmu - funkce Mutate:
kde:
• … Prvek vygenerovaný pomocí transformace (mutace) v nulté iteraci.
• 
… První transformace - argumentem je prvek 
.
• … Prvek, v jehož okolí je v nulté iteraci vygenerován pomocí transformace nový prvek.
Seznam obsahující jednotlivé délky intervalu má tedy délku 
, která představuje počet rozhodovacích proměnných. Každá jednotlivá délka uložená na j-té pozici v seznamu 
je podkladem pro výpočet dolní a horní meze intervalu, v němž se bude generovat náhodné číslo (hodnota rozhodovacího proměnné prvku), podle rovnoměrného rozdělení (viz , řádek 5).
Generování náhodného čísla představující souřadnici bodu na j-té ose (hodnotu rozhodovací proměnné) se děje na základě rovnoměrného rozdělení pomocí volání funkce Randomu. Dolní mez pro generování náhodného čísla je rovna polovině délky intervalu pro jednotlivou rozhodovací proměnnou (v grafu účelové funkce tato délka představuje délku umístěnou v seznamu délek okolí bodu, ve kterém bude generován další prvek) v seznamu odečtené od souřadnice transformovaného prvku (řádek 5). Horní mez je rovna součtu poloviny délky příslušného intervalu a souřadnice jednotlivé rozhodovací proměnné vybraného prvku (řádek 5). Absolutní hodnota délky intervalu v čitateli předchází možné chybě v zadávání délky do seznamu (řádek 5).
Druhou možností generování bodů v sousedství je za pomoci symetrického normálního rozdělení. Funkce generování náhodného čísla je využita při generování prvku v sousedství prvku (viz 
).