18. tétel - NSGA variánsok

Ismertesse a többcélú optimalizálás célját és alapfogalmait! Mutassa be az NSGA algoritmus működését! Ismertesse, hogy miben különbözik ettől az NSGAII!

Többcélú optimalizálás célja és alapfogalmai

Lásd a Többcélú optimalizálás tételben.

NSGA I.

A genetikus és raj alapú algoritmusok jól működnek, de egycélú optimalizálásra vannak, erre kínál megoldást az NSGA (Non-Dominated Sorting Genetic Algorithm).

  • A Pareto dominancián alapul
  • Nem csak egy megoldást, hanem a Pareto frontot adja vissza (optimális megoldások halmaza)
  • Arra is törekszik, hogy a visszatérési érték minél jobban lefedje a megoldáshalmazt

Alapelve megegyezik az evolúciós algoritmusoknál tanulttal, csak a szelekcióban különbözik.

A szelekció során a dominancia alapján rakja sorba az elemeket.

  • Mindenkinek a jóságát az határozza meg, hogy hányan dominálják
    • akiket senki se (első pareto front), azok kerülnek először feldolgozásra
      • majd a második pareto front, és így tovább
    • az első körben feldolgozott elemek mindig nagyobb fitnesz értéket kapnak, mint a következő frontokban lévők

Egy megosztó függvénnyel próbálja diverzifikálni az eredményeket: előnyben részesíti a frontok azon elemeit, amik kisebb sűrűségű helyen vannak, és hátrányba szorítja a sűrű helyen lévőket.

Megvalósítás

NSGA szelekció

Itt kivételesen a nagyobb fitneszt tekintjük jobbnak.

A megadott algoritmus csak a szelekcióért felelős, tehát bemenetként kapja a \(P\) populációt, a kimenete pedig \(M\) halmazba kerül.

A fő ciklus addig fut, amíg a populáció elemei el nem fogynak. Ebben 3 belső ciklus van:

  1. Az első ciklus \(F\) halmazba válogatja \(P\) azon elemeit, akiket nem dominál senki.

    • Első esetben ez az első pareto front lesz, utána a második, stb.
    • A kiválogatás után ezeket az elemek töröljük a \(P\)-ből.

  2. A következő ciklus végzi el a megosztó függvény hívásokat

    • Az \(F\) halmaz összes eleménél kiszámolja a többi \(F\) elemhez tartozó távolság összegét
      • Ezt helyezi el a \(p_{sh}\) tulajdonságba, majd kiszámolja ezek összegét (\(S_{sh}\))

  3. A következő ciklus elkezdi kiosztani a fitnesz értékeket az egyes elemeknek

    • A fitnesz mindig fitnessbase-ből indul ki
      • Ennek a szerepe, hogy az egymást követő frontok egyre rosszabb fitnesz értéket kapjanak
    • Ezt módosítjuk a kiszámított sharing értékek alapján
    • Minél nagyobb a sharing értéke (tehát minél messzebb van a többiektől), annál nagyobb fitnesz értéket fog kapni

A fő ciklusmag végén

  • A feldolgozott elemeket hozzáadjuk az \(M\) halmazhoz,
  • A a fitnessbase értéket lecsökkentjük az aktuális front legkisebb fitneszénél egy kicsivel rosszabb értékre
  • Hogy mennyivel rosszabbra, azt a fitnessdeg-gel szabályozzuk, ez legen egynél valamivel kisebb

Megosztó függvény

  • Szerepe, hogy a távolságok alapján kiszámoljon egy "sűrűség" értéket.
  • Függvény, ami számhoz számot rendel

Egy lehetséges megoldás:

  • meghatározunk egy \(\sigma_{share}\) távolságértéket.
    • Az ennel messzebb lévő elemekkel nem foglalkozunk (a sűrűség 0)
    • a távolságon belüli elemekhez egy lineáris átmenetet adunk meg
      • minden elem önmagától vett távolsága 1 legyen
      • a \(\sigma_{share}\) távolságra lévő elemhez pedig 0 rendelődjön

Értékelés

Előnyök:

  • jó többcélú optimalizálásra
  • pareto dominancián alapul
  • a pareto frontot adja vissza
  • azon belül is a távoli pontokat

Hátrányok:

  • érzékeny a szigma értékre
  • nincs benne elitizmus
  • nagy számításigény

Miben különbözik az NSGA II.?

A feljebb leírt hátrányokra kínál megoldást.

Fast Nondominated Searching Approach

Az NSGA I.-ben az egyes frontok előállításakor minden elemet mindennel össze kell hasonlítani mindennel.

  • ennek a lépésszáma \(M \cdot N^3\)
  • az NSGA II. ezzel szemben ezt \(M \cdot N^2\) lépésben megoldja

ahol \(N\) a populáció mérete, \(M\) a célfüggvények száma, és legrosszabb esetben minden frontban 1 elem van

Hogyan?

Az első ciklus összehasonít minden elemet (\(p\)) minden másikkal (\(q\)), és kiszámolja az alábbbi értékeket:

  1. np érték: megadja, hogy hány elem dominálja \(p\) megoldást
  2. \(S_p\) halmaz: megadja azokat az elemeket, amiket a \(p\) dominál

Eközben a Pareto frontot (akiket senki sem dominál) kigyűjti \(F\) halmazba.

Ezt követően el lehetkezdeni megadni az egymást követő Pareto-frontok elemeit. Ehhez végigmegy \(F\)-en, ami az éppen aktuális front elemeit tartalmazza.

  1. Ezeknél eltároljuk a prank-ba, hogy hányadik frontban vannak
  2. Végignézzük az elemeknek az \(S_p\) halmazát, és az összes ott lévő \(q\) elem np értékét csökkentjük 1-gyel
  3. Ha valakinek az np értéke 0-ra vált, az azt jelenti, hogy ő a következő Pareto frontban lesz → betesszük \(F'\)-be
  4. Ezeket ismételjük az újabb és újabb frontra

Sűrűség becslés

Az NSGA II. megpróbálja megbecsülni az egyes elemek környezetének sűrűségét.

  1. Az első célfüggvény alapján sorbarakja az aktuális Pareto front elemeit
  2. Minden elemhez kiszámol egy idistance távolságot ami
    • a két szélső elemnél \(∞\),
    • a többieknél a kétoldali közvetlen szomszédok távolságából számolható ki
    • ezeket az értékeket összegzi az összes célfüggvény esetén, és ezek összege ad egy sűrűségi becslést(pdist)
  3. Minél kisebb pdist, annál nagyobb a sűrűség.

Szelekció

  • Minden elemnek megvan a Pareto rangja és a crowding distance értéke
  • Egy \(p\) elem akkor dominálja \(q\) elemet, ha
    • \(p\) rangja (prank) kisebb, mint \(q\) rangja (korábbi frontban volt)
      • vagy ha ez egyenlő, akkor \(p\) sűrűsége kisebb
  • A szelekciónál ha nem fér minden elem a frontból a populációba, akkor a sűrűség dönt közöttük

TODO: ez a tétel még nincs teljesen kész, az NSGAII-ről még lehet kéne több minden