12. tétel - Többcélú optimalizálás

Mit értünk többcélú optimalizálás alatt? Mik ezeknek a feladatoknak a jellegzetességei és nehézségei? Milyen módon lehet visszavezeti ezeket a feladatokat egycélú optimalizálásra? Ismertesse a Pareto dominanciával kapcsolatos fogalmakat (dominancia, Pareto optimum, Pareto front)! Mutasson gyakorlati példát ezekre!

A valóságban sok olyan optimalizálási probléma létezik, ahol nem tudunk egyetlen egyértelmű célfüggvényt definiálni.

Például:

  • befektetést kell ajánlani, minél nagyobb hozammal, de minél kisebb kockázattal
  • munkát szeretnénk elvégeztetni, minél jobb minőségben és minél olcsóbban

Ilyenkor több célfüggvény van, és \(G\) a célfüggvények halmaza.

Egy célfüggvényt felírhatunk, mint

\[g_i: ℙ → ℝ, i \in \lbrace 1,2,...|G| \rbrace\]

Visszavezetés egycélú optimalizálásra

A legtöbb általunk használt algoritmus egycélú optimalizálásra van, többcélúra közvetlenül nem használható, de ezeket különböző módszerekkel egycélú optimalizálásra vezethetjük vissza.

flowchart TB
V[Visszavezetés egycélú optimalizálásra] --> O & MD & MM & H
O[Összegzés] --> S[Súlyozás]
MD[Method of Distance]
MM[Min-Max]
H[Hierarchikus módszer]

Összegzés, súlyozás

  • Legegyszerűbb, ha a fitneszfüggvényt úgy valósítjuk meg, hogy a célfüggvényeket összeadjuk
  • Ennél nem sokkal bonyolultabb, ha az öszegzés során súlyvektorral súlyozzuk a célfüggvényeket.
  • Előny:
    • egyszerűség: a kapott fitnesz függvényt simán felhasználhatjuk a tanult algoritmusokban
    • a súlyokkal beállítható a célfüggvények fontossága
  • Hátrány:
    • nehéz lehet meghatározni a súlyokat
    • bizonyos esetek nem írhatóak le súlyozással
      • pl. befektetésnél van akkora kockázat, ami bármekkora is lehet a hozam, nem éri meg

Method of Distance

  • Meghatározzuk célértékek egy vektorát (ideális pont)
    • lehet akár mindegyik koordináta 0
  • Egy elem jósága a hozzá tartozó célfüggvények értékei által megjelölt pont távolsága ettől az ideális ponttól
  • Pl. van egy adott hely, ahova szeretnénk egy bútort venni
    • Az ideális bútor 100 cm magas, 50cm széles és 40 cm mély
    • Ekkor a célfüggvények: magasság(), szélesség(), mélység()
    • Ekkor a célvektor: [100, 50, 40]

Képlet:

\[ (\sum_{i=1}^{|G|} |g_i(gpm(x))- \hat{v}_i|^r)^{\frac{1}{r}} \]

\(r\) segítségével lehet beállítani a távolságszámítás módszerét, pl. \(r=2\) esetén a távolság Euklideszi lesz.

Min-max

  • Figyelembe tudja venni az egyes célfüggvények értékkészlete közötti különbségeket
    • pl a kockázat 0 és 1 közötti számként, a hozam meg 0 és 1 000 000 000 számként van megadva
  • Szintén definiálunk egy vektort (ideális pont)
  • Az egyes célfüggvényeket normalizáljuk:

\[ Z_i(x) = \frac{|g_i(gpm(x))-\hat{v}_i|}{\hat{v}_i} \]

Ezek a \(Z\) értékek tehát az egyes célokra vonatkoznak, még valamilyen formában összegeznünk kell őket a fitnesz függvény megadásához.

  • lehet sima összegzés
  • választhatjuk a legrosszabb eredményt

Hierarchikus módszer

  • A célfüggvényeket sorrendbe rakjuk fontosság szerint.
  • Két elem összehasonlításánál először kiértékeljük az elsőt, ha azonos az eredmény akkor a másodikat, és így tovább
  • Például egy versenyen ha két ember azonos pontot ér el, a nevük ABC sorrendje dönt
  • Hátrány:
    • későbbre priorizált célfüggvény csak a saját szintjén tudja befolyásolni a sorrendet
    • nem ad egyértelmű értéket a fitnesznek, csak két elem összehasonlításakor tudja megmondani, hogy melyik a jobb

Pareto dominancia

Egy \(x\) megoldás Pareto dominál egy \(y\) megoldást, ha

\[\forall i \in \lbrace 1,2,...,|G|\rbrace: g_i(x) \leq g_i(y)\]

\[\exists j \in \lbrace 1,2,...,|G|\rbrace: g_j(x) < g_j(y)\]

Tehát

  1. \(x\) minden szempontból legalább olyan jó, mint \(y\)
  2. és legalább egy szempontból még jobb is nála

Jelölése: \[x \prec y\]

Pareto optimum

Egy megoldásjelölt Pareto optimum, ha nincs olyan megoldásjelölt, ami dominálná őt.

  • Pl. ha a állásajánlatoknál a fizetést és a home office napok számát vesszük, akkor ha van egy olyan ajánlat, amelyik a legtöbbet fizeti és full remote, az pareto optimum lesz

Pareto front

A Pareto optimális elemek halmaza (ha több van).

Pareto front

[Kép forrása]

Több front is lehet.

  • A második pareto frontba azok az elemek tartoznak, amiket csak az első pareto front elemei dominálnak.
  • A harmadikba azok, amiket az első két pareto front elemei dominálnak
  • és így tovább.