Optymalizacja wielokryterialna

Optymalizacja wielokryterialna (także programowanie wielokryterialne, ang. multi-objective optimization, multi-criteria optimization) — to dział optymalizacji matematycznej zajmujący się zagadnieniami jednoczesnej optymalizacji według dwóch lub więcej funkcji celu (kryteriów), które z reguły są ze sobą sprzeczne. Formalnie zadanie zapisywane jest jako minimalizacja wektorowej funkcji celu na zbiorze rozwiązań dopuszczalnych.

Definicja i terminologia

Zadanie optymalizacji wielokryterialnej w ogólnej postaci zapisuje się następująco: $\underset{x\in S}{min}\{f_1(x),f_2(x),\dots ,f_k(x)\}$ gdzie $S\subseteq {ℝ}^n$ — niepusty zbiór rozwiązań dopuszczalnych, a $f_i:S\to ℝ$ — funkcje celu ($k\ge 2$). Wektor $f(x)=(f_1(x),\dots ,f_k(x))$ nazywany jest wektorem celu.

W odróżnieniu od optymalizacji skalarnej, w sformułowaniu wielokryterialnym zazwyczaj nie istnieje jedyne rozwiązanie poprawiające wartości wszystkich kryteriów jednocześnie. Dlatego klasyczne pojęcie optimum uogólnia się przy użyciu koncepcji optymalności w sensie Pareto.

• Rozwiązanie Pareto (rozwiązanie Pareto-optymalne lub efektywne): rozwiązanie dopuszczalne $x^{\ast }\in S$, dla którego nie istnieje inne rozwiązanie $x\in S$ takie, że $f_i(x)\le f_i(x^{\ast })$ dla wszystkich $i=1,\dots ,k$, przy czym $f_j(x)<f_j(x^{\ast })$ dla przynajmniej jednego indeksu $j$. Innymi słowy, rozwiązanie jest Pareto-optymalne, jeśli żadnego kryterium nie można poprawić bez pogorszenia co najmniej jednego innego kryterium.
• Front Pareto (lub zbiór Pareto): zbiór wszystkich wektorów celu odpowiadających rozwiązaniom Pareto-optymalnym.
• Słabo Pareto-optymalne rozwiązanie: rozwiązanie $x^{\ast }\in S$, dla którego nie istnieje inne rozwiązanie $x\in S$ takie, że $f_i(x)<f_i(x^{\ast })$ dla wszystkich $i$.

Kluczowe właściwości i twierdzenia

• Twierdzenie o ważonej sumie: W zadaniach wypukłych (gdzie wszystkie funkcje $f_i(x)$ oraz zbiór $S$ są wypukłe) każde rozwiązanie Pareto-optymalne $x^{\ast }$ jest rozwiązaniem skalarnego zadania minimalizacji ważonej sumy kryteriów $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ dla pewnego zestawu nieujemnych wag $w_i\ge 0$. Jednak w zadaniach niewypukłych metoda ta może nie znaleźć niektórych części frontu Pareto.

• Warunki optymalności Karusha-Kuhna-Tuckera (KKT): Warunki konieczne optymalności dla gładkich zadań uogólnia się na przypadek wielokryterialny. W punkcie Pareto-optimum istnieje niezerowy zestaw nieujemnych mnożników (wag), dla których gradienty funkcji celu i aktywnych ograniczeń są liniowo zależne.

• Właściwości zbioru rozwiązań: Front Pareto posiada szereg ważnych cech jakościowych. Jego granica wyznaczona jest przez punkt idealny (złożony z elementarnych minimów wszystkich kryteriów) oraz punkt nadir (z elementarnych maksimów na froncie).

Przykłady

• Zadanie liniowe: Minimalizować $f_1(x)=-x_1$ i $f_2(x)=-x_2$ przy ograniczeniu $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Tutaj poprawa jednego kryterium (np. zwiększenie $x_1$) nieuchronnie prowadzi do pogorszenia drugiego (zmniejszenia $x_2$). Zbiór rozwiązań Pareto-optymalnych stanowi odcinek prostej $x_1+x_2=1$.
• Zadanie niewypukłe: Minimalizować $f_1(x)=x^2$ i $f_2(x)=(x-2{)}^2$ na odcinku $[0,2]$. Front Pareto jest niewypukły. Metoda ważonych sum z dodatnimi wagami nie będzie w stanie znaleźć rozwiązań wewnątrz tego odcinka (np. w punkcie $x=1$), ponieważ liniowa kombinacja kryteriów będzie osiągać minimum jedynie w punktach skrajnych $x=0$ lub $x=2$.

Pojęcia pokrewne i zastosowania

Optymalizacja wielokryterialna jest ściśle powiązana z wielokryterialnym podejmowaniem decyzji (MCDM), które zajmuje się wyborem najlepszej alternatywy z uwzględnieniem preferencji osoby podejmującej decyzję. Podstawowe metody przekształcania zadania wielokryterialnego w skalarne (skalaryzacji) obejmują:

• Metodę ważonych sum.
• Metodę ograniczeń $\epsilon$: Optymalizowane jest jedno kryterium, a pozostałe przekształcane są w ograniczenia postaci $f_i(x)\le {\epsilon }_i$. Metoda ta jest w stanie znajdować rozwiązania na niewypukłych odcinkach frontu.

Optymalizacja wielokryterialna znajduje szerokie zastosowanie w projektowaniu inżynierskim, ekonomii (np. optymalizacja portfela), zarządzaniu i ekologii.

Zobacz też

• Optymalność w sensie Pareto
• Optymalizacja wektorowa
• Teoria podejmowania decyzji
• Systemy wspomagania decyzji
• Badania operacyjne