NSGA algoritmus

Üdvözlöm, Ön a NSGA algoritmus szó jelentését keresi. A DICTIOUS-ban nem csak a NSGA algoritmus szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a NSGA algoritmus szót egyes és többes számban mondani. Minden, amit a NSGA algoritmus szóról tudni kell, itt található. A NSGA algoritmus szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. ANSGA algoritmus és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Magyar

Kiejtés

  • IPA:

Főnév

NSGA algoritmus

  1. (matematika, algoritmusok) Az NSGA (Non-dominated Sorting Genetic Algorithm) egy többcélú optimalizálási algoritmus, amelyet Kalyanmoy Deb és társai fejlesztettek ki. Az algoritmus célja, hogy egy Pareto-hatékony megoldáshalmazt generáljon, amely a különböző célfüggvények közötti kompromisszumokat ábrázolja.

A későbbi, továbbfejlesztett változata, az NSGA-II, számos hiányosságot kiküszöbölt, például a számítási költségeket és az egyenletes Pareto-front lefedettségét.


Alapelvek

  1. Pareto-dominancia:
    • Egy megoldás akkor dominál egy másikat, ha minden célfüggvény szempontjából legalább olyan jó, és legalább egy szempontból szigorúan jobb.
  2. Pareto-front:
    • Az olyan megoldások halmaza, amelyek nem dominálhatók más megoldások által (nem javíthatók bármely célfüggvény szempontjából a többi megoldás rovására).
  3. Többcélú optimalizáció:
    • Az algoritmus nem egyetlen optimális megoldást keres, hanem egy kompromisszumos megoldáshalmazt, amely a különböző célfüggvények közötti kapcsolatot reprezentálja.


NSGA algoritmus működése

Az NSGA alapvetően egy genetikus algoritmus, amelyet a Pareto-dominancia fogalmával és a többcélú optimalizálás speciális szükségleteivel egészítettek ki.

Lépések

  1. Inicializáció:
    • Generálj egy kezdeti populációt véletlenszerűen.
  2. Fitnesz értékelés:
    • Értékeld ki a populáció minden egyedét az összes célfüggvény szempontjából.
  3. Dominált rendezés (Non-dominated Sorting):
    • Sorold be az egyedeket Pareto-frontok szerint:
      • Az első front (Pareto-front) megoldásai nem dominálnak másokat.
      • A második frontot az első front dominálja, de egymást nem.
      • És így tovább.
  4. Rangsorolás:
    • Minden egyedhez rendelj egy rangot annak alapján, hogy melyik fronton helyezkedik el.
  5. Keresztezés és mutáció:
    • A genetikus algoritmusokhoz hasonlóan hozz létre új egyedeket a keresztezés és mutáció segítségével.
  6. Szelekció:
    • A Pareto-frontok és más metrikák (pl. sokféleség) alapján válaszd ki a következő generációt.
  7. Iteráció:
    • Ismételd az értékelést, rendezést, és szelekciót, amíg el nem éred a megállási feltételt.


NSGA-II: Továbbfejlesztett változat

Az NSGA-II számos javítást hozott, amelyek az eredeti algoritmus problémáira reagáltak:

  1. Gyorsított dominált rendezés:
    • Hatékonyabb Pareto-rendezés, (O(MN^2))-es időkomplexitással ((M) célfüggvény, (N) populációméret).
  2. Tömörségi távolság (Crowding Distance):
    • Az egyedek közötti távolságot méri a célfüggvények értékei alapján, hogy elősegítse az egyenletes Pareto-front lefedettséget.
  3. Elitizmus:
    • A legjobb megoldások automatikus továbbvitele a következő generációba, hogy ne veszítsünk el jó megoldásokat.


Algoritmus Pszeudokódja

NSGA-II(Population, MaxGenerations):
    Initialize Population
    Evaluate Population
    for Generation in range(MaxGenerations):
        Fronts = NonDominatedSorting(Population)
        Assign CrowdingDistance(Fronts)
        MatingPool = SelectBasedOnRankAndCrowdingDistance(Population)
        Offspring = CrossoverAndMutation(MatingPool)
        Evaluate(Offspring)
        CombinedPopulation = Population + Offspring
        NextGeneration = SelectBestFromCombined(CombinedPopulation, PopulationSize)
        Population = NextGeneration
    return ParetoFronts(Population)

Python implementáció

A DEAP (Distributed Evolutionary Algorithms in Python) könyvtár tartalmaz egy NSGA-II implementációt.

Példa

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))
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()

Előnyök

  1. Pareto-front generálás:
    • Az NSGA és az NSGA-II hatékonyan generál Pareto-hatékony megoldásokat.
  2. Rugalmasság:
    • Alkalmazható különböző típusú többcélú optimalizálási problémákra.
  3. Elitizmus (NSGA-II):
    • Nem veszít el jó megoldásokat generációk között.
  4. Egyenletes lefedettség:
    • A Pareto-front egyenletes lefedését elősegíti.


Hátrányok

  1. Időbonyolultság:
    • Az NSGA (O(N^3)) időkomplexitása nagy populációméret esetén lassú lehet. Az NSGA-II ezt (O(N^2))-re csökkenti, de még mindig jelentős lehet.
  2. Paraméterérzékenység:
    • A megfelelő populációméret, keresztezési és mutációs paraméterek kritikusak a teljesítmény szempontjából.
  3. Függvényértékelés költsége:
    • A célfüggvények kiértékelése drága lehet bonyolult problémák esetén.


Alkalmazások

  1. Gépjárműtervezés:
    • Fogyasztás és teljesítmény optimalizálása.
  2. Hálózattervezés:
    • Költség és késleltetés kompromisszumai.
  3. Ellátási lánc menedzsment:
    • Költségek és szállítási idő optimalizálása.
  4. Bioinformatika:
    • Génhálózatok optimalizálása.


Összegzés

Az NSGA és az NSGA-II hatékony algoritmusok többcélú optimalizációs problémákra. Az NSGA-II a gyors Pareto-rendezésnek, elitizmusnak és tömörségi távolságnak köszönhetően jobb teljesítményt nyújt. Széles körben alkalmazzák különböző tudományos és mérnöki problémák megoldására, ahol több szempont közötti kompromisszum megtalálása szükséges.

További információk

Enciclo
Wikious
Sapientia
Scientia
Boobota
Anandapedia
Sagapedia
Wikithot