Globální optimalizace
Kritérium ukončení

| Úvod a cíle |

Velmi důležitou složkou optimalizačního algoritmu, která zajistí, že se optimalizační algoritmus při prohledávání prohledávaného prostoru nedostane do nekonečné smyčky, je tzv. kritérium ukončení (Termination Criterion). Pokud je operace kritéria ukončení vyhodnocena logickým výrazem (hodnoty tohoto výrazu nabývají True nebo False), optimalizační proces se zastaví a navrátí výsledek optimalizačního procesu (viz ).

Ukončovacími kritérii jsou například:

1. Definování mezí:

> o Překročení výpočetního času, který byl nastaven. Pokud uživatel zadá hodnotu tohoto kritéria, mělo by mít nejvyšší prioritu.

> o Celkový počet iterací (vygenerovaných prvků nebo iterací algoritmu) je vyčerpán - počet vyhodnocení účelové funkce potřebný k dosažení podmínky ukončení:

> kde

> > • … Iterace (kolo) algoritmu.

> > • K … Maximální počet provedených experimentů (ohodnocení účelové funkce).

> o Pokud je řešení problému známé - VTR - Value To Reach (např. je známa hodnota účelové funkce). Takové kritérium ukončení bude použito zejména při testování algoritmu.

2. Ukončení, pokud je detekováno, že už nemohou být provedena žádná zlepšení pro specifikovaný počet iterací - optimalizační proces může být zastaven, pokud je detekováno, že už nemohou být provedena žádná zlepšení pro specifikovaný počet iterací. To znamená, že proces konvergoval k nadějnému řešení, kde už pravděpodobně nemohou být provedena žádná další zlepšení.

> o Poměr hodnoty kriteriální funkce nejlepšího aktuálního prvku vůči nejlepšímu prvku z předchozího kola algoritmu. V případě, že jsou použity evoluční algoritmy, lze tento poměr vyjádřit např. jako poměr průměru nebo mediánu fitness populace potomků vůči průměru nebo mediánu fitness populace rodičů.

> o Rozdíl nejlepší a nejhorší hodnoty účelové funkce, které byly doposud nalezeny.

> Tuto podmínku ukončení je praktické formulovat tak, abychom předešli abnormálnímu ukončení programu např. v situaci, kdy prohledávání dojde do nekonečného cyklu. Proto je vhodné přidat další vstupní parametr algoritmu, což je maximální dovolený počet vyhodnocení účelové funkce (maximální počet provedených experimentů). Hledání pokračuje tak dlouho, dokud funkční hodnoty prvků v iteraci se liší více, než požadujeme, nebo dokud není dosaženo nejvyššího počtu vyhodnocení účelové funkce. [11]

> o Gradient

Z uvedených úvah je zřejmé, že pak lze rozlišovat následující čtyři typy ukončení prohledávání - platí při minimalizaci cíle: [11]

1. typ - Korektní ukončení - algoritmus splnil podmínku ukončení před dosažením maximálního dovoleného počtu iterací tím, že rozdíl nejlepší a nejhorší hodnoty účelové funkce, které byly doposud nalezeny, je menší než definovaná mez a současně se algoritmus dostatečně přiblížil globálnímu minimu.
2. typ - Pomalá konvergence - algoritmus se dostatečně přiblížil globálnímu minimu, ale prohledávání bylo ukončeno dosažením maximálního dovoleného počtu iterací.
3. typ - Předčasná konvergence (Premature Convergence) - rozdíl nejlepší a nejhorší hodnoty účelové funkce, které byly doposud nalezeny, je menší než definovaná mez, ale nebylo nalezeno globální minimum. Algoritmus skončil prohledávání v lokálním minimu, nebo se body populace přiblížily k sobě natolik, že jejich funkční hodnoty jsou velmi blízké.
4. typ - Úplné selhání - prohledávání bylo ukončeno dosažením maximálního dovoleného počtu iterací, aniž byl nalezen bod blízký globálnímu minimu.