On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III

Technische Zusammenfassung: Zum Einfluss des Crossovers bei der Many-Objective-Optimierung: Eine Laufzeitanalyse von NSGA-III

Problemstellung
Während das theoretische Verständnis von Multi-Objective Evolutionary Algorithms (MOEAs) wie NSGA-III im Hinblick auf Many-Objective-Probleme Fortschritte gemacht hat, bleiben die spezifischen theoretischen Vorteile des Einsatzes von Crossover-Operatoren in diesem Kontext weitgehend unverstanden. Bestehende theoretische Ergebnisse beschränken sich weitgehend auf bi-objektive Szenarien oder maßgeschneiderte Benchmarks, die auf spezifische Operatoren abgestimmt sind. Im Gegensatz dazu deuten empirische Belege darauf hin, dass Crossover in der Many-Objective-Optimierung hochgradig vorteilhaft ist. Diese Arbeit schließt die Lücke in der theoretischen Laufzeitanalyse, indem sie die Leistung von NSGA-III mit und ohne Crossover auf der klassischen $m$-Objektiv-$m$-ONEJUMPZEROJUMP ($m$-OJZJ)-Benchmark-Funktion untersucht.

Methodik
Die Autoren führen eine rigorose Laufzeitanalyse von NSGA-III auf der $m$-OJZJ$_k$-Benchmark durch, wobei $m$ die Anzahl der Zielgrößen, $n$ die Problemgröße und $k$ die Größe der Lücke (Fitness-Tal) darstellt. Die Analyse umfasst:

1. Algorithmisches Setup: Die Studie verwendet den Standard-NSGA-III-Algorithmus mit einer Populationsgröße $\mu$, einem uniformen Crossover mit Wahrscheinlichkeit $p_c$ und einer Standard-Bit-Mutation. Der Selektionsmechanismus stützt sich auf nicht-dominierte Sortierung und die Zuordnung zu Referenzpunkten, um die Diversität zu erhalten.
2. Benchmark-Funktion: Die $m$-OJZJ$_k$-Funktion besteht aus $m/2$ unabhängigen Blöcken. Jeder Block stellt ein Fitness-Tal der Größe $k$ dar, das überwunden werden muss, um die Pareto-optimalen Lösungen zu erreichen. Die Größe der Pareto-Front wächst exponentiell mit $m$.
3. Analytischer Ansatz: Die Autoren wenden probabilistische Methoden an, einschließlich Chernoff-Schranken, Vereinigungs-Schranken und Argumenten der stochastischen Dominanz. Sie analysieren die Laufzeit in Bezug auf die Anzahl der Generationen, die erforderlich ist, um die gesamte Pareto-Front abzudecken. Die Analyse ist in drei Teile unterteilt:
   • Eine obere Schranke für NSGA-III ohne Crossover (die sich ausschließlich auf Mutation stützt).
   • Eine obere Schranke für NSGA-III mit Crossover.
   • Eine untere Schranke für NSGA-III ohne Crossover für den spezifischen Fall von 4 Zielgrößen ($4$-OJZJ).

Hauptbeiträge und Ergebnisse

• Obere Schranke ohne Crossover:
  Die Arbeit zeigt, dass NSGA-III ohne Crossover im Erwartungswert $O(m^2 n \ln(n/m) + \delta m n k (1 + 2n/m)^{m/2} / \mu)$ Generationen benötigt, um die Pareto-Front mit hoher Wahrscheinlichkeit $1 - o(1) - e^{-(\delta-3)m}$ abzudecken.

  • Bedeutung: Dieses Ergebnis verallgemeinert frühere Erkenntnisse auf eine beliebige Anzahl von Zielgrößen $m$. Es hebt hervor, dass die Laufzeit vom Term dominiert wird, der die Größe der Pareto-Front $(1 + 2n/m)^{m/2}$ beinhaltet, die exponentiell mit $m$ wächst. Die Analyse zeigt, dass die Fähigkeit von NSGA-III, mehrere Individuen mit demselben Fitnessvektor zu behalten (aufgrund der Zuordnung zu Referenzpunkten), Robustheit über einen weiten Bereich von Populationsgrößen hinweg bietet.

• Obere Schranke mit Crossover:
  Die Autoren zeigen, dass NSGA-III mit uniformem Crossover $m$-OJZJ$_k$ asymptotisch schneller optimiert als die Variante, die nur Mutation verwendet. Die erwartete Anzahl der Generationen beträgt $O(k m^{k+1} n^k c^k \mu / k!)$ für eine geeignete Konstante $c$.

  • Bedeutung: Dies ergibt eine Beschleunigung der Ordnung $\Omega((k-1)! (1 + 2n/m)^{m/2} / (\mu^2 c^k m^k))$ im Vergleich zum Fall ohne Crossover. Unter spezifischen Parameterregimen (z. B. $k = \Omega(n/\ln n)$ und $m = O(\log n)$) wird diese Beschleunigung exponentiell. Der Mechanismus beruht darauf, dass Crossover zwei Individuen rekombiniert, die in einem bestimmten Block maximal voneinander entfernt sind (eines mit $k$ Einsen, eines mit $k$ Nullen in der Lücke), um sofort die optimale All-Eins- (oder All-Null-)Zeichenkette zu erzeugen und dabei das Fitness-Tal zu umgehen, das die Mutation Bit für Bit durchqueren müsste.

• Untere Schranke ohne Crossover (4-OJZJ):
  Für den spezifischen Fall von 4 Zielgrößen ($m=4$) und Populationsgrößen $\mu \in O(n^{k-2})$ beweist die Arbeit eine untere Schranke von $\Omega(n^k / \mu)$ Generationen für den Fall ohne Crossover.

  • Bedeutung: Diese untere Schranke ist größer als die für den Fall mit Crossover abgeleitete obere Schranke um einen Faktor von $(k-1)! / (\mu^2 d^k)$ (für eine Konstante $d$), was bei großem $k$ exponentiell ist. Dies bestätigt formal die Notwendigkeit von Crossover für eine effiziente Optimierung auf dieser Benchmark, wenn $k$ groß ist.

Bedeutung und Behauptungen
Die Arbeit behauptet, den ersten rigorosen theoretischen Nachweis zu liefern, dass Crossover signifikante, potenziell exponentielle Laufzeitbeschleunigungen in der Many-Objective-Optimierung bewirkt und damit über das bi-objektive Setting hinausgeht. Die Ergebnisse deuten darauf hin, dass NSGA-III zwar ohne Crossover robust ist, die Einbeziehung von Crossover jedoch entscheidend ist, um Fitness-Landschaften mit großen Tälern (großes $k$) in hochdimensionalen Zielgrößenräumen effizient zu navigieren.

Die Autoren weisen darauf hin, dass die Erweiterung der unteren Schranke auf $m > 4$ ohne Crossover aufgrund komplexer Wechselwirkungen zwischen den Zielgrößen und der Populationsdynamik erheblich schwieriger ist, was ein offenes Forschungsfeld für die Zukunft darstellt. Ebenso erfordert die Herleitung unterer Schranken für den Fall mit Crossover das Verständnis der Verteilung der Genotypen, nicht nur der Zielgrößenvektoren. Die Arbeit schließt, dass diese Erkenntnisse das theoretische Verständnis dafür verbessern, wann und warum MOEAs gut funktionieren, insbesondere hinsichtlich der Rolle des Crossovers beim Entkommen aus lokalen Optima und der Verbesserung der Sucheffizienz in Many-Objective-Szenarien.