Evaluating Real-World Generalizability of Algorithm Selection Models

Sintesi Tecnica: Valutazione della Generalizzabilità nel Mondo Reale dei Modelli di Selezione degli Algoritmi

Definizione del Problema
La Selezione degli Algoritmi (AS) mira a identificare automaticamente l'algoritmo di ottimizzazione più adatto per una specifica istanza di problema, sfruttando caratteristiche misurabili del problema (caratteristiche del landscape) e dati storici sulle prestazioni. Sebbene i modelli di AS siano stati ampiamente sviluppati e valutati su suite di benchmark sintetici controllati (come BBOB e CEC), la loro capacità di generalizzare verso landscape di ottimizzazione del mondo reale rimane in gran parte non verificata. La letteratura esistente suggerisce che i benchmark sintetici spesso mancano della complessità strutturale, dei pattern di rumore e dei vincoli specifici del dominio inerenti ai problemi pratici. Di conseguenza, i modelli addestrati su dati sintetici possono soffrire di overfitting rispetto a specifiche distribuzioni di landscape e fallire quando applicati a compiti reali e specifici del dominio. Questo studio affronta il critico divario nella comprensione di quanto bene i modelli di AS possano trasferirsi tra benchmark sintetici accademici e set di problemi del mondo reale.

Metodologia
Lo studio impiega un framework di valutazione cross-benchmark sistematico che coinvolge quattro distinte fonti di problemi:

1. Benchmark Sintetici: La suite Black-Box Optimization Benchmarking (BBOB) e la serie di benchmark per parametri reali a obiettivo singolo IEEE CEC.
2. Benchmark del Mondo Reale: Un set di problemi di ottimizzazione delle traiettorie nella robotica (ROB) e problemi di pianificazione del percorso per veicoli aerei senza pilota (UAV).

L'assetto sperimentale include un portfolio di algoritmi composto da otto metodi di ottimizzazione a obiettivo singolo basati sulla popolazione (tra cui AGSK, DE, PSO, LSHADE e altri). Gli autori valutano le prestazioni attraverso le dimensioni 6, 12, 18, 24 e 30.

Estrazione delle Caratteristiche e Pre-elaborazione:
Lo studio utilizza caratteristiche di Exploratory Landscape Analysis (ELA) derivate dal pacchetto flacco (62 caratteristiche per istanza). Per investigare l'impatto della rappresentazione dei dati sulla generalizzazione, gli autori testano varie strategie di pre-elaborazione:

• Scaling: Nessuno, y-scaling (solo funzione obiettivo) e x-y-scaling (variabili decisionali e funzione obiettivo).
• Campionamento: Campione completo (10.000 punti) rispetto a campionamento ridotto (50d punti).

Modellazione e Valutazione:
Un regressore Random Forest (RF) viene addestrato per predire il punteggio di precisione normalizzato di ciascun algoritmo per una data istanza di problema. Le prestazioni dell'AS sono misurate tramite la differenza tra il punteggio del miglior algoritmo predetto e il punteggio del vero miglior algoritmo, confrontato con un baseline "dummy" che predice la prestazione media del miglior solver osservato nel set di addestramento. La valutazione segue un rigoroso protocolo cross-benchmark: i modelli sono addestrati su un benchmark e testati su tutti e quattro, nonché in un contesto di benchmark fusi. Inoltre, viene impiegato un test di crossmatch per quantificare la somiglianza statistica delle distribuzioni delle caratteristiche ELA tra coppie di benchmark.

Risultati Chiave

• Generalizzazione Limitata: Nella maggior parte degli scenari cross-benchmark, particolarmente nelle dimensioni inferiori (6d), i modelli di AS addestrati su benchmark sintetici (BBOB/CEC) non riescono a superare il baseline dummy quando testati su problemi del mondo reale (ROB/UAV), e viceversa.
• Effetti della Dimensionalità: Sebbene sia stata osservata una qualche sporadica generalizzazione positiva (ad esempio, da CEC a UAV senza scaling in 6d, o da CEC a UAV in 12d), la generalizzazione rimane inconsistente. Nelle dimensioni più elevate (24d, 30d), i miglioramenti rispetto al baseline sono modesti (0.1–0.2) e altamente dipendenti dalle coppie sorgente-target specifiche e dalle scelte di pre-elaborazione.
• Il Fenomeno dell'Overfitting del "Single-Best Solver": L'analisi delle frequenze di predizione ha rivelato una causa significativa della scarsa generalizzazione. Quando un benchmark di addestramento è dominato da un singolo algoritmo con le migliori prestazioni (ad esempio, EBOwithCMAR su BBOB o APGSK_IMODE su UAV), il modello di AS tende all'overfitting predendo costantemente lo stesso algoritmo. Questo comportamento imita efficacemente il baseline dummy, risultando in nessun guadagno misurabile nell'accuratezza della selezione.
• Disparità dello Spazio delle Caratteristiche: I test statistici di crossmatch hanno confermato che i benchmark sintetici e quelli del mondo reale occupano regioni largamente distinte dello spazio delle caratteristiche ELA. Mentre BBOB e CEC mostrano una sovrapposizione sostanziale, i benchmark che coinvolgono problemi di robotica e UAV esibiscono una somiglianza minima con i suite sintetici, specialmente nelle dimensioni più elevate. Le fasi di pre-elaborazione come lo scaling e il campionamento ridotto hanno aumentato la sovrapposizione dello spazio delle caratteristiche, ma non si sono tradotte costantemente in un miglioramento delle prestazioni dell'AS.

Significatività e Rivendicazioni
L'articolo sostiene che una forte prestazione sui benchmark sintetici standard non garantisce robustezza o trasferibilità ai problemi di ottimizzazione del mondo reale. Lo studio evidenzia come le differenze strutturali tra i landscape sintetici e quelli del mondo reale limitino fondamentalmente la generalizzazione cross-benchmark.

Gli autori concludono che gli approcci di AS attuali sono spesso insufficienti per l'implementazione pratica senza affrontare lo shift distributivo tra i domini di addestramento e di test. Suggeriscono che lo sviluppo futuro debba orientarsi verso:

1. L'arricchimento delle collezioni di benchmark con istanze di problemi reali e diversificate.
2. Lo sviluppo di rappresentazioni delle caratteristiche che catturino meglio le caratteristiche trasferibili dei problemi.
3. La progettazione di modelli di AS esplicitamente mirati alla generalizzazione cross-domain piuttosto che all'ottimizzazione per un benchmark specifico.

Il lavoro sottolinea la necessità di andare oltre gli ambienti sintetici controllati per valutare e sviluppare sistemi di AS capaci di gestire l'eterogeneità e la complessità dei compiti di ottimizzazione del mondo reale.