Evaluating Real-World Generalizability of Algorithm Selection Models

Technische Samenvatting: Evaluatie van de Real-World Generaliseerbaarheid van Algoritme-selectiemodellen

Probleemstelling
Algoritme-selectie (AS) beoogt automatisch de meest geschikte optimalisatiealgoritme te identificeren voor een specifieke probleeminstantie door gebruik te maken van meetbare probleemkenmerken (landschapskenmerken) en historische prestatiegegevens. Hoewel AS-modellen uitgebreid zijn ontwikkeld en geëvalueerd op gecontroleerde synthetische benchmark-suites (zoals BBOB en CEC), blijft hun vermogen om te generaliseren naar real-world optimalisatie-landschappen grotendeels onverifieerd. Bestaande literatuur suggereert dat synthetische benchmarks vaak een gebrek hebben aan de structurele complexiteit, ruispatronen en domeinspecifieke beperkingen die inherent zijn aan praktische problemen. Gevolgelijk kunnen modellen die getraind zijn op synthetische data overfitten op specifieke landschapverdelingen en falen wanneer ze worden toegepast op realistische, domeinspecifieke taken. Deze studie adresseert de kritieke kloof in het begrip van hoe goed AS-modellen kunnen transfereren tussen synthetische academische benchmarks en real-world probleemsets.

Methodologie
De studie hanteert een systematisch cross-benchmark evaluatiekader bestaande uit vier verschillende probleembronnen:

1. Synthetische Benchmarks: De Black-Box Optimization Benchmarking (BBOB) suite en de IEEE CEC real-parameter single-objective benchmark serie.
2. Real-World Benchmarks: Een set robotica trajectoptimalisatieproblemen (ROB) en Unmanned Aerial Vehicle (UAV) padplanningsproblemen.

De experimentele opzet omvat een algoritme-portfolio van acht populatiegebaseerde single-objective optimalisatiemethoden (waaronder AGSK, DE, PSO, LSHADE, en anderen). De auteurs evalueren de prestaties over dimensies 6, 12, 18, 24 en 30.

Feature Extractie en Preprocessing:
De studie maakt gebruik van Exploratory Landscape Analysis (ELA) features afgeleid van de flacco package (62 features per instantie). Om de impact van datarepresentatie op generalisatie te onderzoeken, testen de auteurs verschillende preprocessing strategieën:

• Scaling: Geen, y-scaling (alleen de objectieve functie) en x-y-scaling (beslissingsvariabelen en de objectieve functie).
• Sampling: Volledige sample (10.000 punten) versus gedownsampled (50d punten).

Modellering en Evaluatie:
Een Random Forest (RF) regressor wordt getraind om de genormaliseerde precisiescore van elk algoritme voor een gegeven probleeminstantie te voorspellen. De AS-prestaties worden gemeten aan de hand van het verschil tussen de voorspelde beste algoritme-score en de werkelijke beste algoritme-score, vergeleken met een "dummy" baseline die de gemiddelde prestatie van de beste solver in de trainingsset voorspelt. De evaluatie volgt een strikt cross-benchmark protocol: modellen worden getraind op één benchmark en getest op alle vier, evenals in een samengevoegde benchmark-setting. Daarnaast wordt een crossmatch-test gehanteerd om de statistische gelijkenis van de ELA-featureverdelingen tussen benchmark-paren te kwantificeren.

Belangrijkste Resultaten

• Beperkte Generalisatie: In de meeste cross-benchmark scenario's, met name in lagere dimensies (6d), falen AS-modellen getraind op synthetische benchmarks (BBOB/CEC) om de dummy baseline te overtreffen wanneer ze worden getest op real-world problemen (ROB/UAV), en vice versa.
• Dimensionaliteitseffecten: Hoewel er enige sporadische positieve transfer werd waargenomen (bijv. CEC naar UAV zonder scaling in 6d, of CEC naar UAV in 12d), bleef de generalisatie inconsistent. In hogere dimensies (24d, 30d) waren de verbeteringen ten opzichte van de baseline bescheiden (0.1–0.2) en sterk afhankelijk van specifieke bron-doel paren en preprocessing keuzes.
• Het "Single-Best Solver" Overfitting Fenomeen: De analyse van voorspellingsfrequenties onthulde een significante oorzaak voor slechte generalisatie. Wanneer een trainings-benchmark wordt gedomineerd door een enkel best presterend algoritme (bijv. EBOwithCMAR op BBOB of APGSK_IMODE op UAV), heeft het AS-model de neiging tot overfitting door consequent datzelfde algoritme te voorspellen. Dit gedrag bootst effectief de dummy baseline na, wat resulteert in geen meetbare winst in selectienauwkeurigheid.
• Feature Ruimte Dispariteit: De crossmatch teststatistieken bevestigden dat synthetische en real-world benchmarks grotendeels verschillende regio's in de ELA-feature ruimte bezetten. Hoewel BBOB en CEC substantiële overlap vertoonden, vertoonden benchmarks met robotica en UAV problemen minimale gelijkenis met synthetische suites, vooral in hogere dimensies. Preprocessing stappen zoals scaling en downsampling vergrootten de overlap in de feature-ruimte, maar vertaalden zich niet consistent naar verbeterde AS-prestaties.

Betekenis en Claims
Het paper claimt dat sterke prestaties op standaard synthetische benchmarks geen garantie bieden voor robuustheid of transfereerbaarheid naar real-world optimalisatieproblemen. De studie benadrukt dat de structurele verschillen tussen synthetische en real-world landschappen de cross-benchmark generalisatie fundamenteel beperken.

De auteurs concluderen dat huidige AS-benaderingen vaak ontoereikend zijn voor praktische implementatie zonder de distributieve verschuiving tussen trainings- en doelgebieden aan te pakken. Zij suggereren dat toekomstige ontwikkeling zich moet richten op:

1. Het verrijken van benchmark-collecties met diverse, realistische probleeminstanties.
2. Het ontwikkelen van feature-representaties die beter in staat zijn om transfereerbare probleemkenmerken te vatten.
3. Het ontwerpen van AS-modellen die expliciet gericht zijn op cross-domein generalisatie in plaats van het optimaliseren voor specifieke benchmark-prestaties.

Het werk onderstreept de noodzaak om verder te gaan dan gecontroleerde synthetische settings om AS-systemen te evalueren en te ontwikkelen die in staat zijn om de heterogeniteit en complexiteit van real-world optimalisatietaken aan te kunnen.