NSGA-II verständlich erklärt

Wer eine Wohnung sucht, will wenig Miete und einen kurzen Weg zur Arbeit. Beides zugleich bekommt man selten. Diese Seite zeigt, wie ein Rechenverfahren solche Zielkonflikte angeht, ohne vorher zu entscheiden, was wichtiger ist.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Zwei Wünsche, die sich beißen

Sie suchen eine Wohnung. Sie möchten wenig Miete zahlen und nah an der Arbeit wohnen. Nehmen wir an, die günstigen Wohnungen liegen weit draußen und die nahen sind teuer. Dann gibt es keine Wohnung, die in beidem zugleich die beste ist.

Trotzdem lassen sich manche Wohnungen sofort ausschließen. Wohnung X schlägt Wohnung Y, wenn sie in beidem mindestens so gut ist und in einem von beiden besser. Ist X billiger und liegt gleich nah, fällt Y weg. Wohnungen, die keine andere schlägt, bleiben übrig. Wir nennen sie die ungeschlagenen (Fachleute sagen Pareto-Front).

Unter den ungeschlagenen ist keine die eindeutig beste. Eine ist billig und weit, eine nah und teuer, dazwischen liegen Mischungen. Welche für Sie passt, hängt davon ab, was Ihnen wichtiger ist.

Warum ein fester Umrechnungskurs nicht reicht

Man könnte beide Wünsche in eine Zahl pressen. Zum Beispiel soll eine Minute Arbeitsweg so viel zählen wie ein bestimmter Mietbetrag. Mit diesem festen Kurs bekommt jede Wohnung eine Punktzahl, und die beste gewinnt. Das ist einfach, hat aber zwei Haken.

• Den Kurs legen Sie fest, bevor Sie die Wohnungen sehen. Eine Auswahl vor Augen hätte Sie vielleicht umgestimmt.
• Manche ungeschlagene Wohnung kann bei keinem Kurs gewinnen. Nehmen wir drei Wohnungen an: eine billige und weite, eine teure und nahe und eine mittlere. Keine schlägt die mittlere. Aber sie ist teurer und weiter, als es der Durchschnitt aus den beiden äußeren wäre. Diesen Durchschnitt gibt es nur als Rechenwert, eine solche Wohnung existiert nicht. Seine Punktzahl liegt zwischen denen der beiden äußeren, und die mittlere schneidet noch schlechter ab. Also liegt bei jedem festen Kurs eine der beiden äußeren vor ihr. Sie wird nie gewählt, obwohl keine echte Wohnung sie schlägt.

Das Rechenverfahren NSGA-II verzichtet deshalb auf den Kurs. Es sucht gleich die ganze Auswahl der ungeschlagenen.

Das Beispiel dieser Seite: Routen für einen Lieferwagen

Statt Wohnungen betrachtet das Verfahren Fahrtrouten. Ein Lieferwagen fährt vom Lager mehrere Kunden an und kehrt zurück. Die beiden Wünsche sind eine kurze Strecke und wenig Treibhausgas (CO2). Beides ist nicht dasselbe, denn manche Straßenabschnitte sind kurz, aber CO2-reich. Auf Wunsch kommt die Fahrzeit als dritter Wunsch dazu. Kunden und Straßenwerte sind zufällig erzeugt.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, kurz Demo. Am Ende dieses Teils gibt es zwei Knöpfe: Der erste öffnet die Demo, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht. Alle Aussagen in diesem Teil beschreiben das vereinfachte Rechenbeispiel, nicht die Wirklichkeit.

So arbeitet NSGA-II

Das Verfahren hält eine Gruppe von Routen bereit (Fachleute sagen Population), in der Demo voreingestellt 60. Am Anfang sind es zufällige Routen. Dann wiederholt es Runde für Runde vier Schritte.

• Ränge vergeben. Alle ungeschlagenen Routen bekommen Rang 1. Denkt man sie weg, sind unter den übrigen wieder einige ungeschlagen: Rang 2. So geht es weiter, bis jede Route einen Rang hat.
• Das Gedränge messen. Innerhalb eines Rangs zählt, wie ähnlich eine Route ihren Nachbarn ist, also wie dicht ihre Werte für Strecke und CO2 bei denen anderer Routen liegen (Fachleute sagen Crowding-Distance). Liegen viele Routen dicht beieinander, herrscht Gedränge, und eine einzelne davon ist leicht zu ersetzen. Eine Route am Rand der Auswahl oder mit viel Abstand zu den Nachbarn zeigt etwas Eigenes und ist wertvoll. Sonst gingen die Enden der Auswahl verloren.
• Neue Routen bauen. Zwei Routen werden gemischt, gelegentlich werden zwei Kunden getauscht. Wer Elternteil wird, bestimmt ein Turnier: Zwei zufällige Routen treten an, die mit dem besseren Rang gewinnt, bei gleichem Rang die mit mehr Abstand zu den Nachbarn.
• Auslesen. Alte und neue Routen kommen zusammen. Die Gruppe behält nur so viele wie vorher: erst Rang 1, dann Rang 2 und so weiter. Passt ein Rang nicht mehr ganz hinein, fallen zuerst die Routen im Gedränge weg.

Eine Route von Rang 1 fällt nur heraus, wenn es mehr davon gibt als Plätze. Deshalb wandert die Gruppe Runde für Runde auf die ungeschlagene Auswahl zu. In einem Lauf der Demo mit 30 Kunden schlug am Ende keine der 60 Routen der Gruppe eine andere aus der Gruppe. Ob sie die wahre Auswahl treffen, ist bei so vielen Kunden nicht bekannt.

Was die Messung zeigt

Findet das Verfahren die ganze Auswahl? Die Demo prüft das an einer kleinen Aufgabe mit 8 Kunden. Dort lassen sich alle Routen durchprobieren und so die wahre Auswahl bestimmen. Sie besteht aus 8 Kompromissen. Das Verfahren lief zehn Mal mit jeweils anderem Zufall. Man zählt, wie viele der 8 wahren Kompromisse die Endgruppe enthält. Ordnet man die zehn Läufe nach dieser Zahl, liegt der mittlere Lauf bei 6 von 8. Eine feste Punktzahl, mit mehreren Kursen ausprobiert, traf am selben Beispiel 4 von 8. Dieser Wert stammt aus einer anderen Untersuchung mit eigenem Rechenaufwand, und der schlechteste der zehn Läufe von NSGA-II traf ebenfalls nur 4. Der Vorsprung ist an einem einzigen Beispiel gemessen.

Wird es schwerer, wenn ein drittes Ziel dazukommt? Das hängt davon ab, wie groß die Gruppe ist: Mehr Routen bedeuten mehr Rechenaufwand. Mit 60 Routen fand der mittlere Lauf bei drei Zielen alle 15 Kompromisse, bei zwei Zielen 6 von 8. Mit nur 10 Routen war es umgekehrt: Der mittlere Lauf traf bei zwei Zielen die Hälfte der Kompromisse, bei drei Zielen ein Drittel. Bei drei Zielen ist die Auswahl größer, denn eine Route schlägt eine andere nur, wenn sie in allen drei Zielen mindestens so gut ist. Das gelingt seltener.

Häufige Missverständnisse

• „Sind alle ungeschlagen, gibt es viele verschiedene Lösungen.“ Nicht unbedingt. Zwei gleiche Routen schlagen sich nicht, denn keine ist in einem Ziel besser. Doppelgänger zählen also alle als ungeschlagen. Im Lauf mit 30 Kunden waren von den 60 gegeneinander ungeschlagenen Routen weniger als ein Drittel verschieden. Vermutlich entstehen die Doppelgänger, weil gute Routen kopiert und nur gelegentlich verändert werden; die Messung zeigt den Grund nicht.
• „Das Verfahren liefert die beste Route.“ Es liefert eine Auswahl ungeschlagener Routen. Welche man fährt, entscheidet man danach selbst. Außerdem findet es nicht jeden Kompromiss: Der mittlere Lauf verfehlte im kleinen Beispiel 2 von 8.

Woran Sie das im Alltag erkennen

• Nennt ein Vergleichsportal eine einzige „beste Verbindung“, steckt dahinter eine Gewichtung von Preis und Dauer, die jemand vorab festgelegt hat. Zeigt es dagegen eine Liste, in der jede Verbindung teurer, aber schneller ist als die davor, sehen Sie eine Auswahl ungeschlagener Verbindungen. Ob es alle sind, sagt die Liste nicht.
• Eine Gesamtnote fasst mehrere Eigenschaften zusammen. Ein Gerät, das in einer Eigenschaft sehr schlecht und in zwei sehr gut ist, kann dieselbe Note bekommen wie ein durchschnittliches.

Wie ernst ist das Rechenbeispiel zu nehmen?

Die Aufgabe ist klein und erfunden, mit zufälligen Kunden und Straßenwerten und nur zehn Läufen. Wie gut das Verfahren echte Routenplanung löst, sagen die Zahlen nicht.

Was Sie mitnehmen

• Verlangen Sie vor jeder Entscheidung die ganze Auswahl der ungeschlagenen Möglichkeiten, nicht nur den Sieger einer einzigen Rechnung.
• Prüfen Sie bei einer langen Auswahl, ob die Einträge wirklich verschieden sind.
• Hängt ein Ergebnis vom Zufall ab, trauen Sie dem mittleren von mehreren Läufen mehr als einem einzelnen.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt das Beispiel, das die Demo rechnet, und das Verfahren NSGA-II (Non-dominated Sorting Genetic Algorithm II).

• Aufgabe: mehrere Ziele gleichzeitig minimieren, ohne sie vorab zu einer Zahl zusammenzurechnen. Gesucht ist eine Näherung der Pareto-Front, der Menge der nicht dominierten Zielwerte.
• Instanz: eine Rundtour durch ein Depot in der Mitte und \(n\) Kundenstopps in einem Gebiet von 100 × 100 km mit euklidischen Entfernungen \(\ell\) (voreingestellt \(n = 30\), einstellbar von 8 bis 100). Ein einstellbarer Anteil der Stopps liegt in fünf Gruppen (Städten), der Rest gleichverteilt; voreingestellt gibt es keine Gruppen.
• Ziele: Distanz \(f_1\), CO2 \(f_2\) und optional Fahrzeit \(f_3\). Mit \(t\) als Position in der Tour \(\pi\), zyklisch gelesen (die letzte Kante führt zum Depot zurück), gilt \(f_1 = \sum_t \ell_{\pi(t)\pi(t+1)}\) und \(f_i = \sum_t \ell_{\pi(t)\pi(t+1)}\, c^{(i)}_{\pi(t)\pi(t+1)}\) für \(i = 2, 3\). Der Faktor \(c^{(i)}\) wird je Kante im Bereich 0,6 bis 3,4 gezogen, symmetrisch, unabhängig von der Distanz und voneinander. Manche Abschnitte sind also kurz, aber CO2-reich oder langsam, andere lang, aber sparsam.
• Verfahren: eine Population aus \(N\) Touren (voreingestellt \(N = 60\) und 150 Generationen), Turnierauswahl der Größe \(k\) (voreingestellt \(k = 2\)), Order Crossover, Tausch-Mutation und elitäre Überlebensauswahl über Rang und Crowding-Distance. Beim Order Crossover übernimmt das Kind ein zufälliges Teilstück des ersten Elternteils und füllt die übrigen Plätze mit den fehlenden Knoten in der Reihenfolge des zweiten Elternteils, sodass wieder eine gültige Tour entsteht. Die Tausch-Mutation vertauscht zwei zufällig gewählte Knoten einer Tour. Elitär heißt: Eltern und Kinder konkurrieren gemeinsam um die \(N\) Plätze, gute Eltern gehen also nicht verloren. Crossover-Rate (Voreinstellung neun Zehntel je Kind), Mutationsrate (Voreinstellung ein Fünftel je Kind, höchstens ein Tausch) und Turniergröße sind feste Einstellungen und werden nicht aus dem Verlauf gelernt.
• Referenzfront: Bei kleinen Instanzen (bis zu 9 Knoten, also Depot plus bis zu 8 Stopps) werden alle Touren aufgezählt, mit festem Depot an erster Stelle bis zu \(8! = 40\,320\) Touren (eine Tour und ihr Spiegelbild einzeln gezählt). Die wahre Front besteht aus den nicht dominierten eindeutigen Zielwerten; Werte gelten als gleich, wenn sie sich erst jenseits der sechsten Nachkommastelle unterscheiden. Ein Frontpunkt gilt als getroffen, wenn die Endfront einen Zielwert hat, der in jedem Ziel um höchstens ein Millionstel abweicht.
• Güte der Front: nur bei zwei Zielen als Hypervolumen \(\mathrm{HV}\), der von der Front dominierten Fläche gegen einen festen Referenzpunkt \(R\), der in jedem Ziel schlechter ist als jeder Frontpunkt (hier je Ziel um ein Zehntel über dem größten Wert einer Stichprobe von zweitausend Zufallstouren der Instanz). Je größer \(\mathrm{HV}\), desto besser; Güte und Breite der Front gehen zugleich ein, und der Wert ist nur innerhalb derselben Instanz vergleichbar.

Dominanz, Rang und Crowding-Distance

Alle Ziele werden minimiert. Eine Tour \(a\) dominiert eine Tour \(b\), wenn \(a_i \le b_i\) für alle Ziele \(i\) und \(a_j < b_j\) für mindestens ein \(j\) gilt. Front 1 sind die nicht dominierten Individuen der Population, Front \(r\) die nicht dominierten, nachdem die Fronten \(1, \dots, r-1\) entfernt wurden. Individuen mit gleichen Zielwerten dominieren sich nicht, denn es gibt kein \(j\) mit strikter Verbesserung.

Innerhalb einer Front misst die Crowding-Distance \(d_p\) eines Individuums \(p\) bei \(M\) Zielen das Mittel über die Ziele von normierten Abständen. Dazu wird die Front für jedes Ziel \(i\) nach \(f_i\) sortiert; \(p^{+}\) und \(p^{-}\) sind die beiden Nachbarn von \(p\) in dieser Reihenfolge (nächstgrößerer und nächstkleinerer Wert), und der Abstand \(f_i(p^{+}) - f_i(p^{-})\) wird durch die Spanne \(f_i^{\max} - f_i^{\min}\) der Front im Ziel \(i\) geteilt:

\[d_p = \frac{1}{M}\sum_{i=1}^{M} \frac{f_i(p^{+}) - f_i(p^{-})}{f_i^{\max} - f_i^{\min}}\]

Randindividuen je Ziel erhalten \(d_p = \infty\); dasselbe gilt für Fronten mit höchstens zwei Individuen. Die Division durch \(M\) ist eine reine Reskalierung, ändert keinen Vergleich und entspricht der Bibliothek pymoo. Verglichen wird mit dem Crowded-Comparison-Operator: \(a \prec_n b\), wenn \(\mathrm{rang}(a) < \mathrm{rang}(b)\) gilt oder bei gleichem Rang \(d_a > d_b\).

Das Hypervolumen \(\mathrm{HV}\) einer nicht dominierten Front \(F\) mit den Punkten \((x_s, y_s)\), aufsteigend nach dem ersten Ziel sortiert, und \(x_{|F|+1} := R_1\) ist \(\mathrm{HV} = \sum_{s=1}^{|F|} (x_{s+1} - x_s)(R_2 - y_s)\).

Der Ablauf einer Generation

• Start: \(N\) zufällige Touren, Zielwerte berechnen, schnelle nicht dominierte Sortierung und Crowding-Distance je Front.
• Eltern: Es werden \(N\) Turniere aus je \(k\) zufälligen Individuen ausgetragen; es gewinnt der niedrigere Rang, bei Gleichstand die größere Crowding-Distance. Für den \(m\)-ten Nachkommen ist der \(m\)-te Turniersieger der erste Elternteil, der zweite Elternteil ist zufällig unter den \(N\) Siegern gewählt. Je Elternpaar entsteht ein Kind.
• Nachkommen: Order Crossover mit der Crossover-Rate, sonst eine Kopie des ersten Elternteils; danach Tausch-Mutation mit der Mutationsrate. Es entstehen \(N\) Nachkommen.
• Überleben: Eltern und Nachkommen (\(2N\) Individuen) werden zusammen sortiert. Die Fronten werden der Reihe nach übernommen, bis die nächste nicht mehr ganz passt; aus ihr bleiben die Individuen mit der größten \(d_p\). Ein Individuum von Front 1 geht deshalb nur verloren, wenn Front 1 mehr als \(N\) Individuen enthält.
• Aufwand: Die Sortierung nutzt eine \(N \times N\)-Dominanzmatrix und wächst damit quadratisch in der Populationsgröße. Für die Referenzfront aller Touren wäre die Matrix mit 1,6 Milliarden Paaren zu groß; dort wird gegen eine laufend aktualisierte, meist kleine Front gefiltert (Aufwand etwa Zahl der Touren mal Frontgröße).

Herleitung und Handrechnung

Dieser Block ist Rechnung dieser Seite, keine Messung der Demo.

• Schritt 1, warum eine feste Gewichtung Punkte verfehlt: Gewählt sei ein Gewichtsvektor \(w \ge 0\), und \(w^{\top} f\) werde minimiert. Gibt es Frontpunkte \(A\), \(B\) und ein \(\lambda \in [0, 1]\) mit \(f(C) \ge \lambda f(A) + (1-\lambda) f(B)\) in jedem Ziel, so folgt \(w^{\top} f(C) \ge \lambda\, w^{\top} f(A) + (1-\lambda)\, w^{\top} f(B) \ge \min\{w^{\top} f(A), w^{\top} f(B)\}\). Der Punkt \(C\) ist bei keinem Gewicht strikt besser als \(A\) oder \(B\). Er kann trotzdem nicht dominiert sein, wenn \(A\) in einem Ziel besser und \(B\) im anderen besser ist. Eine Nachrechnung dieser Seite an der Front der kleinen Instanz (2 Ziele, 8 Punkte) ergibt, dass nur 4 der 8 Punkte Ecken der unteren konvexen Hülle sind. Die anderen 4 sind bei keinem Gewicht der eindeutige Minimierer. Das passt zu den gemessenen 4 von 8, belegt aber nicht, dass die Lücke allein daran liegt: Auch ein Suchverfahren, das die gewichtete Summe minimiert, kann Ecken verfehlen.
• Schritt 2, Rang und Crowding von Hand: Sechs Touren mit den Zielwerten \((1|5)\), \((2|3)\), \((4|1)\), \((2|5)\), \((3|3)\), \((5|2)\). Front 1 sind die ersten drei, denn jede andere Tour wird von mindestens einer von ihnen dominiert: \((2|5)\) von \((1|5)\), \((3|3)\) von \((2|3)\), \((5|2)\) von \((4|1)\). Die übrigen drei sind untereinander nicht dominiert und bilden Front 2. In Front 1 liegt \((2|3)\) im ersten Ziel zwischen 1 und 4 bei einer Spanne von 3, im zweiten zwischen 1 und 5 bei einer Spanne von 4. Beide normierten Abstände sind 1, also ist \(d_p = (1 + 1)/2 = 1\). Die Randtouren \((1|5)\) und \((4|1)\) haben \(d_p = \infty\).
• Schritt 3, Überleben von Hand: Angenommen, aus diesen sechs Touren sollen vier bleiben. Front 1 (drei Touren) passt ganz hinein, aus Front 2 bleibt ein Platz. Dort rechnet man wie in Schritt 2: \((3|3)\) hat \(d_p = 1\), die beiden Randtouren \((2|5)\) und \((5|2)\) haben \(d_p = \infty\). Die Mitteltour fällt zuerst weg. Welche der beiden Randtouren den letzten Platz bekommt, entscheidet ein Gleichstand ohne weitere Regel.
• Schritt 4, Hypervolumen von Hand: Für die Front \((1|3)\), \((2|2)\), \((3|1)\) und \(R = (4|4)\) ergibt die Formel \(1 \cdot 1 + 1 \cdot 2 + 1 \cdot 3 = 6\).
• Schritt 5, warum Doppelgänger Front 1 füllen: Zwei Touren mit gleichen Zielwerten erfüllen \(a_i \le b_i\) für alle \(i\), aber nie \(a_j < b_j\). Keine dominiert die andere, also stehen beide in derselben Front, und eine Population aus wenigen verschiedenen Touren kann vollständig in Front 1 liegen.

Befunde

Alle Werte außer dem der gewichteten Summe und der Zufallssuche (Probelauf dieser Seite) stammen aus Läufen der Demo. Die Werte zu getroffenen Frontpunkten sind Mediane über zehn Läufe mit verschiedenen Zufallsfolgen auf derselben Instanz. Die kleine Vergleichsinstanz hat 8 Stopps. Ihre wahre Front mit zwei Zielen hat 8 Punkte, mit drei Zielen 15 Punkte. Die Abdeckung ist der Anteil der wahren Frontpunkte, die ein Lauf trifft. Die Messungen zur Populationsgröße und zur Konvergenz sind Einzelläufe auf der Instanz mit 30 Stopps.

Frage	Befund
Trifft NSGA-II die Front besser als eine feste Gewichtung? (kleine Instanz, 2 Ziele, \(N = 60\), 150 Generationen)	NSGA-II trifft im Median 6 von 8 Frontpunkten, die gewichtete Summe 4 von 8. Der zweite Wert ist aus einer anderen Demo auf derselben Instanz übernommen (ein festes Gewicht je Lauf, acht Gewichte mit je fünf Läufen zusammengenommen) und wird hier nicht neu gerechnet; das Rechenbudget ist nicht angeglichen.
Wie schneidet eine reine Zufallssuche ab? (kleine Instanz, 2 Ziele; Probelauf dieser Seite, nicht Teil der Demo)	Zehn Ziehungen mit Zurücklegen aus allen Touren, jeweils so viele wie NSGA-II bewertet (Anfangsgruppe plus 150 Generationen mit je 60 Nachkommen, gut ein Fünftel der Zahl aller Touren): Median 2 von 8 getroffenen Frontpunkten, Spanne 1 bis 4, gegen 6 bei NSGA-II. Die Basis ist kein Teil der Demo.
Wird die Abdeckung mit mehr Zielen schwächer? (kleine Instanz, knappes Budget \(N = 10\))	Abdeckung von 50 % bei 2 Zielen auf 33,3 % bei 3 Zielen. Nachgerechnet sind das im Median 4 von 8 und 5 von 15 Punkten.
Und bei großzügigem Budget? (kleine Instanz, \(N = 60\))	Keine Verschlechterung, im Gegenteil: 6 von 8 Punkten (75 %) bei 2 Zielen, alle 15 Punkte bei 3 Zielen.
Hilft eine größere Population? (Instanz mit 30 Stopps, 2 Ziele, Einzellauf je Größe, Bezug \(N = 60\))	Hypervolumen bei 150 Individuen +9 %, bei 15 Individuen −16 %. Mit der Populationsgröße ändert sich auch der Rechenaufwand; der Vergleich ist nicht aufwandsgleich.
Konvergiert die Population zur vollen Front? (Instanz mit 30 Stopps, \(N = 60\), 150 Generationen, Einzellauf)	Front 1 wächst von 1 Individuum in der Startpopulation auf alle 60. Die Endpopulation besteht aus weniger als einem Drittel verschiedener Touren.

Messfallen bei der Referenzfront: Zunächst zählte die Aufzählung Touren statt eindeutiger Zielwerte, weil zwei Touren denselben Zielwert erreichen können; die kleine Instanz kam dadurch auf 9 statt 8 Frontpunkte. Bei drei Zielen blieb ein Scheinpunkt: Eine gespiegelte Tour summiert dieselben Kanten in anderer Reihenfolge, die Zielwerte unterscheiden sich nur um Rauschen der Fließkommazahlen, und beide Zeilen blieben nicht dominiert. Die Front hatte 16 statt 15 Punkte, die Abdeckung unter knappem Budget 6 von 16 (37,5 %) statt 5 von 15. Seit der Rundung auf 6 Nachkommastellen stimmt die Aufzählung auf kleinen Instanzen mit einer unabhängigen Zählung überein.

Grenzen und was die Messung zeigt

Das zeigt die Messung:

• Die nicht dominierte Sortierung und die Crowding-Distance stimmen mit der Bibliothek pymoo überein, geprüft an 30 beziehungsweise 20 zufälligen Instanzen mit zwei bis drei Zielen, dazu mit einer Handrechnung an sechs Punkten und mit einer unabhängigen Neuimplementierung. Das Hypervolumen stimmt mit einer Rechteckvereinigung überein.
• Die Aufzählung aller Touren stimmt auf kleinen Instanzen mit einer unabhängigen Aufzählung überein, auch bei drei Zielen.

Das zeigt sie nicht:

• Der Vergleich mit der Gewichtung beruht auf einer einzigen Instanz mit 8 Stopps und zehn Läufen. Die Läufe streuen: Eine Nachrechnung dieser Seite ergibt zwischen 4 und 8 getroffenen Frontpunkten, der schlechteste Lauf liegt also auf dem Wert der Gewichtung. Der Vergleichswert der Gewichtung stammt aus einem anderen Verfahren mit eigenem Rechenbudget; die Rechenbudgets sind nicht angeglichen.
• Die Umkehrung bei knappem und großzügigem Budget ist klein und empfindlich gegen den Zufall; der Rückgang bei knappem Budget beruht auf einem Median von 5 von 15 gegen 4 von 8 getroffenen Punkten.
• Die Werte zur Populationsgröße und zur Konvergenz sind Einzelläufe. Einzelne Läufe mit 150 Generationen sind empfindlich gegen winzige Rundungsunterschiede (welche Tour bei einem Gleichstand gewinnt, kann sich über viele Generationen fortsetzen), deshalb können Werte auf anderer Rechnerausstattung abweichen. Dass Front 1 am Ende die ganze Population umfasst, sagt wegen gleicher Touren wenig über die Vielfalt der Lösungen.
• Eine Zeit- oder Aufwandsmessung enthält die Demo nicht, und die Wirkung der Operatorraten und der Turniergröße wird nicht untersucht.

Grenzen des Verfahrens und der Demo:

• Die Crowding-Distance garantiert keine gleichmäßige Abdeckung bei vielen Zielen. Mit drei Zielen ist das Beispiel zu klein, um diese Schwäche sauber zu zeigen; der gemessene Effekt ist klein, empfindlich gegen den Zufall und nur unter knappem Budget sichtbar. Als gängige Erklärung gilt, dass bei vielen Zielen fast alle Individuen nicht dominiert sind und der Rang kaum noch trennt; das misst die Demo nicht.
• Gleiche Touren werden nicht entfernt, anders als in manchen Bibliotheken. Der Abgleich mit pymoo gilt nur für Sortierung und Crowding-Distance.
• Die Dominanzsortierung wächst quadratisch in der Populationsgröße und wird bei sehr großen Populationen zum Engpass.
• Die Operatorraten sind von Hand gesetzt. Das Hypervolumen wird nur bei zwei Zielen berechnet; bei drei Zielen bräuchte es ein Volumenintegral statt der Rechteckzerlegung.
• Nicht umgesetzt sind mehr als drei Ziele, eine Referenzpunkt-Nischenbildung und ein allgemeines Hypervolumen in mehr Dimensionen.

Einordnung

Als Fortsetzung setzt nsga3-demo an der Schwäche bei vielen Zielen an: Referenzpunkte und Nischenbildung ersetzen die Crowding-Distance, geprüft mit vier Zielen. In deren Messung deckt NSGA-II bei vier Zielen auf der untersuchten Instanzgröße den Zielraum besser ab als NSGA-III. moead-demo dagegen sortiert nicht nach Dominanz, sondern zerlegt das Problem in skalare Unterprobleme, je eines pro Gewichtsvektor. Den Vergleichswert der gewichteten Summe übernimmt die Demo aus genetic-algorithm-demo; sie rechnet ihn nicht selbst.

Quellen

• 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.
• Blank, J., Deb, K. (2020): pymoo: Multi-objective optimization in Python. IEEE Access 8, 89497–89509.
• Zitzler, E., Thiele, L. (1999): Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation 3(4), 257–271 (zur Kennzahl Hypervolumen).
• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/nsga2-demo.

Die Demo nennt Deb et al. (2002) und die Bibliothek pymoo. Die Fundstellen dieser beiden Arbeiten und die Arbeit von Zitzler und Thiele sind aus dem Gedächtnis ergänzt und nicht nachgeschlagen.