Zum Inhalt springen
Zurück zu den Suchergebnissen

NSGA-II — Non-dominated Sorting Genetic Algorithm II

Jahr
2002
Typ
Evolutionary multi-objective optimisation algorithm

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

NSGA-II (Non-dominated Sorting Genetic Algorithm II) ist der Standard-Referenzalgorithmus für die evolutionäre Mehrzieloptimierung, eingeführt von Deb, Pratap, Agarwal und Meyarivan im Jahr 2002.

Anstatt mehrere widersprüchliche Ziele in eine einzige Punktzahl zu überführen, entwickelt er eine Population von Kandidatenlösungen über Generationen hinweg und liefert eine Menge von Pareto-optimalen Kompromisslösungen – die Pareto-Front – mittels schneller nicht-dominierter Sortierung und einer Crowding-Distance-Metrik zur Erhaltung der Diversität.

Die Intuition hinter der Methode

Stellen Sie sich vor, Sie möchten ein Produkt entwerfen, das gleichzeitig so billig und so langlebig wie möglich ist. Billiger bedeutet normalerweise weniger langlebig, sodass es keine einzelne perfekte Antwort gibt – es gibt eine Familie sinnvoller Kompromisse. NSGA-II funktioniert wie eine Population konkurrierender Entwürfe: Jede Generation werden schwächere Entwürfe, die in jedem Ziel von anderen dominiert werden, eliminiert, und die Überlebenden werden so verteilt, dass sie die gesamte Bandbreite der Kompromisse abdecken, anstatt sich in einer Ecke zu ballen. Nach genügend Generationen bleibt Ihnen eine reichhaltige Auswahl an Optionen – die Pareto-Front –, aus der Sie die Balance wählen, die Ihren Prioritäten entspricht.

Geschichte

NSGA-II wurde 2002 von Kalyanmoy Deb und Kollegen am Indian Institute of Technology Kanpur als korrigierter und wesentlich verbesserter Nachfolger des ursprünglichen NSGA (Srinivas & Deb, 1994) veröffentlicht. Die wichtigsten Innovationen waren ein schnelles nicht-dominiertes Sortierverfahren mit einer Komplexität von O(MN²), ein expliziter Crowding-Distance-Operator zur Aufrechterhaltung der Lösungsdiversität ohne Sharing-Parameter und ein elitistischer Selektionsmechanismus. Die Arbeit aus dem Jahr 2002 in den IEEE Transactions on Evolutionary Computation ist zu einem der meistzitierten Werke im Bereich der evolutionären Berechnung geworden und hat NSGA-II zum De-facto-Benchmark für evolutionäre Mehrzielalgorithmen gemacht. Spätere Varianten – NSGA-III (2014) und andere – erweitern das Framework auf Probleme mit vielen Zielen.

Wann wird sie eingesetzt?

NSGA-II wird immer dann angewendet, wenn ein Problem zwei oder mehr widersprüchliche Zielfunktionen hat, die nicht ohne Informationsverlust in ein einziges Kriterium zusammengeführt werden können. Die Entscheidungsvariablen können kontinuierlich, binär oder kategorisch sein, und es ist keine Verteilungsannahme über die Zielfunktionslandschaft erforderlich. Der Algorithmus eignet sich für technische Konstruktion, Ressourcenallokation, Zeitplanung und Portfolio-Probleme, bei denen ein Spektrum von Kompromisslösungen nützlicher ist als ein einzelnes Optimum. Eine ausreichende Anzahl von Generationen (typischerweise mehrere hundert oder mehr) ist erforderlich, um eine gute Abdeckung der Front zu erreichen; zu wenige Generationen sind der Hauptfehlerfall.

Grenzen und Hinweise

  • Die Leistung verschlechtert sich, wenn die Anzahl der Ziele über drei oder vier hinauswächst – die Crowding Distance wird in hohen Dimensionen zu einem schlechten Diversitätsmaß.
  • Erfordert sorgfältige Abstimmung von Populationsgröße und Anzahl der Generationen; zu wenige Generationen verhindern eine angemessene Abdeckung der Front.
  • Die Auswertung von Zielfunktionen, die teure Simulationen beinhalten, macht den Algorithmus rechnerisch aufwendig.
  • Die Ergebnisse sind stochastisch: Unterschiedliche Zufalls-Seeds können zu unterschiedlichen Pareto-Fronten führen, daher werden mehrere Durchläufe und statistische Vergleiche (z. B. Hypervolumen) empfohlen.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Erzeugt eine vielfältige Menge von Pareto-optimalen Kompromisslösungen in einem einzigen Durchlauf, wodurch die Notwendigkeit entfällt, die Optimierung mit unterschiedlichen Gewichten zu wiederholen.
  • Die schnelle nicht-dominierte Sortierung läuft in O(MN²) Zeit (M Ziele, N Populationsgröße), was sie für moderate Problemgrößen handhabbar macht.
  • Die elitistische Selektion stellt sicher, dass früh gefundene gute Lösungen niemals verworfen werden.
  • Anwendbar auf kontinuierliche, binäre und kategorische Entscheidungsvariablen ohne Verteilungsannahmen.
  • Weit verbreitet in den Bereichen Ingenieurwesen, Operations Research und Computerwissenschaften validiert.

Anwendungen

  • Technische Konstruktion: Gleichzeitige Minimierung des Gewichts und Maximierung der strukturellen Festigkeit von mechanischen Komponenten.
  • Umwelt- und Energiesysteme: Abwägung von Kosten, Emissionen und Zuverlässigkeit bei der Planung von Stromnetzen oder erneuerbaren Energien.
  • Gesundheitswesen und Operations Research: Zeitplanung, die gleichzeitig Patientenwartezeiten, Ressourcenauslastung und Kosten optimiert.
  • Portfolio-Optimierung in der Finanzwelt und Projektauswahl in der Wirtschaft: Abwägung von Rendite, Risiko und Liquidität.
  • Hyperparameter-Tuning im maschinellen Lernen: Optimierung der Genauigkeit gegenüber Modellkomplexität oder Inferenzzeit.

So funktioniert es

So funktioniert es

1

Eine Population von Kandidatenlösungen wird durch zufällige Stichprobenziehung von Entscheidungsvariablen (oder durch Design) innerhalb ihrer Grenzen erstellt. Die Populationsgröße wird so gewählt, dass von Anfang an eine Diversität über den Zielfunktionsraum gewährleistet ist.

2

Jede Kandidatenlösung wird in Werte von Entscheidungsvariablen dekodiert und jede Zielfunktion wird ausgewertet. Das Ergebnis ist ein Vektor von Zielpunktzahlen pro Individuum. Dieser Schritt ist oft der rechnerische Engpass, wenn Ziele Simulationen oder teure Modelle beinhalten.

3

Lösungen werden durch nicht-dominierte Sortierung eingestuft: Die erste Front enthält alle Lösungen, die keine andere Lösung in jedem Ziel dominiert; die zweite Front enthält Lösungen, die nur von denen in der ersten Front dominiert werden; und so weiter. Innerhalb jeder Front wird eine Crowding-Distance-Punktzahl berechnet, um zu messen, wie isoliert eine Lösung von ihren Nachbarn ist – eine höhere Crowding Distance bedeutet, dass die Lösung eine weniger überfüllte Region der Front einnimmt.

4

Eine elitistische Selektionsstrategie verschmilzt die aktuelle Population mit Nachkommen und behält die besten N Individuen bei, füllt die Fronten in der Reihenfolge auf und verwendet die Crowding Distance, um Gleichstände in der letzten zulässigen Front aufzulösen. Dies garantiert, dass gute Lösungen aus früheren Generationen niemals verloren gehen.

5

Ausgewählte Individuen reproduzieren sich durch genetische Operatoren – binäre Turnierselektion, simuliertes binäres Crossover (SBX) und polynomiale Mutation –, wodurch eine neue Nachkommenpopulation entsteht. Diese Operatoren erhalten sinnvolle Variationen und erkunden gleichzeitig die Nachbarschaft vielversprechender Lösungen.

6

Schritte werden für eine vorgegebene Anzahl von Generationen durchlaufen und wiederholt. Die Konvergenz wird durch visuelle Inspektion der Pareto-Front oder durch Verfolgung des Hypervolumen-Indikators beurteilt. Die endgültige Ausgabe ist die Menge der nicht-dominierten Lösungen, die die wahre Pareto-Front annähert.

Häufige Fallstricke

  • Weniger als mehrere hundert Generationen zu durchlaufen, ergibt typischerweise eine unvollständige Pareto-Front; wenn das Rechenbudget knapp ist, ziehen Sie stattdessen eine gewichtete Einzieloptimierung in Betracht.
  • Die Behandlung eines Problems mit einem einzigen Ziel als Mehrzielproblem ist unnötig – verwenden Sie einen Einziel-Optimierer.
  • Das Versäumnis, sinnvolle Grenzen für Variablen festzulegen, führt dazu, dass Populationen niemals zulässige oder sinnvolle Bereiche des Suchraums erreichen.
  • Die Berichterstattung über nur eine Lösung aus der Pareto-Front, ohne die gesamte Front offenzulegen, verbirgt die Kompromissstruktur, die NSGA-II aufdecken soll.

Häufig gestellte Fragen

Wie viele Generationen benötigt NSGA-II?

Es gibt keine allgemeingültige Regel, aber weniger als einige hundert Generationen zu durchlaufen, ergibt typischerweise eine unvollständige Pareto-Front. Ein praktischer Ansatz ist, den Hypervolumen-Indikator über die Generationen hinweg zu plotten und zu stoppen, wenn er sich stabilisiert. Wenn das Rechenbudget dies nicht zulässt, ist ein gewichteter Einziel-Optimierer eine sicherere Alternative.

Was ist die Pareto-Front?

Die Pareto-Front ist die Menge von Lösungen, bei denen keine Verbesserung eines Ziels möglich ist, ohne mindestens ein anderes zu verschlechtern. NSGA-II nähert diese Front an und liefert Ihnen die vollständige Auswahl an ausgewogenen Kompromissen anstelle einer einzelnen Antwort.

Kann NSGA-II mehr als zwei Ziele verarbeiten?

Ja, aber die Crowding Distance – der Diversitätsmechanismus – wird weniger effektiv, wenn die Anzahl der Ziele drei oder vier übersteigt (das 'Many-Objective'-Regime). Für Probleme mit fünf oder mehr Zielen werden im Allgemeinen NSGA-III oder auf Dekomposition basierende Algorithmen wie MOEA/D bevorzugt.

Ist NSGA-II deterministisch?

Nein. Die genetischen Operatoren und die Anfangspopulation beinhalten Zufälligkeit, sodass unterschiedliche Läufe mit unterschiedlichen Zufalls-Seeds zu unterschiedlichen Pareto-Front-Approximationen führen können. Best Practice ist, den Algorithmus mehrmals laufen zu lassen und die Frontqualität mit dem Hypervolumen-Indikator zu vergleichen.

Verwandte Methoden

Quellen

  1. Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

    DOI-Referenz öffnen
    Kopiert.
  2. Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.

    DOI-Referenz öffnen
    Kopiert.