💻 computer science

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

Dit artikel introduceert MO-ELA, een nieuwe set exploratieve landschapskenmerken afgeleid van zowel de beslissings- als de objectieruimte over vijf verschillende categorieën, die de automatische algoritme-selectie voor continue multi-objective optimalisatie aanzienlijk verbetert door effectief de probleemcomplexiteit te vatten en het prestatievermogen van algoritmen te onderscheiden.

Oorspronkelijke auteurs: Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

Gepubliceerd 2026-02-03

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een chef-kok bent die moet beslissen welk recept je gaat koken voor een dinerfeestje. Je hebt een enorm kookboek met duizenden recepten (algoritmen), maar je weet dat geen enkel recept perfect werkt voor elk type ingrediënt (optimalisatieprobleem). Sommige gerechten vereisen een delicate behandeling, terwijl andere een stevige hand nodig hebben. Als je het fout raadt, is de maaltijd verpest.

Dit is het probleem van Automated Algorithm Selection (AAS). Het is alsof je een slimme sous-chef hebt die naar je ingrediënten kijkt en je direct vertelt: "Voor deze specifieke set ingrediënten gebruik je Recept A, en niet Recept B."

Lama tijd lang werkte deze "sous-chef" uitstekend voor eenvoudige, enkelvoudige doelen (Single-Objective Optimization). Maar wanneer het doel ingewikkelder wordt—zoals het proberen te maken van een gerecht dat zowel het gezondste als het lekkerste tegelijkertijd is (Multi-Objective Optimization)—faalden de oude hulpmiddelen. Ze konden de complexe relatie tussen de twee doelen niet zien.

Dit artikel introduceert een nieuwe, superkrachtige set hulpmiddelen genaamd MO-ELA (Multi-Objective Exploratory Landscape Analysis) om de sous-chef te helpen de landschappen van deze complexe problemen duidelijk te zien.

Het Probleem: Navigeren door een Mistige Bergketen

Beschouw een multi-objective probleem als een mistige bergketen waar je probeert de hoogste piek (de beste oplossing) te vinden. Echter, je hebt twee tegenstrijdige doelen: je wilt zo hoog mogelijk zijn (één doel maximaliseren) maar ook zo dicht mogelijk bij een specifieke vallei zijn (een ander doel minimaliseren).

In deze mist zijn sommige paden glad en gemakkelijk te beklimmen, terwijl andere paden bestaan uit grillige kliffen met veel doodlopende wegen. De "oude" hulpmiddelen konden slechts naar één kant van de berg tegelijk kijken, waardoor ze de realiteit misten dat het terrein drastisch verandert wanneer je het hele plaatje bekijkt.

De Oplossing: Een Nieuwe Set Verrekijkers

De auteurs hebben een nieuwe set "verrekijkers" (kenmerken) gemaakt om snel een snapshot te nemen van de bergketen voordat de klim begint. In plaats van alleen naar de hoogte van de grond te kijken, kijken ze naar hoe de punten zich tot elkaar verhouden in twee verschillende werelden:

De Beslissingsruimte (Decision Space): Waar de wandelaars staan (de inputs).
De Doelruimte (Objective Space): Hoe hoog en hoe dicht bij de vallei die wandelaars zijn (de resultaten).

Ze hebben vijf verschillende soorten lenzen gebouwd om deze snapshot te analyseren:

De "Gelaagde Taart" Lens (Non-Dominated Sorting): Stel je voor dat je de wandelaars in lagen sorteert. De bovenste laag bevat de "super-wandelaars" die op minstens één manier beter zijn dan de rest. Deze lens telt hoeveel lagen er zijn en hoe de "super-wandelaars" verdeeld zijn. Als de lagen vlak en gelijkmatig zijn, is de berg makkelijk. Als ze grillig en ongelijkmatig zijn, is de berg lastig.
De "Statistische Snapshot" Lens: Deze neemt simpelweg een snelle wiskundige controle van de bovenste laag wandelaars. Hoe verspreid zijn ze? Bewegen ze synchroon? Het is alsof je controleert of de groep een hecht team is of een verspreide menigte.
De "Vormveranderder" Lens (PCA): Deze lens drukt de 3D-berg plat tot een 2D-kaart om de hoofdvorm te zien. Het vraagt: "Is de berg een lange rug, een ronde koepel of een vlakke vlakte?"
De "Draadkunst" Lens (Graph Structures): Dit is het meest creatieve deel. Stel je voor dat je de wandelaars met draden verbindt om een web te vormen.
- Ze trekken draden op basis van hoe dicht wandelaars bij elkaar zijn in de Beslissingsruimte (waar ze staan).
- Vervolgens strekken ze die zelfde draden uit naar de Doelruimte (waar ze terechtkomen).
- De Magie: Als de draden strak en recht blijven, is de berg glad. Als de draden verdraaid, verstrikt of uit vorm getrokken raken, betekent dit dat het terrein misleidend en moeilijk te navigeren is. Het is alsof je ziet of een kaart overeenkomt met de realiteit van het terrein.
De "Helling" Lens (Gradient): Deze meet hoe steil de heuvels zijn. Zijn de hellingen mild, of zijn er plotselinge kliffen?

Het Experiment: De Grote Smaaktest

Om deze nieuwe verrekijkers te testen, voerden de auteurs een massaal experiment uit. Ze namen 1.165 verschillende "bergketens" (benchmarkproblemen) en lieten drie verschillende klimteams (algoritmen: NSGA-II, SMS-EMOA en MOEA/D) proberen deze te bedwingen.

Ze vroegen: "Kun onze nieuwe verrekijkers voorspellen welke ploeg zal winnen op welke berg?"

De Resultaten:

De Oude Manier: Zonder de nieuwe hulpmiddelen was de voorspelling oké, maar vaak fout.
De Nieuwe Manier: Met de MO-ELA kenmerken werd de "sous-chef" ongelooflijk nauwkeurig. Voor de problemen met twee doelen was het systeem bijna perfect en koos het bijna elke keer het winnende team. Voor de problemen met drie doelen was het ook een enorme verbetering.
Het Beste Deel: Het systeem had niet alle verrekijkers nodig. Het had slechts een kleine, specifieke subset van de kenmerken nodig (ongeveer 32 van de 200+) om perfect te werken. Dit bewijst dat de nieuwe hulpmiddelen efficiënt zijn en niet slechts "ruis".

Waarom Dit Belangrijk Is

Dit artikel laat zien dat door te kijken naar de relatie tussen waar je begint en waar je eindigt—met behulp van deze slimme "draadkunst" en "gelaagde taart" technieken—je de moeilijkheid van een probleem heel snel kunt begrijpen.

De auteurs ontdekten dat deze hulpmiddelen stabiel zijn (ze geven hetzelfde antwoord, zelfs als je een iets andere snapshot van de berg neemt) en expressief (ze vertellen je precies wat een probleem moeilijk maakt).

Kortom, dit artikel geeft ons een betere kaart voor het navigeren door complexe problemen met meerdere doelen, zodat we de juiste solver kunnen kiezen nog voordat we aan de klim beginnen.

Technische Samenvatting: MO-ELA

Probleemstelling

Geautomatiseerde Algoritmekeuze (AAS) is een volwassen veld voor enkelvoudige (SO) optimalisatie, waarbij machine learning-modellen het best presterende algoritme voorspellen voor een specifiek probleeminstantiënd op basis van "exploratieve landschapselementen" (ELA). Echter, in het domein van continue multi-objectieve (MO) optimalisatie is het landschap van beschikbare kenmerken echter schaars. Bestaande benaderingen vertrouwen vaak op het berekenen van SO-kenmerken voor elk objectief afzonderlijk, wat er niet in slaagt de complexe interacties tussen objectieven te vangen, of op beperkte MO-kenmerken die niet direct toepasbaar zijn op onbeperkte (box-constrained) continue problemen. Er is behoefte aan een rigoureuze, complementaire set kenmerken die specifiek zijn ontworpen om het landschap van box-constrained continue multi-objectieve optimalisatieproblemen (MOP's) te karakteriseren om de AAS-prestaties te verbeteren.

Methodologie

De auteurs stellen MO-ELA voor, een nieuwe set van 226 kenmerken voor bi-objectieve en 233 kenmerken voor tri-objectieve problemen. Deze kenmerken zijn afgeleid van een willekeurige steekproef van punten in zowel de beslissingsruimte als de objectieruimte, gebruikmakend van dominantieverhoudingen en diverse structurele analyses. De kenmerken zijn onderverdeeld in vijf afzonderlijke groepen:

Non-Dominated Sorting (NDS) Gebaseerde Kenmerken:
- Maakt gebruik van de non-dominated sorting procedure (geïnspireerd door NSGA-II) om de steekproef te partitioneren in lagen ( $L_1, L_2, \dots$ ).
- Berekent metrieken zoals het aantal niet-gedomineerde punten, het aantal lagen en het gemiddelde aantal punten per laag.
- Berekent Hypervolume (HV) en Solow-Polasky (SP) maten voor de eerste vijf lagen.
- Past polynoomregressies toe (graden 1–4) op de HV-waarden over de lagen om de niet-lineariteit van de Pareto-front distributie te vangen, waarbij $R^2$ als kenmerk wordt gebruikt.
Beschrijvende Statistieken van Niet-Gedomineerde Punten:
- Past statistische maten (min, max, gemiddelde, standaarddeviatie) toe op de objectieve vectoren van de eerste niet-gedomineerde laag ( $L_1$ ).
- Omvat paargewijze Spearman-correlaties tussen objectieven en het absolute verschil in standaarddeviaties voor bi-objectieve gevallen.
PCA-Gebaseerde Kenmerken:
- Voert Principal Component Analysis (PCA) uit op drie sets: de beslissingsruimte punten ( $X$ ), de objectieruimte punten ( $Y$ ), en de geconcateneerde set ($XY$) van de niet-gedomineerde laag.
- Extraheert de minimum, maximum en gemiddelde verklaarde variantie van de hoofdcomponenten van deze sets.
Graaf-Gebaseerde Kenmerken:
- Construeert grafen gebaseerd op de niet-gedomineerde laag $L_1$ in zowel de beslissings- als de objectieruimte.
- MST en kNN Grafen: Bouwt Minimum Spanning Trees (MST) en k-Nearest Neighbor (kNN) grafen ( $k=1$ ) in de beslissingsruimte ( $G_D$ ) en de objectieruimte ( $G_O$ ).
- Edge Transfer: Transfereert de randstructuur van de ene graaf naar de andere (bijv. MST-randen uit de beslissingsruimte toegepast op objectiepunten, aangeduid als $G_{D \to O}$ ).
- Metrieken: Berekent randgewichten (afstanden), node closeness centrality, hoeken tussen verbonden knopen, en eigenschappen van verbonden componenten (aantal componenten, knopen per component, langste pad).
- Omvat ratio's van kenmerken tussen de beslissings- en objectieruimte grafen om de distortie tussen de ruimtes te vangen.
Gradiënt-Gebaseerde Kenmerken:
- Berekent absolute per-variabele hellingen tussen verbonden knopen in de MST van de objectieruimte ( $G^O_{ST}$ ).
- Aggregeert deze hellingen over alle objectieven en randen om een multi-objectieve gradiëntvector te vormen, waaruit min, max, std en gemiddelde waarden worden geëxtraheerd.

Experimentele Opstelling:

Benchmarks: Een uitgebreide set van 1.165 probleeminstanties afgeleid van BiObjBBOB, ZDT, DTLZ en MPM2, dekkend voor 2 en 3 objectieven en dimensies $d \in \{2, 5, 10, 20\}$ .
Algoritmen: Drie solvers (NSGA-II, SMS-EMOA, MOEA/D) werden 20 keer per instantie gedraaid.
AAS Framework: Machine learning-modellen (SVM, XGBoost, Random Forest) werden getraind om de beste solver te voorspellen. Kenmerkselectie werd uitgevoerd met een forward-backward exhaustive search om de meest invloedrijke subset te identificeren.
Metrieken: Prestaties werden geëvalueerd met behulp van de Genormaliseerde Hypervolume (HVN) en de Relatieve Verbetering (RI) in het dichten van de kloof tussen de Single Best Solver (SBS) en de Virtual Best Solver (VBS).

Belangrijkste Resultaten

Algoritmekeuze Prestaties: De voorgestelde kenmerken verbeterden de AAS-prestaties aanzienlijk. Voor bi-objectieve problemen bereikte de beste selector (XGBoost met kenmerkselectie) een RI van 0,963, waarmee de kloof naar de VBS effectief werd gedicht. Voor tri-objectieve problemen werd een RI van 0,272 bereikt.
Kenmerkbijdrage: Na kenmerkselectie waren de nieuw voorgestelde MO-ELA kenmerken frequent onder de belangrijkste bijdragers.
- Voor bi-objectieve problemen waren 14 van de 32 geselecteerde kenmerken nieuw (gedomineerd door NDS-kenmerken).
- Voor tri-objectieve problemen waren 17 van de 36 geselecteerde kenmerken nieuw (gedomineerd door kNN graaf-kenmerken).
Kenmerkstabiliteit: De kenmerken vertoonden een hoge stabiliteit over verschillende willekeurige steekproeven en steekproefgroottes, met gemiddelde paargewijze correlaties van ~0,8 voor alle kenmerken en bijna 1,0 voor de geselecteerde subset.
Kenmerkexpressiviteit: De geselecteerde kenmerken vertoonden een lage wederzijdse correlatie (gemiddeld ~0,30 voor bi, ~0,23 voor tri), wat aangeeft dat ze verschillende aspecten van het landschap vangen.
Steekproefgrootte Gevoeligheid: Een steekproefgrootte van 500 leverde de beste resultaten voor dimensies 5, 10 en 20. Voor dimensie 2 was een steekproefgrootte van 200 optimaal. Opvallend genoeg verbeterden grotere steekproefgroottes de prestaties zelfs wanneer het resterende budget voor solver-runs werd verminderd, wat suggereert dat de expressiviteit van kenmerken cruciaal is.

Betekenis en Claims

Het artikel claimt dat MO-EDA een rigoureuze uitbreiding biedt van exploratieve landschapselementen voor continue multi-objectieve optimalisatie. De primaire betekenis ligt in:

Het overbruggen van de kloof: Het adresseert de schaarste aan kenmerken voor MO-problemen door een uitgebreide set te introduceren die de interacties tussen objectieven en de geometrie van zowel de beslissings- als de objectieruimte vastlegt.
Bewezen Nut: De kenmerken zijn niet louter theoretisch; ze stellen machine learning-modellen empirisch in staat om tussen probleeminstanties te onderscheiden en algoritmen te selecteren met bijna optimale nauwkeurigheid (benaderend de VBS voor bi-objectieve gevallen).
Complementariteit: De nieuwe kenmerken complementeren bestaande MO-ELA kenmerken (van Liefooghe et al., 2021), waarbij kenmerkselectie consistent een mix van beide behoudt, wat suggereert dat verschillende groepken verschillende noodzakelijke eigenschappen van het landschap vangen.
Practicaliteit: De kenmerken zijn stabiel en effectief, zelfs met relatief kleine steekproefgroottes (bijv. 200–500 punten), waardoor ze haalbaar zijn voor praktische toepassing waar computationele budgetten beperkt zijn.

De auteurs concluderen dat hoewel dit onderzoek zich nog in een vroege fase bevindt, deze kenmerken betekenisvolle inzichten bieden in de probleemstructuur en de state-of-the-art in geautomatiseerde algoritmekeuze voor continue multi-objectieve optimalisatie aanzienlijk verbeteren.