Beyond Numerical Features: CNN-Driven Algorithm Selection via Contour Plots for Continuous Black-Box Optimization

Riepilogo Tecnico: Selezione di Algoritmi Guidata da CNN tramite Grafici di Livello

Enunciato del Problema
L'ottimizzazione a scatola nera continua (BBO) consiste nel minimizzare o massimizzare funzioni obiettivo per le quali non sono disponibili informazioni sul gradiente, affidandosi esclusivamente alle valutazioni della funzione. Sebbene i risolutori privi di derivata (ad esempio, varianti di CMA-ES) funzionino bene, il teorema del "No Free Lunch" stabilisce che nessun singolo algoritmo supera universalmente gli altri su tutte le istanze del problema. Di conseguenza, la Selezione Automatica di Algoritmi (AAS) mira a scegliere il risolutore più adatto da un portafoglio fisso per una specifica istanza del problema.

Gli approcci AAS esistenti nell'ambito della BBO continua si basano prevalentemente sull'Analisi Esplorativa del Paesaggio (ELA), che costruisce vettori di caratteristiche numeriche (ad esempio, curvatura, separabilità) a partire da valutazioni esplorate, o sulla Deep-ELA, che utilizza embedding appresi da trasformatori pre-addestrati. Gli autori sostengono che questi descrittori numerici potrebbero non riuscire a catturare la struttura spaziale evidente nei paesaggi visualizzati. Sebbene l'AAS basata su CNN sia stata esplorata in domini discreti con codifiche dirette delle istanze, la sua applicazione alla BBO continua, dove le rappresentazioni devono essere costruite tramite esplorazione, è poco indagata.

Metodologia
Il documento propone un approccio AAS guidato dalla rappresentazione che tratta i paesaggi esplorati come immagini anziché come vettori numerici.

1. Rappresentazione dell'Istanzia (Grafici di Livello):

   • Singolo Obiettivo (SOO): Ogni istanza del problema viene resa come una mappa di contorno in scala di grigi 2D valutando la funzione obiettivo su una griglia fissa $300 \times 300$. Per dimensioni $d > 2$, viene creato un taglio 2D selezionando casualmente due coordinate per delimitare un sottospazio, fissando le altre a zero (sfruttando il dominio simmetrico di BBOB).
   • Multi-Obiettivo (MOO): Per problemi bi-obiettivo ($d=2, m=2$), viene utilizzata una strategia di campionamento di sottografici. Cinque finestre rettangolari allineate agli assi vengono campionate all'interno del dominio per ciascun obiettivo, generando molteplici visualizzazioni per ridurre la dipendenza da un'unica resa globale.
   • Varianti di Input: Per studiare la fedeltà dell'input, i grafici vengono ridimensionati a risoluzioni $r \in \{64, 128, 300\}$.

2. Architetture CNN:
   Vengono proposti due varianti di modello per prevedere le prestazioni relative (Tempo di Esecuzione Atteso per SOO, ipervolume relativo per MOO) degli algoritmi in un portafoglio:

   • Modello Combinato: Le cinque visualizzazioni specifiche dell'istanza (o campioni di finestra) vengono impilate lungo la dimensione dei canali e inviate direttamente a un encoder CNN.
   • Modello Separato: Ogni visualizzazione viene elaborata individualmente da un encoder con pesi condivisi, e i vettori di caratteristiche risultanti vengono concatenati prima di essere passati a un capo di regressione.
   • Architettura SOO: Un encoder CNN a tre livelli.
   • Architettura MOO: Un encoder ResNet-18 a causa delle maggiori esigenze rappresentative.

3. Meccanismo di Selezione:
   Il modello prevede la metrica di prestazione (ad esempio, ERT relativo) per ciascun algoritmo nel portafoglio. Viene selezionato il risolutore con il valore previsto migliore (ERT minimo o HV massimo).

Contributi Chiave

1. Rappresentazione Immagine Basata sull'Esplorazione: Gli autori introducono una nuova formulazione AAS per la BBO continua che utilizza le renderizzazioni di mappe di contorno dei paesaggi esplorati come rappresentazioni delle istanze, eliminando la necessità di caratteristiche ELA create manualmente.
2. Valutazione Empirica: Lo studio fornisce un'analisi completa sui benchmark standard BBOB 2009 a singolo obiettivo e su un setting bi-obiettivo seguendo il protocollo Deep-ELA. Analizza gli effetti dell'aggregazione delle visualizzazioni (Combinato vs Separato) e della risoluzione di input.
3. Benchmark delle Prestazioni: Il lavoro posiziona la selezione basata su contorni rispetto a baseline consolidate basate su caratteristiche (ELA con MLP/RF e varianti Deep-ELA).

Risultati Sperimentali

• Ottimizzazione a Singolo Obiettivo (SOO):
  • Sul benchmark BBOB 2009 (96 configurazioni), la CNN Combinata con risoluzione di input $300 \times 300$ ha superato significativamente il Miglior Risolutore Singolo (SBS), riducendo l'ERT relativo medio da 30.37 (SBS) a 5.60.
  • L'approccio CNN è stato competitivo con le baseline basate su caratteristiche più forti (ELA-MLP: 5.72; Deep-ELA Medium-kNN: 6.04).
  • Le prestazioni sono generalmente migliorate con risoluzioni di input più elevate ($r=300$), sebbene ciò abbia aumentato i costi di addestramento.
  • Il metodo ha mostrato guadagni significativi sui gruppi di funzioni F1–F19, mentre le prestazioni sul gruppo più difficile (F20–F24) sono rimaste miste rispetto ai metodi basati su caratteristiche.
• Ottimizzazione Multi-Obiettivo (MOO):
  • Nel setting di valutazione Deep-ELA, i selettori basati su CNN sono stati competitivi con le baseline Deep-ELA.
  • La CNN Separata ha ottenuto i migliori punteggi medi di HV relativo (0.971–0.974), superando le varianti Deep-ELA (0.904).
  • Il metodo è stato particolarmente efficace sulle istanze ZDT (raggiungendo punteggi quasi perfetti), mentre i risultati su DTLZ e MMF sono stati solidi ma leggermente inferiori alle migliori impostazioni Deep-ELA.

Significato e Affermazioni
Il documento afferma che semplici modelli visivi possono sfruttare la struttura spaziale dei paesaggi esplorati per la selezione degli algoritmi senza fare affidamento su caratteristiche ELA create manualmente. I risultati suggeriscono che le visualizzazioni dei grafici di livello contengono segnali sufficienti per guidare un'AAS efficace nella BBO continua, offrendo una rappresentazione complementare ai descrittori numerici.

Limitazioni e Ambito
Gli autori notano esplicitamente diverse limitazioni:

• Budget di Esplorazione: L'approccio attuale richiede un budget di esplorazione sostanziale (cinque mappe $300 \times 300$ per configurazione), rendendolo adatto all'analisi offline ma non al dispiegamento online con budget rigorosamente bassi.
• Rappresentazione ad Alta Dimensionalità: Per $d > 2$, la rappresentazione a taglio 2D è una vista parziale del paesaggio, il che potrebbe contribuire a prestazioni più deboli sui gruppi di funzioni più difficili.
• Protocolli Fissi: La valutazione è vincolata a portafogli e protocolli specifici (incluso il campionamento a finestre per MOO), e lo studio MOO è limitato a $d=2, m=2$.

Il lavoro è presentato come una prova di concetto che dimostra la fattibilità delle rappresentazioni basate su immagini, con direzioni future che puntano verso esplorazione sensibile ai costi, design multi-visualizzazione e caratteristiche ibride visive-numeriche.