NSGA II

• IPA:

NSGA II

1. (matematika, algoritmusok)

Az NSGA-II egy továbbfejlesztett, hatékony többcélú optimalizációs algoritmus, amelyet Kalyanmoy Deb és társai fejlesztettek ki. Az NSGA-II célja, hogy többcélú optimalizációs problémákra generáljon Pareto-hatékony megoldáshalmazt, miközben javítja az eredeti NSGA algoritmus hiányosságait, például a számítási költséget és a megoldások egyenletes Pareto-front lefedettségét.

Az NSGA-II kulcsfontosságú jellemzői:

1. Dominált rendezés (Non-dominated Sorting):
   • Az egyedeket Pareto-frontok alapján rendezi:
     • Az első fronton azok a megoldások vannak, amelyeket más megoldás nem dominál.
     • A második frontot az első front dominálja, de egymást nem.
2. Elitizmus:
   • A legjobb megoldások automatikusan átkerülnek a következő generációba.
3. Tömörségi távolság (Crowding Distance):
   • Az egyedek közötti sokféleség biztosítása érdekében a Pareto-fronton belüli távolságot méri a célfüggvények alapján.
4. Gyorsított dominált rendezés:
   • Az NSGA-II gyorsabb Pareto-rendezést használ ((O(MN^2))), ahol (M) a célfüggvények száma, (N) a populációméret.

Az NSGA-II a genetikus algoritmusok alapelveit alkalmazza, de többcélú optimalizációra adaptálva.

1. Inicializáció:
   • Generálj egy kezdeti populációt ((P_0)).
   • Számítsd ki minden egyed célfüggvényértékeit.
2. Dominált rendezés:
   • Oszd fel a populációt Pareto-frontokba.
3. Szelekció és genetikai operátorok:
   • Válaszd ki a legjobb egyedeket a rangjuk (front) és a tömörségi távolságuk alapján.
   • Hozz létre új utódokat keresztezés és mutáció segítségével ((Q_t)).
4. Unió és új populáció létrehozása:
   • Kombináld az aktuális populációt (${\textstyle P_{t}}$) és az utódokat (${\textstyle Q_{t}}$) egy új unióba (${\textstyle R_{t}=P_{t}\cup Q_{t}}$).
   • Rendezés és szelekció után hozz létre egy új generációt (${\textstyle P_{t+1}}$).
5. Iteráció:
   • Ismételd, amíg el nem éred a megállási feltételt (pl. generációk száma vagy Pareto-front konvergencia).

NSGA-II(Population, MaxGenerations):
    Initialize Population P_0
    Evaluate Population P_0
    for t in range(MaxGenerations):
        Q_t = CrossoverAndMutation(P_t)
        Evaluate Q_t
        R_t = P_t + Q_t
        Fronts = NonDominatedSorting(R_t)
        P_{t+1} = SelectBest(Fronts, PopulationSize)
    return ParetoFronts(P_MaxGenerations)

1. Dominált rendezés:
   • Egy megoldás ((A)) akkor dominál egy másikat ((B)), ha:
     • (A) minden célfüggvény szempontjából legalább olyan jó, mint (B),
     • és van legalább egy célfüggvény, amelyben (A) szigorúan jobb.
2. Tömörségi távolság:
   • Az egyedek közötti sokféleséget méri, hogy az algoritmus egyenletesen fedje le a Pareto-frontot.
   • Az (i)-edik egyed tömörségi távolsága: $${\displaystyle d_{i}=\sum _{k=1}^{M}{\frac {f_{k}^{i+1}-f_{k}^{i-1}}{f_{k}^{\text{max}}-f_{k}^{\text{min}}}}}$$ ahol ${\textstyle f_{k}^{i+1}}$ és ${\textstyle f_{k}^{i-1}}$ az ${\textstyle i}$-edik egyed szomszédos célértékei.
3. Elitizmus:
   • Az NSGA-II biztosítja, hogy a Pareto-front legjobb megoldásai ne vesszenek el a következő generációk során.

Az NSGA-II implementálására a DEAP könyvtárat használjuk.

from deap import base, creator, tools, algorithms
import random

# Célfüggvények definiálása
def evaluate(individual):
    x, y = individual
    return x**2, (y - 2)**2

# Inicializáció
creator.create("FitnessMulti", base.Fitness, weights=(-1.0, -1.0))  # Minimizálás
creator.create("Individual", list, fitness=creator.FitnessMulti)
toolbox = base.Toolbox()

toolbox.register("attr_float", random.uniform, -10, 10)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, n=2)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Genetikai operátorok
toolbox.register("mate", tools.cxBlend, alpha=0.5)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2)
toolbox.register("select", tools.selNSGA2)
toolbox.register("evaluate", evaluate)

# NSGA-II futtatása
def main():
    population = toolbox.population(n=100)
    ngen = 50  # Generációk száma
    cxpb = 0.7  # Keresztezési valószínűség
    mutpb = 0.2  # Mutációs valószínűség

    algorithms.eaMuPlusLambda(population, toolbox, mu=100, lambda_=200, cxpb=cxpb,
                              mutpb=mutpb, ngen=ngen, stats=None, halloffame=None, verbose=True)

    return population

# Futtatás
pareto_front = main()

1. Pareto-front generálása:
   • Hatékonyan képes több célfüggvény kompromisszumait feltárni.
2. Elitizmus:
   • A legjobb megoldások biztosítása generációk között.
3. Egyenletes lefedettség:
   • A Pareto-front egyenletes reprezentációját biztosítja.
4. Gyors rendezés:
   • Az NSGA-II gyors Pareto-rendezési algoritmust alkalmaz.

1. Paraméterérzékenység:
   • A populációméret, keresztezési és mutációs arányok jelentősen befolyásolják az eredményt.
2. Skálázhatóság:
   • Nagy számú célfüggvény esetén (pl. több mint 3) az algoritmus teljesítménye romolhat.

1. Mérnöki tervezés:
   • Gépek, járművek és szerkezetek többcélú optimalizálása.
2. Hálózattervezés:
   • Adatátviteli útvonalak optimalizálása költség és késleltetés szempontjából.
3. Ellátási lánc menedzsment:
   • Költségek és szállítási idő kompromisszumai.
4. Bioinformatika:
   • Génhálózatok optimalizálása.

Az NSGA-II egy hatékony és széles körben használt többcélú optimalizációs algoritmus. Gyors Pareto-rendezése, elitizmusa és tömörségi távolsága miatt számos tudományos és mérnöki területen alkalmazzák. Az algoritmus a többcélú optimalizálási problémák megoldásának egyik legjobb eszköze, különösen két vagy három célfüggvény esetén.

• NSGA II - Értelmező szótár (MEK)
• NSGA II - Etimológiai szótár (UMIL)
• NSGA II - Szótár.net (hu-hu)
• NSGA II - DeepL (hu-de)
• NSGA II - Яндекс (hu-ru)
• NSGA II - Google (hu-en)
• NSGA II - Helyesírási szótár (MTA)
• NSGA II - Wikidata
• NSGA II - Wikipédia (magyar)