CVaR-RMD: pressione selettiva basata sul CVaR per la scoperta robusta di metaeuristiche

Abstract degli autori

Di recente, i modelli linguistici di grandi dimensioni sono stati usati per scoprire euristiche mediante una ricerca iterativa di programmi, offrendo un approccio promettente alla progettazione automatica di algoritmi. Tuttavia, le prestazioni dei candidati selezionati in base alla media possono peggiorare al variare delle famiglie di istanze, dei semi casuali e delle dimensioni dei problemi, perché gli obiettivi basati sulla media possono nascondere fallimenti rari ma gravi. Proponiamo CVaR-RMD, un framework evolutivo sensibile al rischio che usa un modello linguistico di grandi dimensioni per modificare programmi euristici eseguibili e classifica i candidati in base al valore a rischio condizionato empirico calcolato su condizioni di valutazione eterogenee. In tre ambiti dell’ottimizzazione combinatoria, la selezione basata sul CVaR migliora le prestazioni nella coda superiore e riduce i tassi di fallimento, mantenendo prestazioni medie competitive. Questi miglioramenti persistono su istanze più grandi mai viste prima e su benchmark dello stesso dominio allestiti in modo indipendente.