[CZ] Vícekriteriální optimalizace

Doposud jsme se bavili jen o jednokriteriální optimalizaci (měli jsme jednu fitness funkci), ale evoluční algoritmy se velmi často a velmi úspěšně používají i pro vícekriteriální optimalizaci, tj. optimalizaci více funkcí zároveň. Představte si třeba návrh tvaru křídla. Tam chceme, aby křídlo mělo co možná největší vztlak a zároveň kladlo co nejmenší odpor vzduchu. Ukazuje se, že evoluční algoritmy jsou velmi vhodné pro řešení vícekriteriálních problémů a patří mezi nejlepší vícekriteriální optimalizátory.

Vícekriteriální problém je tedy zadán jako množina několika funkcí z nějakého prohledávacího prostoru do reálných čísel. Vzhledem k tomu, že funkce si mohou navzájem odporovat, není většinou možné najít řešení, které by bylo optimální pro všechny zároveň. Cílem tedy je nalézt množinu Pareto optimálních řešení.

Abychom mohli definovat Pareto optimální řešení, musíme napřed nadefinovat dominanci dvou řešení. Řekneme, že řešení a dominuje řešení b (případně že řešení b je dominováno řešením a) jestliže a je ve všech kriteriích alespoň tak dobré jako b a alespoň v jednom kritériu lepší. Pareto optimální řešení jsou potom ta, která nejsou dominována žádným jiným možným řešením z prohledávaného prostoru. Množina Pareto-optimálních řešení je často nekonečná a není tedy možné najít úplně všechna řešení, hledá se tedy nějaká její konečná aproximace. Je zajímavé, že v případě vícekriteriální optimalizace není jeden nejlepší jedinec v populaci, používá se celá populace a považuje se za aktuální aproximaci Pareto optimální množiny řešení. Obraz této Pareto-optimální množiny do prostoru funkčních hodnot se nazývá Pareto-optimální fronta.

Porovnání kvality řešení

S více kritérii přichází i nové výzvy při návrhu evolučních algoritmů. Jedním z problémů je, jak vůbec zjistit, které algoritmy fungují lépe a které hůře. K tomu je potřeba porovnat výsledné aproximace Pareto optimální množiny. Zpočátku se podobné porovnání dělalo především vizuálně – namalovaly se obě srovnávané množiny a diskutovalo se, proč je jedna lepší než druhá. Hlavní nevýhodnou tohoto postupu je, že není moc objektivní a špatně se vyhodnocuje, pokud jsou obě množiny podobné. Postupně začaly vznikat různé indikátory, které vyjadřovaly kvality množin řešení lépe. Mezi ty jednodušší patří třeba to, kolik procent jedné množiny je dominováno množinou druhou. Dnes se ale nejčastěji používají dva indikátory – inverzní generační vzdálenost (Inverse Generational Distance, IGD) a hyperobjem (hypervolume, HV).

Indikátor IGD měří průměrnou vzdálenost od řešení na Pareto optimální frontě k nejbližšímu řešení ve výsledné množině. Díky tomu indikátor vyjadřuje jak blízkost řešení k Pareto-optimální frontě (convergence), tak to, jestli jsou řešení po frontě rozmístěna rovnoměrně (spread). Menší hodnoty tohoto indikátoru jsou lepší. Občas se používá i generační vzdálenost (GD), ta počítá, jak daleko je od řešení v množině k nejbližšímu Pareto optimálnímu řešení. Ta ale vyjadřuje jen konvergenci, ale už ne rozmístění jedinců.

Hyperobjem vyjadřuje objem prostoru dominovaného danou množinou (a omezeného zvoleným referenčním bodem). V případě, že máme jen dvě funkce, které obě najednou minimalizujeme, tak se jedná o plochu “nad” body, které jsou obrazy jedinců v populaci. Plocha je shora omezena referenčním bodem (jinak by byla nekonečná). Tento indikátor opět spojuje jak konvergenci tak pokrytí Pareto-optimální fronty. Větší hodnoty tohoto indikátoru jsou lepší. Někdy se také jako indikátor používá rozdíl hyperobjemu skutečné Pareto optimální fronty a aproximace nalezené algoritmem. Potom jsou samozřejmě lepší menší hodnoty.

Vícekriteriální evoluční algoritmy

Nemožnost přímo porovnat dva jedince přináší další výzvu do evolučních algoritmů. Je potřeba zajistit konvergenci k Pareto optimální frontě a zároveň zajistit i dobré pokrytí této fronty. Podíváme se, jak funguje jeden z jednodušších algoritmů pro vícekriteriální optimalizaci: NSGA-II.

Hlavní rozdíl mezi jednokriteriálními a vícekriteriálními algoritmy je přirozeně v selekci (operátory mohou klidně zůstat stejné). V NSGA-II se před selekcí sloučí populace rodičů a potomků (tím se zajistí elitismus). Sloučená populace se potom rozdělí do nedominovaných front. V první nedominované frontě jsou jedinci, kteří nejsou dominováni žádným jiným jedincem v populaci. Ve druhé frontě, jsou jedinci, kteří nejsou dominování žádným jedincem v populaci po odebrání první fronty atd. Do další generace potom postupují jedincí, kteří jsou ve frontách s nižším číslem. Přirozeně nastane okamžik, kdy se nějaká fronta do nové populace nevejde celá. V tou chvíli přichází druhotné třídicí kritérium, na základě kterého se vybírají jedinci právě z této fronty. V původní NSGA-II se jako druhotné kritérium používá tzv. crowding distance. To je součet přes všechna kritéria, rozdílu nejbližšího horšího (v daném kritériu) a nejbližšího lepšího jedince. Větší hodnoty jsou lepší, neboť jedinci jsou potom v oblastech, kde nikdo jiný není a tedy prospívají pokrytí Pareto fronty. Používají se ale i jiná druhotná kritéria, například tzv. hypervolume contribution, tj. příspěvek daného jedince k hyperobjemu dané nedominované fronty. Počítá se jako rozdíl hyperbojemu fronty a hyperobjemu fronty bez daného jedince. Jedinci s vyšším příspěvkem jsou vybíráni přednostně.

Dnešní zdrojové kódy

V dnešních zdrojových kódech (package evolution.multi v Javě nebo soubor multi.py v Pythonu) máme jednoduchou implementaci NSGA-II (tato implementace funguje jen pro dvě kritéria). V Java knihovně bylo potřeba udělat několik změn:

• Přibyl MultiRealIndividual, tomu lze nastavit více hodnot účelových funkcí, má také číslo své nedominované fronty a druhotné třídicí kritérium (ssc).
• Hodnota fitness u jedinců se nepoužívá ani nijak nenastavuje.
• Hodnota objective value je u všech jedinců stejná a obsahuje hyperobjem aktuální populace.
• Používá se MergingReplacement, který sloučí populace rodičů a potomků než se spustí selekce. Nepoužívá se žádný další elitismus (ani nemá smysl).

Python implementace je podobná tomu, co známe z jiných cvičení, fitness jen vrací tuple místo jedné hodnoty. Implementaci najdete v souboru multi.py, pomocné funkce jsou v multi_utils.py a testovací optimalízační problémy jsou v moo_functions.py.

Máme naimplementovaných pět dvoukriteriálních problémů ze ZDT benchmarku (pojmenovaného podle jmen autorů). Nemáme problém ZDT5, protože ten má binární kódování, ostatní problémy mají kódování reálné. Všechny tyto problémy jsou relativně jednoduché, separabilní. První funkce je u všech kromě ZDT6 lineární. ZDT1 a ZDT2 se liší jen tvarem Pareto-optimální fronty. ZDT3 má Pareto-optimální frontu nespojitou (ale Pareto-optimální množina spojitá je). ZDT4 má spoustu lokálních Pareto optimálních front a ZDT6 má obě funkce multi-modální. U všech problémů se obě funkce minimalizují a optimum leží na hranici prohledávaného prostou (kvůli tomu si tato sada funkcí vysloužila hodně kritiky a od jejího používání se pomalu ustupuje).