|
||
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]