La selezione di algoritmi (Algorithm Selection, AS) è un problema centrale in ambito informatico, particolarmente rilevante in contesti come l’ottimizzazione combinatoria e la risoluzione di problemi NP-hard. Il case study “SUNNY-AS2: Enhancing SUNNY for Algorithm Selection” di Tong Liu (Meituan, Beijing, China), Roberto Amadini e Maurizio Gabbrielli (Dipartimento di Informatica – Scienza e Ingegneria, Università di Bologna), Jacopo Mauro (Department of Mathematics and Computer Science, University of Southern Denmark, Denmark) presenta un miglioramento significativo di SUNNY, un approccio basato su k-NN (k-nearest neighbors o primi k-vicini) per la selezione degli algoritmi.

La selezione di algoritmi è una necessità che si pone quando si può contare su un portafoglio di algoritmi e si vuole selezionare il più adatto per risolvere una specifica istanza di un problema. Un problema di selezione degli algoritmi è definito da una tripla (I, A, m) dove I è un insieme di istanze, A è un insieme di algoritmi e m :I × A → R  è una metrica di valutazione delle prestazioni. Per selezionare il miglior algoritmo per risolvere un’istanza sconosciuta x, SUNNY utilizza il k-NN per selezionare dal training set  di I  il sottoinsieme Ik  (detto neighborhood) delle k istanze più vicine al vettore di features F(x) secondo la distanza euclidea. In base alle prestazioni degli algoritmi di A sulle istanze di Ik , SUNNY seleziona un sottoinsieme di A da eseguire. La versione originale di SUNNY ha, però, mostrato alcune limitazioni, specialmente quando applicata a scenari diversi dalla programmazione vincolata (Constraint Programming, CP) per la quale è stata originariamente sviluppata.

Sunny-as2 introduce tre migliorie fondamentali rispetto alla versione originale:

1. Selezione delle features basata su wrapper: a differenza del suo predecessore, sunny-as2 utilizza una selezione delle features basata su wrapper, che permette una definizione più precisa delle features rilevanti per il problema. 

1. Configurazione della dimensione del neighborhood: sunny-as2 permette di configurare la dimensione diIk migliorando così la generalizzazione a diversi scenari. 

1. Approccio greedy per velocizzare la fase di addestramento: L’introduzione di un algoritmo greedy per la selezione degli algoritmi riduce il tempo necessario per la fase di addestramento, rendendo il sistema più efficiente.

L’utente può scegliere fra tre diverse varianti:

1. sunny-as2-k: vengono utilizzate tutte le features e viene eseguita solo la configurazione di k. 

1. sunny-as2-f: il valore di k è fisso e viene eseguita solo la selezione delle features. 

1. sunny-as2-fk: il valore di k e delle features vengono configurati insieme.

Gli autori del case study hanno poi condotto una serie di esperimenti per valutare le prestazioni di sunny-as2 e i risultati mostrano una maggiore efficienza rispetto ad altri metodi di selezione di algoritmi allo stato dell’arte. In particolare, è stato osservato che la configurazione del valore di k e la selezione delle features possono avere un impatto significativo sulle prestazioni del sistema.

In conclusione, sunny-as2 rappresenta un passo avanti significativo nel campo della selezione degli algoritmi, perché offre una soluzione più versatile ed efficiente rispetto ai metodi tradizionali. Con la sua capacità di adattarsi a diversi scenari e la flessibilità delle configurazioni, questo sistema dimostra come l’integrazione tra machine learning e ottimizzazione combinatoria possa portare a risultati sorprendentemente efficaci. Gli esperimenti condotti dagli autori del case study confermano non solo l’efficacia di sunny-as2, ma anche il suo potenziale nel plasmare il futuro della selezione degli algoritmi. In un mondo sempre più dipendente da soluzioni informatiche ottimizzate, l’importanza di strumenti come sunny-as2 non può essere sottovalutata.