Sintesi Tecnica: MO-ELA

Definizione del Problema

La Selezione Automatica degli Algoritmi (AAS) è un campo maturo per l'ottimizzazione a obiettivo singolo (SO), dove modelli di apprendimento automatico prevedono l'algoritmo con le migliori prestazioni per una specifica istanza di problema basandosi su caratteristiche di "analisi del paesaggio esplorativo" (ELA). Tuttavia, nel dominio dell'ottimizzazione multi-obiettivo (MO) continua, il panorama delle caratteristiche disponibili è scarso. Gli approcci esistenti si affidano spesso al calcolo di caratteristiche SO per ogni singolo obiettivo individualmente, il che non riesce a catturare le complesse interazioni tra gli obiettivi, o su caratteristiche MO vincolate che non sono direttamente applicabili a problemi continui non vincolati (con vincoli di scatola). È necessario un insieme di caratteristiche rigorose e complementari, progettate specificamente per caratterizzare il paesaggio dei problemi di ottimizzazione multi-obiettivo continua con vincoli di scatola (MOP), al fine di migliorare le prestazioni della AAS.

Metodologia

Gli autori propongono MO-ELA, un nuovo insieme di 226 caratteristiche per problemi bi-obiettivo e 233 caratteristiche per problemi tri-obiettivo. Queste caratteristiche sono derivate da un campione casuale di punti sia nello spazio decisionale che in quello degli obiettivi, utilizzando relazioni di dominanza e varie analisi strutturali. Le caratteristiche sono suddivise in cinque gruppi distinti:

1. Caratteristiche basate sul Non-Dominated Sorting (NDS):

   • Utilizza la procedura di sorting non dominato (ispirata a NSGA-II) per partizionare il campione in strati ($L_1, L_2, \dots$).
   • Calcola metriche come il numero di punti non dominati, il numero di strati e la media dei punti per strato.
   • Calcola l'Ipervolume (HV) e le misure di Solow-Polasky (SP) per i primi cinque strati.
   • Applica regressioni polinomiali (gradi 1–4) ai valori di HV attraverso gli strati per catturare la non linearità della distribuzione della frontiera di Pareto, utilizzando $R^2$ come caratteristica.

2. Statistiche Descrittive dei Punti Non Dominati:

   • Applica misure statistiche (min, max, media, deviazione standard) ai vettori obiettivo del primo strato non dominato ($L_1$).
   • Include le correlazioni di Spearman a coppie tra gli obiettivi e la differenza assoluta nelle deviazioni standard per i casi bi-obiettivo.

3. Caratteristiche basate sulla PCA:

   • Esegue l'Analisi delle Componenti Principali (PCA) su tre insiemi: i punti dello spazio decisionale ($X$), i punti dello spazio obiettivo ($Y$) e l'insieme concatenato ($XY$) dello strato non dominato.
   • Estrae il minimo, il massimo e la varianza media spiegata dalle componenti principali di questi insiemi.

4. Caratteristiche basate su Grafi:

   • Costruisce grafi basati sullo strato non dominato $L_1$ sia nello spazio decisionale che in quello obiettivo.
   • Grafi MST e kNN: Costruisce grafi di Albero Spino Minimo (MST) e dei k-Vicini più prossimi (kNN) ($k=1$) nello spazio decisionale ($G_D$) e nello spazio obiettivo ($G_O$).
   • Trasferimento di Archi (Edge Transfer): Trasferisce la struttura degli archi di un grafo all'altro (ad esempio, gli archi MST dallo spazio decisionale applicati ai punti obiettivo, denotati come $G_{D \to O}$).
   • Metriche: Calcola i pesi degli archi (distanze), la centralità di vicinanza dei nodi (closeness centrality), gli angoli tra i nodi connessi e le proprietà delle componenti connesse (numero di componenti, nodi per componente, percorso più lungo).
   • Include i rapporti tra le caratteristiche tra i grafi dello spazio decisionale e dello spazio obiettivo per catturare la distorsione tra gli spazi.

5. Caratteristiche basate sul Gradiente:

   • Calcola le pendenze assolute per variabile tra i nodi connessi nell'MST dello spazio obiettivo ($G^O_{ST}$).
   • Aggrega queste pendenze attraverso tutti gli obiettivi e gli archi per formare un vettore di gradiente multi-obiettivo, dal quale vengono estratti i valori di min, max, deviazione standard e media.

Configurazione Sperimentale:

• Benchmark: Un set completo di 1.165 istanze di problemi derivate da BiObjBBOB, ZDT, DTLZ e MPM2, coprendo 2 e 3 obiettivi e dimensioni $d \in \{2, 5, 10, 20\}$.
• Algoritmi: Tre solver (NSGA-II, SMS-EMOA, MOEA/D) sono stati eseguiti 20 volte per istanza.
• Framework AAS: Modelli di machine learning (SVM, XGBoost, Random Forest) sono stati addestrati per prevedere il miglior solver. La selezione delle caratteristiche è stata eseguita tramite una ricerca esaustiva forward-backward per identificare il sottoinsieme più influente.
• Metriche: Le prestazioni sono state valutate utilizzando l'Ipervolume Normalizzato (HVN) e il Miglioramento Relativo (RI) nella chiusura del divario tra il Singolo Miglior Solver (SBS) e il Virtual Best Solver (VBS).

Risultati Chiave

• Prestazioni della Selezione dell'Algoritmo: Le caratteristiche proposte hanno migliorato significativamente le prestazioni della AAS. Per i problemi bi-obiettivo, il miglior selettore (XGBoost con selezione delle caratteristiche) ha ottenuto un RI di 0,963, chiudendo efficacementmente il divario con il VBS. Per i problemi tri-obiettivo, è stato ottenuto un RI di 0,272.
• Contributo delle Caratteristiche: Dopo la selezione delle caratteristiche, le nuove caratteristiche MO-ELA proposte erano frequentemente tra i principali contributori.
  • Per i problemi bi-obiettivo, 14 delle 32 caratteristiche selezionate erano nuove (dominate dalle caratteristiche NDS).
  • Per i problemi tri-obiettivo, 17 delle 36 caratteristiche selezionate erano nuove (dominate dalle caratteristiche del grafo kNN).
• Stabilità delle Caratteristiche: Le caratteristiche hanno dimostrato un'elevata stabilità attraverso diversi campioni casuali e dimensioni del campione, con correlazioni di coppia medie di ~0,8 per tutte le caratteristiche e quasi 1,0 per il sottoinsieme selezionato.
• Espressività delle Caratteristiche: Le caratteristiche selezionate hanno mostrato una bassa correlazione mutua (media ~0,30 per bi, ~0,23 per tri), indicando che catturano aspetti distinti del paesaggio del problema.
• Sensibilità alla Dimensione del Campione: Una dimensione del campione di 500 ha prodotto i risultati migliori per le dimensioni 5, 10 e 20. Per la dimensione 2, una dimensione del campione di 200 è stata ottimale. In particolare, campioni più grandi hanno migliorato le prestazioni anche quando il budget rimanente per le esecuzioni del solver era ridotto, suggerendo che l'espressività delle caratteristiche è critica.

Significato e Rivendicazioni

Il documento afferma che MO-EDA fornisce un'espansione rigorosa delle caratteristiche del paesaggio esplorativo per l'ottimizzazione multi-obiettivo continua. Il suo significato primario risiede in:

1. Colmare il Divario: Affronta la scarsità di caratteristiche per i problemi MO introducendo un insieme completo che cattura le interazioni tra gli obiettivi e la geometria sia dello spazio decisionale che di quello obiettivo.
2. Utilità Dimostrata: Le caratteristiche non sono meramente teoriche; esse permettono empiricamente ai modelli di machine learning di distinguere tra istanze di problemi e selezionare algoritmi con un'accuratezza quasi ottimale (avvicinandosi al VBS per i casi bi-obiettivo).
3. Complementarità: Le nuove caratteristiche completano le caratteristiche MO-ELA esistenti (da Liefooghe et al., 2021), poiché la selezione delle caratteristiche mantiene costantemente un mix di entrambe, suggerendo che diversi gruppi di caratteristiche catturano diverse proprietà necessarie del paesaggio.
4. Praticità: Le caratteristiche sono stabili ed efficaci anche con dimensioni di campionamento relativamente piccole (ad esempio, 200–500 punti), rendendole fattibili per applicazioni pratiche dove i budget computazionali sono limitati.

Gli autori concludono che, sebbene la ricerca sia nelle fasi iniziali, queste caratteristiche forniscono intuizioni significative sulla struttura del problema e migliorano significativamente lo stato dell'arte della selezione automatica degli algoritmi per l'ottimizzazione multi-obiettivo continua.