Maximum Dispersion, Maximum Concentration: Enhancing the Quality of MOP Solutions

Technische Zusammenfassung: Maximale Dispersion, Maximale Konzentration

Problemdefinition
Multi-Objective Optimization Problems (MOPs) erfordern einen Ausgleich zwischen widersprüchlichen Zielen, wobei üblicherweise die Annäherung an die Pareto-Front (PF) im Objektivraum angestrebt wird. Während traditionelle Multi-Objective Evolutionary Algorithms (MOEAs) effektiv zur PF konvergieren, leiden sie häufig unter einer kritischen Einschränkung: Lösungen neigen dazu, sich in spezifischen Regionen des Entscheidungsraums zu gruppieren. Dieser Mangel an Diversität im Entscheidungsraum ($\Omega$) führt zu einem Implementierungs-Bias, bei dem Entscheidungsträgern eine enge Auswahl an Optionen präsentiert wird, die unpraktikabel werden kann, falls sich die Ausgangsbedingungen ändern. Umgekehrt gibt es zwar präferenzbasierte Methoden, um die Suchbemühungen auf eine bestimmte Region of Interest (ROI) im Objektivraum zu fokussieren, um die Konvergenz zu verbessern, doch adressieren diese selten das gleichzeitige Bedürfnis nach maximaler Dispersion im Entscheidungsraum. Das Paper identifiziert eine Lücke in der Literatur hinsichtlich der simultanen Optimierung der Lösungskonzentration im Objektivraum und der Dispersion im Entscheidungsraum.

Methodik: Der C-DWU-Algorithmus
Die Autoren schlagen den C-DWU-Algorithmus (Cone-Dominance Weighted Uniformity) vor, eine Adaption des bestehenden Dominance-Weighted Uniformity (DWU)-Ansatzes. Die Methodik integriert die Präferenzen eines Entscheidungsträgers, definiert durch einen Präferenzkegel $C$ (charakterisiert durch einen Achsenvektor $v$ und einen Öffnungswinkel $\theta$), durch zwei spezifische Modifikationen in den Evolutionsprozess:

1. Bestrafte Nicht-dominierte Sortierung: Während der Sortierungsphase werden Lösungen, die außerhalb des Präferenzkegels $C$ liegen, bestraft. Die Bestrafung ist proportional zum Winkelabstand ($\phi$) zwischen dem Objektivvektor der Lösung und der Kegelachse $v$. Dies wird mittels einer Bestrafungsfunktion $P_{\alpha,\theta}(\phi) = \lfloor e^{\alpha(\phi-\theta)} \rfloor$ berechnet, welche das Nicht-dominanz-Front-Niveau auswärtiger Lösungen erhöht und so die Suche effektiv in Richtung der ROI drängt.
2. Modifizierte Selektionsheuristik (C-wd): Die Standard-DWU-Selektionsheuristik, die die Uniformität im Entscheidungsraum maximiert, wird modifiziert, um den Präferenzkegel einzubeziehen. Eine neue Funktion, C-wd, wendet einen Bestrafungsterm $P_{\beta,\theta}(\phi)$ auf die Dominanz-gewichtete Uniformitätsberechnung für Lösungen außerhalb des Kegels an. Dies stellt sicher, dass der Algorithmus, während er versucht, den Abstand zwischen den Lösungen im Entscheidungsraum zu maximieren (Dispersion), jene priorisiert, die auch die Konzentrationsbeschränkungen innerhalb der ROI im Objektivraum erfüllen.

Der Algorithmus zielt darauf ab, eine Teilmenge von Lösungen zu finden, die Pareto-optimal, konzentriert innerhalb der definierten ROI im Objektivraum und maximal dispergiert innerhalb des Entscheidungsraums sind.

Experimentelles Setup und Ergebnisse
Die Autoren evaluierten C-DWU gegenüber einer modifizierten Version von NSGA-II (bezeichnet als C-NSGAII), die dieselbe kegelbasierte Bestrafung auf den Standard-NSGA-II anwendet, jedoch keinen Mechanismus für die Diversität im Entscheidungsraum besitzt. Experimente wurden auf bi-objektiven, eingeschränkten Optimierungsproblemen mit den Test-Suites WFG4, WFG9 (multimodal) und DTLZ2 (unimodal) mit Entscheidungsraumdimensionen von 5, 7 und 9 durchgeführt.

• Konvergenz (Objektivraum): Gemessen durch die Inverted Generational Distance (IGD) relativ zur ROI. Die Ergebnisse zeigen, dass C-NSGAII in den meisten Instanzen eine etwas bessere Konvergenz (niedrigere IGD-Werte) erreichte.
• Dispersion (Entscheidungsraum): Gemessen durch eine Uniformitätsmetrik basierend auf dem minimalen Abstand zwischen den Lösungen. C-DWU übertraf C-NSGAII signifikant und erreichte wesentlich höhere Uniformitätswerte.
• Visualisierung: Eine hochdimensionale Visualisierung (mittels CAP-VIZ) des WFG4-Problems zeigte, dass die Lösungen von C-NSGAII stark in einem einzigen Sektor des Entscheidungsraums (nahe der Achse $e_9$) gruppiert waren, während die Lösungen von C-DWU über mehrere Sektoren (7, 8 und 9) verteilt waren, mit größerer Variabilität sowohl im Winkelabstand als auch in der euklidischen Norm.

Zentrale Beiträge

• Dual-Objective Optimization: Das Paper führt einen Rahmen ein, der gleichzeitig die Lösungskonzentration in einer spezifischen ROI im Objektivraum maximiert und die Lösung-Dispersion im Entscheidungsraum maximiert.
• Algorithmische Adaption: Die Entwicklung von C-DWU, welches den DWU-Algorithmus modifiziert, um Präferenzkegel-Beschränkungen zu akzeptieren, ohne die Diversität im Entscheidungsraum zu opfern.
• Minderung von Bias: Der Ansatz adressiert das Problem „polarisierter“ Lösungen im Entscheidungsraum und bietet Entscheidungsträgern eine diverse Menge an Implementierungsoptionen, die alle innerhalb einer bevorzugten Region des Objektivraums optimal sind.

Bedeutung und Behauptungen
Die Autoren behaupten, dass die vorgeschlagene Methode die Qualität der MOP-Lösungen verbessert, indem sie Diversität und Genauigkeit ausbalanciert. Sie argumentieren, dass während der C-DWU-Algorithmus eine marginale Reduktion der Konvergenzraten im Vergleich zu C-NSGAII aufweisen kann, dieser Trade-off durch den erheblichen Gewinn an Lösungsvielfalt gerechtfertigt ist. Die primäre Bedeutung liegt darin, Entscheidungsträgern ein robustes Set an Optionen zur Verfügung zu stellen; diverse Lösungen im Entscheidungsraum ermöglichen Flexibilität, falls unvorhergesehene Änderungen in realen Szenarien auftreten, was eine kostspielige Re-Optimierung verhindert. Das Paper schließt mit der Feststellung, dass die Definition einer ROI via Präferenzkegel eine effektive und leicht anpassbare Methode ist, um die Präferenzen von Entscheidungsträgern in evolutionäre Algorithmen zu integrieren und gleichzeitig die Repräsentativität des Lösungssatzes zu bewahren.