💻 computer science

MO-ELA: Rigorously Expanding Exploratory Landscape Features for Automated Algorithm Selection in Continuous Multi-Objective Optimisation

Dieses Paper stellt MO-ELA vor, eine neuartige Menge explorativer Landschaftsmerkmale, die sowohl aus dem Entscheidungs- als auch aus dem Ziellraum abgeleitet werden und in fünf verschiedenen Kategorien unterteilt sind, was die automatisierte Algorithmenselektion für die kontinuierliche multikriterielle Optimierung signifikant verbessert, indem die Problemkomplexität effektiv erfasst und die Leistung der Algorithmen differenziert wird.

Ursprüngliche Autoren: Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

Veröffentlicht 2026-02-03

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Chefkoch, der entscheiden muss, welches Rezept er für eine Dinnerparty kochen soll. Sie haben ein riesiges Kochbuch mit tausenden von Rezepten (Algorithmen), aber Sie wissen, dass kein einzelnes Rezept perfekt für jede Art von Zutat funktioniert (Optimierungsproblem). Manche Gerichte erfordern einen sanften Umgang, andere eine kräftige Hand. Wenn Sie falsch raten, ist das Essen ruiniert.

Dies ist das Problem der Automatisierten Algorithmus-Selektion (AAS). Es ist, als hätte man einen klugen Sous-Chef, der auf Ihre spezifischen Zutaten blickt und Ihnen sofort sagt: „Für diese spezielle Kombination aus Zutaten verwende Rezept A, nicht Rezept B.“

Lange Zeit funktionierte dieser „Sous-Chef“ hervorragend für das einfache Kochen mit einem einzigen Ziel (Single-Objective Optimization). Aber wenn das Ziel komplizierter wird – wie etwa der Versuch, ein Gericht zu kreieren, das gleichzeitig sowohl extrem gesund als auch extrem lecker ist (Multi-Objective Optimization) – versagten die alten Werkzeuge. Sie konnten die komplexe Beziehung zwischen den beiden Zielen nicht erfassen.

Dieses Paper stellt ein neues, superstarkes Set an Werkzeugen namens MO-ELA (Multi-Objective Exploratory Landscape Analysis) vor, das dem Sous-Chef hilft, die Landschaft dieser komplexen Probleme klar zu sehen.

Das Problem: Navigieren durch eine neblige Gebirgskette

Stellen Sie sich ein Multi-Objective-Problem wie eine neblige Gebirgskette vor, in der Sie versuchen, den höchsten Gipfel (die beste Lösung) zu finden. Dabei haben Sie jedoch zwei gegensätzliche Ziele: Sie wollen so hoch wie möglich sein (ein Ziel maximieren) und gleichzeitig so nah wie möglich an einem bestimmten Tal sein (ein anderes Ziel minimieren).

In diesem Nebel sind einige Pfade glatt und leicht zu erklimmen, während andere aus zerklüfteten Klippen mit vielen Sackgassen bestehen. Die „alten“ Werkzeuge konnten nur eine Seite des Berges zur Zeit betrachten und übersahen dabei, dass sich das Gelände drastisch verändert, wenn man das Gesamtbild betrachtet.

Die Lösung: Ein neues Fernglas

Die Autoren haben ein neues Set an „Ferngläsern“ (Features) entwickelt, um vor dem Aufstieg eine schnelle Momentaufnahme der Gebirgskette zu machen. Anstatt nur nach der Höhe des Bodens zu schauen, untersuchen sie, wie die Punkte in zwei verschiedenen Welten zueinander in Beziehung stehen:

Der Entscheidungsraum (Decision Space): Wo die Wanderer stehen (die Inputs).
Der Zielraum (Objective Space): Wie hoch und wie nah am Tal die Wanderer sind (die Ergebnisse).

Sie haben fünf verschiedene Arten von Linsen gebaut, um diese Momentaufnahme zu analysieren:

Die „Schichttorten“-Linse (Non-Dominated Sorting): Stellen Sie sich vor, Sie sortieren die Wanderer in Schichten. Die oberste Schicht enthält die „Super-Wanderer“, die in mindestens einer Hinsicht besser sind als alle anderen. Diese Linse zählt, wie viele Schichten es gibt und wie die „Super-Wanderer“ verteilt sind. Wenn die Schichten flach und gleichmäßig sind, ist der Berg einfach zu bezwingen. Wenn sie zerklüftet und uneben sind, ist der Berg schwierig.
Die „Statistische Schnappschuss“-Linse: Diese führt lediglich einen schnellen mathematischen Check der obersten Schicht der Wanderer durch. Wie weit sind sie verstreut? Bewegen sie sich synchron? Es ist, als würde man prüfen, ob die Gruppe ein eng vernetztes Team oder eine verstreute Menge ist.
Die „Gestaltwandler“-Linse (PCA): Diese Linse staucht den 3D-Berg auf eine 2D-Karte zusammen, um die Hauptform zu erkennen. Sie fragt: „Ist der Berg ein langer Grat, eine runde Kuppel oder eine flache Ebene?“
Die „String-Art“-Linse (Graph Structures): Dies ist der kreativste Teil. Stellen Sie sich vor, Sie verbinden die Wanderer mit Fäden, um ein Netz zu bilden.
- Sie ziehen Fäden basierend darauf, wie nah die Wanderer im Entscheidungsraum (wo sie stehen) beieinander liegen.
- Dann dehnen sie genau dieselben Fäden auf den Zielraum (wo sie landen) aus.
- Die Magie: Wenn die Fäden straff und gerade bleiben, ist der Berg glatt. Wenn die Fäden sich verdrehen, verheddern oder verformen, bedeutet das, dass das Gelände täuschend und schwer zu navigieren ist. Es ist, als würde man prüfen, ob eine Karte mit der Realität des Geländes übereinstimmt.
Die „Hangneigungs“-Linse (Gradient): Diese misst, wie steil die Hügel sind. Sind die Hänge sanft oder gibt es plötzliche Klippen?

Das Experiment: Der große Geschmackstest

Um diese neuen Ferngläser zu testen, führten die Autoren ein massives Experiment durch. Sie nahmen 1.165 verschiedene „Gebirgsketten“ (Benchmark-Probleme) und ließen drei verschiedene Kletterteams (Algorithmen: NSGA-II, SMS-EMOA und MOEA/D) versuchen, diese zu bezwingen.

Sie fragten: „Können unsere neuen Ferngläser vorhersagen, welches Team auf welchem Berg gewinnen wird?“

Die Ergebnisse:

Der alte Weg: Ohne die neuen Werkzeuge war die Vorhersage zwar okay, aber oft falsch.
Der neue Weg: Mit den MO-ELA-Features wurde der „Sous-Chef“ unglaublich präzise und wählte bei den Problemen mit zwei Zielen fast jedes Mal das Gewinner-Team. Auch bei den Problemen mit drei Zielen war es eine enorme Verbesserung.
Das Beste daran: Das System benötigte nicht alle Ferngläser. Es brauchte nur eine kleine, spezifische Auswahl (etwa 32 von über 200 Features), um perfekt zu funktionieren. Dies beweist, dass die neuen Werkzeuge effizient sind und nicht bloß aus „Rauschen“ bestehen.

Warum das wichtig ist

Das Paper zeigt, dass man durch das Betrachten der Beziehung zwischen dem Startpunkt und dem Endpunkt – unter Verwendung dieser cleveren „String-Art“- und „Schichttorten“-Techniken – die Schwierigkeit eines Problems sehr schnell verstehen kann.

Die Autoren fanden heraus, dass diese Werkzeuge stabil sind (sie liefern auch dann das gleiche Ergebnis, wenn man eine etwas andere Momentaufnahme des Berges macht) und expressiv (sie erklären genau, was ein Problem schwierig macht).

Kurz gesagt: Dieses Paper liefert uns eine bessere Karte zur Navigation durch komplexe Multi-Objective-Probleme und stellt sicher, dass wir den richtigen Solver auswählen, noch bevor wir überhaupt mit dem Aufstieg beginnen.

Technisches Resümee: MO-ELA

Problemstellung

Die automatisierte Algorithmenselektion (Automated Algorithm Selection, AAS) ist ein ausgereiftes Feld für die eindimensionale (single-objective, SO) Optimierung, bei der maschinelle Lernmodelle das leistungsfähigste Algorithmus basierend auf „Exploratory Landscape Analysis“ (ELA)-Merkmalen für eine spezifische Probleminstanz vorhersagen. In der Domäne der kontinuierlichen Multi-Objective-Optimierung (MO) ist die Landschaft der verfügbaren Merkmale jedoch spärlich besetzt. Bestehende Ansätze verlassen sich oft darauf, SO-Merkmale für jedes Ziel einzeln zu berechnen, was jedoch die komplexen Interaktionen zwischen den Zielen nicht erfasst, oder auf eingeschränkte MO-Merkmale, die nicht direkt auf unbeschränkte (box-constrained) kontinuierliche Probleme anwendbar sind. Es besteht ein Bedarf an einem rigorosen, komplementären Satz von Merkmalen, die speziell darauf ausgelegt sind, die Landschaft von box-beschränkten kontinuierlichen Multi-Objective-Optimierungsproblemen (MOPs) zu charakterisieren, um die AAS-Leistung zu verbessern.

Methodik

Die Autoren schlagen MO-ELA vor, einen neuartigen Satz von 226 Merkmalen für bi-objektive und 233 Merkmale für tri-objektive Probleme. Diese Merkmale werden aus einer Zufallsstichprobe von Punkten sowohl im Entscheidungs- als auch im Ziellraum abgeleitet, wobei Dominanzbeziehungen und verschiedene Strukturanalysen genutzt werden. Die Merkmale sind in fünf distinkte Gruppen unterteilt:

Non-Dominated Sorting (NDS) basierte Merkmale:
- Verwendet das Verfahren des Non-Dominated Sortings (inspiriert durch NSGA-II), um die Stichprobe in Schichten ( $L_1, L_2, \dots$ ) zu partitionieren.
- Berechnet Metriken wie die Anzahl der nicht-dominierten Punkte, die Anzahl der Schichten und die durchschnittliche Anzahl an Punkten pro Schicht.
- Berechnet Hypervolumen (HV) und Solow-Polasky (SP) Maße für die ersten fünf Schichten.
- Passt Polynomregressionen (Grade 1–4) an die HV-Werte über die Schichten an, um die Nichtlinearität der Pareto-Front-Verteilung zu erfassen, wobei $R^2$ als Merkmal verwendet wird.
Deskriptive Statistiken der nicht-dominierten Punkte:
- Wendet statistische Maße (Min, Max, Mittelwert, Standardabweichung) auf die Zielvektoren der ersten nicht-dominierten Schicht ( $L_1$ ) an.
- Beinhaltet paarweise Spearman-Korrelationen zwischen den Zielen sowie die absolute Differenz der Standardabweichungen für bi-objektive Fälle.
PCA-basierte Merkmale:
- Führt eine Hauptkomponentenanalyse (Principal Component Analysis, PCA) auf drei Datensätzen durch: den Punkten im Entscheidungsraum ( $X$ ), den Punkten im Ziellraum ( $Y$ ) und dem konkatenierten Satz ($XY$) der nicht-dominierten Schicht.
- Extrahiert das Minimum, Maximum und den durchschnittlichen erklärten Varianzanteil aus den Hauptkomponenten dieser Sätze.
Graph-basierte Merkmale:
- Konstruiert Graphen basierend auf der nicht-dominierten Schicht $L_1$ sowohl im Entscheidungs- als auch im Ziellraum.
- MST- und kNN-Graphen: Erstellt Minimum Spanning Trees (MST) und k-Nearest Neighbor (kNN) Graphen ( $k=1$ ) im Entscheidungsraum ( $G_D$ ) und im Ziellraum ( $G_O$ ).
- Edge Transfer: Überträgt die Kantenstruktur eines Graphen auf den anderen (z. B. MST-Kanten aus dem Entscheidungsraum angewandt auf die Zielpunkte, bezeichnet als $G_{D \to O}$ ).
- Metriken: Berechnet Kantengewichte (Distanzen), Knotennähe-Zentralität (Closeness Centrality), Winkel zwischen verbundenen Knoten sowie Eigenschaften verbundener Komponenten (Anzahl der Komponenten, Knoten pro Komponente, längster Pfad).
- Beinhaltet Verhältnisse von Merkmalen zwischen den Graphen im Entscheidungs- und Ziellraum, um die Verzerrung zwischen den Räumen zu erfassen.
Gradienten-basierte Merkmale:
- Berechnet absolute pro Variable fallende Steigungen zwischen verbundenen Knoten im MST des Ziellraums ( $G^O_{ST}$ ).
- Aggregiert diese Steigungen über alle Ziele und Kanten hinweg zu einem Multi-Objective-Gradienten-Vektor, aus dem Min, Max, Standardabweichung und Mittelwert extrahiert werden.

Experimenteller Aufbau:

Benchmarks: Ein umfassender Satz von 1.165 Probleminstanzen, abgeleitet von BiObjBBOB, ZDT, DTLZ und MPM2, die 2 und 3 Ziele sowie Dimensionen $d \in \{2, 5, 10, 20\}$ abdecken.
Algorithmen: Drei Solver (NSGA-II, SMS-EMOA, MOEA/D) wurden jeweils 20 Mal pro Instanz ausgeführt.
AAS-Framework: Maschinelle Lernmodelle (SVM, XGBoost, Random Forest) wurden trainiert, um den besten Solver vorherzusagen. Die Merkmalsselektion wurde mittels einer Vorwärts-Rückwärts-Exhaustiv-Suche durchgeführt, um die einflussreichste Teilmenge zu identifizieren.
Metriken: Die Leistung wurde mittels des normalisierten Hypervolumens (HVN) und der relativen Verbesserung (Relative Improvement, RI) beim Schließen der Lücke zwischen dem Single Best Solver (SBS) und dem Virtual Best Solver (VBS) evaluiert.

Zentrale Ergebnisse

Leistung der Algorithmenselektion: Die vorgeschlagenen Merkmale verbesserten die AAS-Leistung signifikant. Für bi-objektive Probleme erreichte der beste Selektor (XGBoost mit Merkmalsselektion) eine RI von 0,963 und schloss damit praktisch die Lücke zum VBS. Für tri-objektive Probleme wurde eine RI von 0,272 erreicht.
Beitrag der Merkmale: Nach der Merkmalsselektion gehörten die neu vorgeschlagenen MO-ELA-Merkmale häufig zu den wichtigsten Beitragsleistenden.
- Für bi-objektive Probleme waren 14 der 32 selektierten Merkmale neu (dominiert von NDS-Merkmalen).
- Für tri-objektive Probleme waren 17 der 36 selektierten Merkmale neu (dominiert von kNN-Graph-Merkmalen).
Stabilität der Merkmale: Die Merkmale zeigten eine hohe Stabilität über verschiedene Zufallsstichproben und Stichprobengrößen hinweg, mit durchschnittlichen paarweisen Korrelationen von ~0,8 für alle Merkmale und nahezu 1,0 für die selektierte Teilmenge.
Expressivität der Merkmale: Die selektierten Merkmale zeigten eine geringe gegenseitige Korrelation (Durchschnitt ~0,30 für bi, ~0,23 für tri), was darauf hindeutet, dass sie unterschiedliche Aspekte der Problemlandschaft erfassen.
Sensitivität der Stichprobengröße: Eine Stichprobengröße von 500 lieferte die besten Ergebnisse für die Dimensionen 5, 10 und 20. Für Dimension 2 war eine Stichprobengröße von 200 optimal. Bemerkenswerterweise verbesserten größere Stichproben die Leistung selbst dann, wenn das verbleibende Budget für Solver-Läufe reduziert wurde, was darauf hindeutet, dass die Expressivität der Merkmale entscheidend ist.

Bedeutung und Ansprüche

Das Paper behauptet, dass MO-EDA eine rigorose Erweiterung der explorativen Landschaftsmerkmale für die kontinuierliche Multi-Objective-Optimierung darstellt. Die primäre Bedeutung liegt in:

Überbrückung der Lücke: Es adressiert die Knappheit an Merkmalen für MO-Probleme durch die Einführung eines umfassenden Satzes, der die Interaktionen zwischen Zielen und die Geometrie sowohl des Entscheidungs- als auch des Ziellraums erfasst.
Nachgewiesener Nutzen: Die Merkmale sind nicht bloß theoretisch; sie ermöglichen es maschinellen Lernmodellen empirisch, zwischen Probleminstanzen zu unterscheiden und Algorithmen mit nahezu optimaler Genauigkeit zu selektieren (nahezu Erreichen des VBS bei bi-objektiven Fällen).
Komplementarität: Die neuen Merkmale ergänzen bestehende MO-ELA-Merkmale (aus Liefooghe et al., 2021), da die Merkmalsselektion konsistent eine Mischung aus beiden beibehält, was darauf hindeutet, dass unterschiedliche Merkmalsgruppen verschiedene notwendige Eigenschaften der Landschaft erfassen.
Praktikabilität: Die Merkmale sind stabil und effektiv selbst bei relativ kleinen Stichprobengrößen (z. B. 200–500 Punkte), was sie für die praktische Anwendung mit begrenzten Rechenbudgets geeignet macht.

Die Autoren kommen zu dem Schluss, dass diese Forschung zwar noch in einem frühen Stadium ist, diese Merkmale jedoch aussagekräftige Einblicke in die Problemstruktur bieten und den Stand der Technik in der automatisierten Algorithmenselektion für die kontinuierliche Multi-Objective-Optimierung signifikant verbessern.