S-CARD-CMSA: A Score-Aware Candidate Archive with Density-Filtered Reporting for Multimodal Optimization

Sintesi Tecnica: S-CARD-CMSA

Problema
L'ottimizzazione multimodale (MMO) mira a individuare molteplici ottimi distinti, globali o quasi-globali, in un singolo ciclo algoritmico. Sebbene la competizione IEEE CEC 2026 sul Benchmarking dei Metodi di Niching fornisca un rigoroso framework di valutazione, essa introduce una specifica sfida di punteggio: il punteggio finale non è determinato solo dalla copertura dei picchi, ma combina il Robust Peak Ratio (RPR), che misura la frazione di minimizzatori globali trovati, con un F1-score che penalizza pesantemente la bassa precisione. La precisione è inversamente correlata al numero di soluzioni riportate; pertanto, riportare troppi candidati ridondanti o di bassa qualità può degradare significativamente il punteggio finale, anche se l'algoritmo scopre con successo molti ottimi. La sfida principale consiste nel bilanciare un'alta copertura (RPR) con un controllo rigoroso sul numero di soluzioni riportate per massimizzare l'F1-score.

Metodologia: S-CARD-CMSA
Il documento propone S-CARD-CMSA (Score-Aware Candidate Archive with Density-Filtered Reporting), un'estensione conservativa dell'algoritmo RS-CMSA-ESII (Repelling Subpopulations Covariance Matrix Self-Adaptation Evolution Strategy II). Il metodo aderisce a un principio di progettazione rigoroso: preserva la dinamica di ricerca centrale, il campionamento, l'adattamento della covarianza, gli aggiornamenti delle regioni tabù e i meccanismi di restart dell'ottimizzatore base RS-CMSA-ESII. Le modifiche sono limitate interamente alle fasi di ritenzione dei candidati e di reporting finale.

Il framework introduce due componenti primarie:

1. Archivio Passivo di Candidati Secondari:
   Nella versione standard di RS-CMSA-ESII, l'insieme finale di soluzioni deriva esclusivamente dall'archivio primario. Tuttavia, candidati utili trovati durante un restart (specificamente la migliore soluzione del restart, $x^r_{best}$) possono essere rifiutati dai rigorosi controlli di novità o di verifica del bacino dell'archivio primario. S-CARD-CMSA mantiene un archivio secondario passivo ($C$) che registra il miglior candidato ($x^r_{best}$) di ogni restart senza influenzare la traiettoria di ricerca. Ciò assicura che candidati promettenti visitati durante la ricerca non vadano perduti, anche se non sono stati accettati nell'archivio primario.

2. Reporting a Densità Filtrata Sensibile al Punteggio (Score-Aware Density-Filtered Reporting):
   L'insieme finale di soluzioni è costruito dall'unione dell'archivio primario ($A$) e dell'archivio secondario filtrato ($C_f$). Viene applicata una regola di reporting in quattro fasi:

   • Filtraggio del Valore Obiettivo: I candidati secondari con valori obiettivi significativamente peggiori del minimo globale trovato nel pool vengono scartati utilizzando una finestra di tolleranza fissa ($\Delta f$).
   • Preservazione dell'Archivio Primario: I candidati dell'archivio primario hanno la priorità e vengono inseriti nell'insieme finale, a condizione che siano validi e non duplicati esatti.
   • Calcolo della Distanza Normalizzata: La somiglianza tra i candidati è misurata utilizzando la distanza euclidea normalizzata per tenere conto della scalabilità variabile.
   • Inserimento con Filtro di Densità: I candidati secondari sono considerati in ordine crescente di valore obiettivo. Un candidato viene inserito solo se la sua distanza dal candidato già riportato più vicino supera una soglia di densità ($\tau_\rho$). La soglia è scalata dimensionalmente come $\tau_\rho(D) = \alpha_\rho \sqrt{D}$. Se un candidato è troppo vicino a un report esistente, viene mantenuto quello con il valore obiettivo superiore. Questo passaggio mira specificamente alla riduzione della ridondanza locale per migliorare la precisione senza sacrificare la copertura dei picchi.

Contributi Chiave

• Proposta di Framework: Un nuovo framework di reporting su misura per il trade-off RPR-F1 della competizione CEC 2026, costruito su un robusto ottimizzatore base con adattamento di covarianza.
• Meccanismo di Archivio Passivo: L'introduzione di un archivio secondario per recuperare candidati di alta qualità a livello di restart che l'archivio primario rifiuta, migliorando così il potenziale di copertura senza alterare le dinamiche di ricerca.
• Reporting a Densità Filtrata: Una regola specifica che bilancia copertura e precisione filtrando i candidati ridondanti in base alla distanza normalizzata e al valore obiettivo, affrontando direttamente i vincoli di punteggio della competizione.
• Ablazione e Validazione: Uno studio sperimentale completo che confronta il metodo proposto con il baseline e varie varianti intermedie (ad esempio, reporting rigoroso vs rilassato, regole dipendenti dalla dimensione e varianti modificate nella ricerca) attraverso molteplici istanze di problemi e dimensioni.

Risultati Sperimentali
Gli esperimenti di sviluppo sono stati condotti su un sottoinsieme del benchmark CEC 2026 (320 run) e validati su un sottoinsieme più ampio (768 run).

• Performance: La variante proposta DF-SCA (Density-Filtered SCA) ha ottenuto un punteggio medio di 0.6049 sul sottoinsieme di sviluppo, superando il baseline "Medium" score-aware (0.6012) e l'originale RS-CMSA-ESII (0.5761).
• Analisi del Trade-off: DF-SCA ha mantenuto lo stesso RPR medio dello strong SCA-Medium baseline (0.5589), ma ha migliorato la precisione media da 0.8516 a 0.8705 e l'F1-score da 0.6434 a 0.6509.
• Riduzione della Ridondanza: Il metodo ha ridotto con successo il numero medio di soluzioni riportate da 10.14 (SCA-Medium) a 9.82, confermando che il miglioramento del punteggio deriva da un migliore controllo della precisione piuttosto che dal semplice riportare più candidati.
• Stabilità: La validazione sul sottoinsieme di 768 run ha confermato la stabilità del miglioramento, con DF-SCA che mostra guadagni costanti in tutte le dimensioni ($D \in \{2, 5, 10, 20\}$) e un rapporto vittoria/sconfitta/pareggio di 84/6/678 contro il baseline.
• Varianti Scartate: Diverse modifiche alla ricerca interna (ad esempio, inizializzazione del restart consapevole dell'archivio, passaggi di raffinamento locale come TLLS e CMAR) sono state testate ma scartate a causa di prestazioni inconsistenti o guadagni di punteggio trascurabili.

Significatività e Rivendicazioni
Il documento afferma che S-CARD-CMSA offre un miglioramento a basso rischio e riproducibile di un forte ottimizzatore MMO esistente. La sua significatività risiede nel dimostrare che guadagni di performance significativi nel contesto della CEC 2026 possono essere ottenuti non ridisegnando il motore di ricerca centrale, ma ottimizzando il post-processing delle informazioni sui candidati.

Gli autori sottolineano che il metodo non utilizza le posizioni dei minimi globali reali durante l'ottimizzazione; tali informazioni sono utilizzate esclusivamente per l'analisi offline e il punteggio. Il miglioramento è attribuito a un utilizzo più efficiente dei candidati già generati dall'ottimizzatore base, specificamente recuperando i candidati "persi" del restart e filtrandoli attraverso una regola basata sulla densità che si allinea con la metrica di punteggio della competizione, sensibile alla precisione. Il documento conclude che, sebbene le modifiche più profonde a livello di ricerca rimangano difficili, la ritenzione e il reporting dei candidati consapevoli del punteggio forniscono una via efficace e robusta per migliorare le prestazioni dell'ottimizzazione multimodale sotto criteri di valutazione rigorosi.