Jaké typy optimalizačních funkcí se používají pro testování algoritmů a proč jsou tak odlišné?

Při vývoji a testování metod pro globální optimalizaci se v praxi používá sada tzv. benchmarkových funkcí. Tyto funkce nejsou určeny pro praktické nasazení, ale pro systematické hodnocení schopností algoritmů – tedy jejich přesnosti, robustnosti a efektivity v různých typech prostředí. Jsou konstruovány tak, aby reprezentovaly specifické vlastnosti problémů, s nimiž se může optimalizační metoda setkat. Rozdíly mezi nimi jsou zásadní, protože každá z těchto funkcí modeluje jiný typ výzev.

Rastriginovy funkce, které se vyskytují v několika variantách, mají výrazně odlišné definiční obory. Verze Rastrigin01 je diskrétní a omezuje hodnoty proměnných na malý počet konkrétních čísel – od −1 do 3. Tím se z ní stává funkce, která testuje algoritmy v extrémně omezeném, avšak vysoce kombinatorickém prostoru. Oproti tomu Rastrigin02 definuje proměnné na širším, rovněž diskrétním rozsahu od −10 do 30. Obě tyto varianty sdílí typickou strukturu Rastriginovy funkce – kombinaci kvadratických členů a oscilací, která způsobuje výskyt mnoha lokálních minim a testuje schopnost algoritmu nalézt globální optimum.

Sphere funkce má podobnou strukturu, ale zachází se všemi proměnnými stejně. Vysoká symetrie a hladkost této funkce ji činí základním testem pro optimalizační metody – její úloha spočívá spíše v testování základní schopnosti algoritmu pracovat efektivně v konvexním prostředí, než ve schopnosti zvládat komplexitu.

Zcela odlišnou úlohu plní funkce označená jako F16. Tato šestnáctirozměrná funkce je založena na specifickém interakčním vzorci mezi proměnnými, který je určen dvěma pevně danými maticemi součinitelů. Tato konstrukce zavádí složité nelineární interakce mezi proměnnými a znemožňuje jednoduchou dekompozici problému. Optimální hodnota zde není nulová, ale konkrétní, známá konstanta – 25.875. Funkce tohoto typu slouží k testování schopnosti algoritmu zvládat strukturované, avšak neprůhledné výzvy.

V kontrastu k výše uvedeným stojí množina tzv. omezených (constrained) optimalizačních problémů. Ty přidávají další vrstvu složitosti: nejenže je třeba optimalizovat cílovou funkci, ale současně musí být splněny konkrétní podmínky. Například problém g06 má dvě nelineární omezení a rozsah hodnot proměnných je výrazně omezen – což činí jeho hledání globálního minima obzvláště obtížným. Optimalizační algoritmus musí v tomto případě nejen najít minimum funkce, ale zároveň zůstat v rámci platného prostoru definovaného těmito omezeními.

Funk

Jak optimalizovat složité problémy pomocí algoritmu SOCE: Porovnání s jinými metodami

Metody globální optimalizace jsou zásadní při hledání optimálních řešení v případech, kdy objektivní funkce je

Jak efektivně vyhledávat globální a lokální optima v rozsáhlém návrhovém prostoru?

Jedním z klíčových aspektů optimalizačních algoritmů je rovnováha mezi globálním průzkumem a lokálním vyhledáváním. V navrhovaném přístupu MGOSIC (Multi-Goal Optimization using Surrogate and Infill Criteria) se tato rovnováha dosahuje kombinací strategie hustého lokálního vyplňování a selektivního průzkumu neprobádaných oblastí návrhového prostoru.

Nicméně samotná infill kritéria, založená na predikcích metod jako Kriging, RBF nebo QRS, nejsou schopna zajistit rovnoměrné pokrytí globálního prostoru, zejména v řídkých oblastech. Proto MGOSIC implementuje doplňkovou strategii průzkumu neznámých oblastí pomocí odhadu střední kvadratické chyby (MSE) predikce modelu Kriging. Během optimalizace se sleduje průměrná změna nejlepších hodnot funkcí v několika po sobě jdoucích iteracích. Pokud tato změna klesne pod definovanou mez, algoritmus přechází do režimu globálního průzkumu a generuje nové vzorky pomocí stratifikovaného náhodného vzorkování (LHS), z nichž vybírá body s nejvyšší predikovanou chybou. Tyto body jsou následně použity k rozšíření znalostí o prostoru a předejití uvíznutí v lokálním minimu.

Výkonnost MGOSIC byla dále ověřena na sadách testovacích úloh zahrnujících jak nízkodimenzionální (2–5 rozměrů), tak vysokodimenzionální problémy (6–20 rozměrů), zahrnující multimodální, konvexní i rozsáhlé optimalizační úlohy. Srovnání s tradičními algoritmy jako EGO, CAND či DE ukazuje výraznou nadřazenost MGOSIC z hlediska počtu nutných evaluací funkcí (NFE) i počtu iterací (NIT). Například v případech s četnými lokálními minimy, jako jsou funkce Ackley nebo RS, dosahuje MGOSIC cílových hodnot mnohem efektivněji než ostatní metody, které často selhávají nebo vyžadují řádově více výpočetních cyklů.

MGOSIC také překonává algoritmy, které používají vícebodová infill kritéria – například SOCE nebo MSEGO. Zatímco MSEGO ve své podstatě rozšiřuje EGO o možnost vzorkovat více bodů v každém cyklu, a SOCE využívá shlukovací přístup, MGOSIC vyniká adaptivním

Jak optimalizovat nákladné výpočty: Metody využívající surrogate modely a vícezačínkový výzkum

V současném světě optimalizace se stále častěji používají surrogate modely, které slouží k aproximaci složitých a nákladných funkčních výpočtů. Tento přístup nejenže významně snižuje nároky na čas a výpočetní výkon, ale zároveň umožňuje efektivní nalezení optimálních řešení i v případech, kdy jsou simulace příliš nákladné nebo časově náročné. Existují různé strategie pro implementaci surrogate modelů v optimalizačních procesech, přičemž dvě hlavní kategorie zahrnují offline a online přístupy.

Na druhé straně online optimalizace začíná s hrubým surrogate modelem, který se postupně vylepšuje přidáváním nových vzorků během každé iterace. Tento přístup je mnohem flexibilnější a adaptivní, protože se model neustále přizpůsobuje novým informacím získaným během výpočtu. Klíčem k úspěšné online optimalizaci je efektivní strategie doplňování vzorků, která balancuje mezi zkoumáním neznámých oblastí prostoru a využíváním aktuálního modelu pro prozkoumání těchto oblastí.

Výzvou je ale najít optimální rovnováhu mezi explorací a exploitací, která umožňuje modelu postupně zlepšovat svou přesnost, aniž by došlo k příliš velkému přežití pouze na základě již známých informací. U problémů s vysokou dimenzionalitou (D ≥ 10) se ukazuje, že tyto strategie často čelí výzvám, protože explorační schopnosti metody jsou omezeny a přesnost modelu v těchto podmínkách není dostatečná.

Pokud jde o vysokodimenzionální a nákladné optimalizační úkoly, často se používají metody, které umožňují vícenásobné zahájení průzkumu. Tento přístup, známý jako Multi-Start Exploration (MDEME), se zaměřuje na prozkoumání široké oblasti prostoru hledání pomocí několika různých startovních bodů. MDEME, jak název napovídá, spočívá v tom, že optimalizační proces začíná z různých míst, čímž se zvyšuje pravděpodobnost, že nalezené řešení bude globálně optimální, nikoliv pouze lokální. Tento přístup může být velmi efektivní v problémech, kde se nachází mnoho lokálních minim, což je častý problém u multimodálních funkcí.

Kromě těchto metod existuje ještě řada dalších přístupů, jako jsou adaptivní metody, které vylepšují výběr vzorků v závislosti na dosažených výsledcích. Příkladem může být použití různých algoritmů pro detekci komunit v komplexních sítích, které umožňují zlepšit vyhledávání optimálních řešení v nejednoznačných nebo neúplných datech. Při použití těchto algoritmů je nutné být obezřetný, aby se zabránilo přílišné specializaci modelu, což může vést k selhání při hledání nových, dosud neprozkoumaných řešení.

Významným pokrokem v této oblasti je použití hybridních modelů, které kombinují různé metodologie, jako je metamodeling a swarm intelligence, pro dosažení lepších výsledků v nákladných výpočtech. Tento přístup zahrnuje jak využívání prediktivních modelů, tak i schopnost adaptivně upravovat metody hledání v závislosti na nových informacích získaných během simulace.

Jak funguje surrogate-assisted Gray Wolf Optimization a proč je důležitá?

Algoritmus Gray Wolf Optimization (GWO) je populární metoda založená na sociálním chování vlků při lovu, která využívá tři klíčové vůdce smečky – alfa, beta a delta. Každý vlk v populaci aktualizuje svou pozici na základě těchto vůdců pomocí vzorců, které zahrnují náhodné faktory a vzdálenosti mezi aktuální pozicí vlka a pozicemi vůdců. Tímto způsobem je simulováno koordinované hledání optimálního řešení v daném prostoru.

Surrogate-assisted GWO (SAGWO) představuje pokročilou variantu, která využívá náhrady (surrogátní modely) k efektivnějšímu řešení složitých a výpočetně náročných optimalizačních úloh, zejména těch s vysokou dimenzionalitou. Jako surrogate model je zde použit radiálně bazovaný funkční model (RBF), který je schopný rychle vytvářet přesné aproximace cílové funkce na základě omezeného počtu vzorků. Tento model pomáhá algoritmu GWO zefektivnit průzkum prostoru tím, že předpovídá slibná místa, kde se nachází potenciálně lepší řešení.

V rámci SAGWO se inicializuje databáze vzorků pomocí Latin Hypercube Sampling (LHS), což zajišťuje rovnoměrné pokrytí prostoru návrhů. Nejlepší vzorky jsou vybrány jako počáteční pozice vlků. Následně se trénuje RBF model na těchto datech, což umožní předpovědět nejlepší možná řešení, která se přidávají do databáze. Na základě těchto informací jsou aktualizováni vůdci smečky alfa, beta a delta nejen podle dosavadních pozic vlků, ale i podle předpovědí modelu.

Tento přístup lze chápat jako přidání „zkušeného vlka“ do smečky, který díky znalostem získaným z RBF modelu dokáže lépe vést ostatní. Zkušenosti vlků i predikce RBF se vzájemně doplňují a společně vedou k efektivnějšímu hledání. Aktualizace pozic jednotlivých vlků tak není pouze reakcí na aktuální situaci, ale zahrnuje i informace o potenciálních úspěšných oblastech, které model RBF odhalil.

Důležitým aspektem SAGWO je také tzv. „knowledge mining“ neboli získávání znalostí z surrogate modelu, které se zaměřuje na lokální region kolem nejlepšího aktuálního řešení. Tento přístup odráží skutečnost, že globální modely surrogate nemusí být vždy přesné, ale v blízkosti optimálních řešení dokážou být velmi užitečné. Pro získání lepších lokálních predikcí se používá kombinace globální a lokální optimalizace, včetně multi-start lokálních vyhledávání, čímž se efektivněji zmapují perspektivní oblasti prostoru.

Celý postup tak vytváří synergii mezi behaviorální optimalizací založenou na přírodních vzorcích a statistickou predikcí, což umožňuje zvládat složité optimalizační úlohy, které by jinak byly příliš náročné na výpočetní zdroje.

K pochopení těchto principů je důležité uvědomit si, že surrogate-assisted metody nejsou pouhým nahrazením skutečných výpočtů, ale inteligentním doplňkem, který usnadňuje průzkum prostoru návrhů. Efektivita této metody spočívá v pečlivé integraci vzorkovacích strategií, adaptivní aktualizaci modelů a sofistikovaném výběru vůdců smečky, což dohromady vytváří robustní rámec pro globální optimalizaci.