On the Structural (Dis)Agreement of Landscape Representations in Black-Box Optimization

Technische Samenvatting: Structurele (Dis)Agreement van Landschapsrepresentaties in Black-Box Optimalisatie

Probleemstelling
Automatische Algoritme Selectie (AAS) voor black-box optimalisatie is sterk afhankelijk van landschapskenmerkrepresentaties om probleeminstanties af te beelden op algoritmeprestaties. Hoewel er diverse representaties bestaan – variërend van traditionele Exploratory Landscape Analysis (ELA) kenmerken tot op deep learning gebaseerde embeddings (bijv. DoE2Vec, DeepELA, TransOptAS) – is er beperkt inzicht in hoe deze verschillende representaties hetzij overeenkomen hetzij uiteenlopen met betrekking tot de structurele organisatie van probleemruimten. Het huidige onderzoek staat voor twee hoofduitdagingen: een gebrek aan voldoende diverse benchmarkdatasets om generalisatie te testen, en de onzekerheid of bestaande representaties complementaire of redundante informatie over onderliggende landschapseigenschappen vastleggen. Specifiek blijft het onduidelijk of verschillende representaties dezelfde set problemen op consistente manieren ordenen of of ze onderscheidende geometrische versus semantische eigenschappen benadrukken.

Methodologie
De auteurs stellen een systematische, onbewaakte evaluatiepijplijn voor om de structurele consistentie en complementariteit van vier state-of-the-art landschapsrepresentaties te analyseren:

1. ELA: Traditionele laag-niveau statistische kenmerken (62 kenmerken per instantie).
2. DoE2Vec: Een variational autoencoder die 32-dimensionale latente vectoren produceert.
3. TransOptAS: Een op transformer gebaseerde encoder die 50-dimensionale embeddings produceert, getraind om algoritmeprestaties te voorspellen.
4. DeepELA: Een self-supervised transformer die 48-dimensionale kenmerken produceert die invariant zijn voor functietransformaties.

Datageneratie:
Om diversiteit te waarborgen buiten standaard benchmarks om, maakt de studie gebruik van de MA-BBOB-suite. Deze dataset bestaat uit 8.280 getransformeerde probleeminstanties die zijn gegenereerd via affiene combinaties van 552 paren van verschillende BBOB-probleemklassen. Elke combinatie wordt geëvalueerd met behulp van een Latin Hypercube Sample van grootte $50d$ met dimensie $d=10$.

Experimentele Procedure:

1. Clustering: Voor elke representatie voerden de auteurs een uitgebreide grid search uit over vijf clustering-algoritmen (Agglomeratief, K-Means, Spectraal, Gaussische Mengverdeling, BIRCH) en hyperparameters (aantal clusters $k \in [5, 500]$). De optimale configuratie voor elke representatie werd geselecteerd op basis van de Silhouette Score.
2. Analyse binnen Representatie: De auteurs construeerden dekkingmatrijzen om bij te houden hoe probleeminstanties zich over clusters verdelen. Ze evalueerden deze structuren met Homogeniteit (H), Completie (C) en V-maat (V) om te beoordelen hoe goed de clusters overeenkomen met de ground-truth probleemklassen.
3. Analyse over Representaties: Om representaties te vergelijken, leidden de auteurs vector-gebaseerde beschrijvingen van clusters af (waarbij elke vectorinvoer de frequentie van een specifiek probleem in een cluster vertegenwoordigt) en berekenden ze de cosinusgelijkheid tussen clusters van verschillende representaties. Hiërarchische clustering werd toegepast op deze gelijkheidsscores om structurele uitlijningen te identificeren.
4. Prestatie-uitlijning: Tot slot analyseerde de studie de relatie tussen kenmerkruimte-clusters en algoritmeprestaties. Met behulp van portefeuilles van Differential Evolution (DE) en Particle Swarm Optimization (PSO) varianten, maten de auteurs hoe consistent de best presterende algoritmeconfiguratie werd geselecteerd binnen de clusters die door elke representatie werden gedefinieerd.

Belangrijkste Resultaten
De studie onthult dat geen enkele representatie domineert; eerder ordent elke representatie de probleemruimte op een fundamenteel verschillende manier, waarbij complementaire aspecten van het landschap worden vastgelegd:

• Geometrische Cohesie (ELA & TransOptAS): Deze representaties vormen compacte, goed gescheiden geometrische structuren. ELA behaalde de hoogste Silhouette-score (0,3505), gevolgd door TransOptAS (0,2670). Beide vertoonden echter een lage homogeniteit, wat betekent dat hoewel de clusters geometrisch strak zijn, ze vaak gemengde probleemtypen bevatten.
• Semantische Fideliteit versus Fragmentatie (DoE2Vec): DoE2Vec behaalde de hoogste homogeniteit (0,5612) en V-maat (0,5882), wat wijst op een sterke uitlijning met de ware probleemsemantiek. Het produceerde echter een sterk gefragmenteerd landschap met een groot aantal clusters (355) en de laagste Silhouette-score (0,1722), wat suggereert dat er sprake is van over-segmentatie van de kenmerkruimte.
• Gebalanceerd Beeld (DeepELA): DeepELA bood een intermediair beeld, waarbij het geometrische scheiding en semantische consistentie in evenwicht bracht, hoewel het een matige gelijkenis vertoonde met andere representaties.
• Structurele Disagreement: Warmtekaarten van cross-representatie gelijkenis toonden aan dat hoewel TransOptAS nauw aansluit bij ELA, DoE2Vec aanzienlijk afwijkt vanwege zijn fijnmazige clustering. De vier representaties ordenen dezelfde problemen op opvallend verschillende manieren.
• Prestatie Trade-off: Bij analyse van algoritmeprestaties (DE en PSO) ontstond een trade-off. DoE2Vec toonde de hoogste homogeniteit in prestatieselectie (problemen in dezelfde cluster delen vaak het beste algoritme), maar een lage completie (soortgelijke algoritmen werden over verschillende clusters geselecteerd). Omgekeerd vertoonde TransOptAS een hoge completie (het groeperen van vergelijkbare prestatieproblemen samen), maar een lagere zuiverheid. Geen enkele representatie ving het algoritme-prestatiegedrag volledig op.

Betekenis en Bijdragen
De primaire bijdrage van het artikel is de demonstratie dat landschapsrepresentaties niet uitwisselbaar zijn; ze leggen verschillende structurele visies op dezelfde probleemruimte op.

• Complementariteit: De bevindingen benadrukken dat ELA/TransOptAS de voorkeur geven aan geometrische cohesie, terwijl DoE2Vec prioriteit geeft aan semantische zuiverheid. Dit suggereert dat multi-view analyses essentieel zijn voor het bouwen van robuuste meta-leer systemen, omdat het vertrouwen op een enkele representatie cruciale aspecten van het probleemlandschap kan missen.
• Richting voor Selectie: De resultaten bieden richtlijnen voor downstream taken: als het doel is om problemen met vergelijkbaar algoritmisch gedrag te groeperen, kunnen representaties met hoge completie (zoals TransOptAS) de voorkeur hebben, terwijl die met hoge homogeniteit (zoals DoE2Vec) beter in staat zijn specifieke probleemtypen te isoleren.
• Beperkingen: De auteurs merken op dat het onderzoek beperkt is tot een enkele benchmark-suite (MA-BBOB) en specifieke algoritme-families (DE en PSO). Het voorgestelde empirische kader is echter ontworpen om uitbreidbaar te zijn naar andere benchmarks en optimalisatiedomeinen.

Concluderend pleit de studie tegen het bestaan van een "universele" landschapsrepresentatie. In plaats daarvan bepleit ze de integratie van meerdere representaties om hun complementaire sterktes te benutten in geautomatiseerde algoritme selectie en meta-leer.