Mnohokriterální optimalizace

Vícekriterální optimalizace (také vícekriterální programování, angl. multi-objective optimization, multi-criteria optimization) — je oblast matematické optimalizace zabývající se úlohami simultánní optimalizace podle dvou nebo více účelových funkcí (kritérií), která si zpravidla navzájem odporují. Formálně je úloha zapsána jako minimalizace vektorové účelové funkce na množině přípustných řešení.

Definice a terminologie

Úloha vícekriterální optimalizace je v obecném tvaru zapsána následovně: $\underset{x\in S}{min}\{f_1(x),f_2(x),\dots ,f_k(x)\}$ kde $S\subseteq {ℝ}^n$ — neprázdná množina přípustných řešení a $f_i:S\to ℝ$ — účelové funkce ($k\ge 2$). Vektor $f(x)=(f_1(x),\dots ,f_k(x))$ se nazývá cílovým vektorem.

Na rozdíl od skalární optimalizace ve vícekriterální formulaci zpravidla neexistuje jediné řešení, které by současně zlepšovalo hodnoty všech kritérií. Proto se klasický pojem optima zobecňuje pomocí konceptu Paretovy optimality.

• Paretovo řešení (Pareto-optimální neboli efektivní řešení): přípustné řešení $x^{\ast }\in S$, pro které neexistuje jiné řešení $x\in S$ takové, že $f_i(x)\le f_i(x^{\ast })$ pro všechna $i=1,\dots ,k$, přičemž $f_j(x)<f_j(x^{\ast })$ alespoň pro jeden index $j$. Jinými slovy, řešení je Pareto-optimální, pokud nelze zlepšit žádné kritérium bez zhoršení alespoň jednoho jiného kritéria.
• Paretova fronta (nebo Paretova množina): množina všech cílových vektorů odpovídajících Pareto-optimálním řešením.
• Slabě Pareto-optimální řešení: řešení $x^{\ast }\in S$, pro které neexistuje jiné řešení $x\in S$ takové, že $f_i(x)<f_i(x^{\ast })$ pro všechna $i$.

Klíčové vlastnosti a věty

• Věta o vážené sumě: Ve výpuklých úlohách (kde jsou všechny funkce $f_i(x)$ a množina $S$ výpuklé) je každé Pareto-optimální řešení $x^{\ast }$ řešením skalární úlohy minimalizace vážené sumy kritérií $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ pro nějakou sadu nezáporných vah $w_i\ge 0$. V nevýpuklých úlohách však tato metoda nemusí nalézt některé části Paretovy fronty.

• Podmínky optimality Karusche-Kuhna-Tuckera (KKT): Nutné podmínky optimality pro hladké úlohy se zobecňují na vícekriterální případ. V bodě Pareto-optima existuje nenulová sada nezáporných multiplikátorů (vah), pro které jsou gradienty účelových funkcí a aktivních omezení lineárně závislé.

• Vlastnosti množiny řešení: Paretova fronta má řadu důležitých kvalitativních charakteristik. Její hranice je vymezena ideálním bodem (složeným z prvkových minim všech kritérií) a nadirových bodem (z prvkových maxim na frontě).

Příklady

• Lineární úloha: Minimalizovat $f_1(x)=-x_1$ a $f_2(x)=-x_2$ při omezení $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Zde zlepšení jednoho kritéria (například zvýšení $x_1$) nevyhnutelně vede ke zhoršení druhého (snížení $x_2$). Množina Pareto-optimálních řešení tvoří úsečku přímky $x_1+x_2=1$.
• Nevýpuklá úloha: Minimalizovat $f_1(x)=x^2$ a $f_2(x)=(x-2{)}^2$ na úsečce $[0,2]$. Paretova fronta je nevýpuklá. Metoda vážených sum s kladnými vahami nebude schopna nalézt řešení uvnitř této úsečky (například v bodě $x=1$), protože lineární kombinace kritérií dosahuje minima pouze v krajních bodech $x=0$ nebo $x=2$.

Související pojmy a aplikace

Vícekriterální optimalizace úzce souvisí s vícekriterálním rozhodováním (MCDM), které se zabývá výběrem nejlepší alternativy s ohledem na preference osoby přijímající rozhodnutí. Hlavní metody převodu vícekriterální úlohy na skalární (skalarizace) zahrnují:

• Metoda vážené sumy.
• Metoda $\epsilon$-omezení: Optimalizuje se jedno kritérium a ostatní jsou převedena na omezení tvaru $f_i(x)\le {\epsilon }_i$. Tato metoda je schopna nacházet řešení na nevýpuklých částech fronty.

Vícekriterální optimalizace nachází široké uplatnění v technickém projektování, ekonomice (například optimalizace portfolia), řízení a ekologii.

Viz také

• Paretova optimalita
• Vektorová optimalizace
• Teorie rozhodování
• Systémy podpory rozhodování
• Operační výzkum