Ottimizzazione Multi-Obiettivo: Il Campionamento Ripetuto ε Manda in Pensione il Caso!

Avete mai provato a ottimizzare qualcosa cercando di raggiungere *tanti* obiettivi contemporaneamente? Pensate alla progettazione di un’auto: volete massimizzare la velocità, minimizzare i consumi, massimizzare la sicurezza, minimizzare i costi… un bel rompicapo! Nel mondo della ricerca, chiamiamo questi problemi “ottimizzazione multi-obiettivo” (o, quando gli obiettivi sono davvero tanti, “many-objective”). Risolverli è una delle sfide più affascinanti e complesse.

Gli algoritmi evolutivi multi-obiettivo (MOEA) sono tra gli strumenti più potenti che abbiamo per affrontare queste sfide. Funzionano un po’ come l’evoluzione naturale: generano un insieme di possibili soluzioni, le valutano in base ai vari obiettivi e selezionano le migliori per creare nuove generazioni, sperando di avvicinarsi sempre di più a un set di soluzioni ottimali, il famoso “fronte di Pareto”.

Il Cuore del Problema: Selezione e Diversità

Uno dei punti cruciali, specialmente quando gli obiettivi diventano numerosi (diciamo più di tre), è come mantenere la diversità tra le soluzioni. Immaginate di avere tante soluzioni eccellenti ma tutte molto simili tra loro: non avreste una buona panoramica delle possibili alternative! Gli algoritmi basati sulla classica “dominanza di Pareto” faticano parecchio in questi scenari “many-objective”, perché quasi tutte le soluzioni finiscono per essere “non dominate” (cioè, nessuna è chiaramente migliore di un’altra su *tutti* gli obiettivi), rendendo difficile la selezione.

Per superare questo limite, sono state introdotte estensioni della dominanza di Pareto, come la ε-dominanza. L’idea è di “rilassare” un po’ il concetto di dominanza: una soluzione ne ε-domina un’altra se è leggermente migliore su alcuni obiettivi, anche se non su tutti. Questo aiuta a distinguere meglio le soluzioni e a selezionare un insieme più gestibile e diversificato.

Algoritmi come AεSεH (Adaptive ε-Sampling and ε-Hood) usano proprio l’ε-dominanza per selezionare le soluzioni che sopravvivono alla generazione successiva (survival selection) e per raggruppare i genitori (parent selection). AεSεH è furbo perché adatta il valore di ε dinamicamente, senza fare ipotesi sulla forma del fronte di Pareto, il che lo rende versatile.

Però, c’è un “ma”. Il meccanismo di campionamento di AεSεH (Adaptive ε-Sampling) non è precisissimo. Spesso seleziona un numero di soluzioni leggermente diverso da quello desiderato (la dimensione della popolazione). Per aggiustare il tiro, cosa fa? Aggiunge o toglie soluzioni a caso. E questo, capite bene, può rovinare la bella distribuzione che si era cercato di ottenere con l’ε-dominanza. Un po’ frustrante, no?

La Nostra Idea: Il Campionamento Ripetuto ε (Rε-Sampling)

Ed è qui che entriamo in gioco noi! Ci siamo chiesti: possiamo ridurre questa casualità e ottenere un campionamento *davvero* accurato e ben distribuito? La risposta che abbiamo trovato è il Campionamento Ripetuto ε (Repeated ε-Sampling, o Rε-Sampling).

Come funziona? È un processo iterativo:

1. Partiamo dall’insieme di soluzioni non dominate che vogliamo ridurre.
2. Iniziamo con un valore di ε molto piccolo, che definisce una “distanza di espansione” minima tra le soluzioni.
3. Applichiamo l’ε-Sampling: selezioniamo una soluzione a caso, trasformiamo i suoi valori obiettivo usando ε, e scartiamo tutte le altre soluzioni che essa ε-domina (cioè quelle troppo “vicine” nello spazio degli obiettivi). Ripetiamo finché non abbiamo esaminato tutte le soluzioni iniziali.
4. Abbiamo ottenuto un primo campione. È della dimensione giusta? Probabilmente no, sarà ancora troppo grande.
5. Allora, aumentiamo leggermente il valore di ε (aumentando la “distanza di espansione”) e ripetiamo il passo 3, ma questa volta partendo dal campione ottenuto al passo precedente.
6. Continuiamo così, aumentando ε ad ogni iterazione, finché il campione non raggiunge (o si avvicina moltissimo) alla dimensione desiderata.

In pratica, eliminiamo gradualmente le soluzioni più vicine tra loro, partendo da quelle quasi sovrapposte e allargando via via il raggio d’azione. L’obiettivo è ottenere un insieme finale di soluzioni ben spaziate, riducendo al minimo la necessità di aggiustamenti casuali.

Mettiamolo alla Prova: Esperimenti sui Paesaggi MNK

Per vedere se la nostra idea funzionava, abbiamo preso l’algoritmo AεSεH e abbiamo provato due cose:

• I-AεSεH (Improved AεSεH): Abbiamo usato Rε-Sampling *dopo* il campionamento standard di AεSεH, come una sorta di “raffinatore” per migliorare la selezione finale.
• RεSAεH (Repeated ε-Sampling and Adaptive ε-Hood): Abbiamo sostituito *completamente* il campionamento standard di AεSεH con il nostro Rε-Sampling.

Come banco di prova abbiamo usato i paesaggi MNK. Sono problemi di ottimizzazione binaria (sequenze di 0 e 1) molto interessanti perché possiamo decidere noi quanti obiettivi (M), quante variabili (N, la lunghezza della sequenza) e quanto le variabili interagiscono tra loro (K, l’epistasi). Più K è alto, più il problema è complesso e “frastagliato”. Abbiamo testato con 4, 5, 6 e 7 obiettivi, 100, 300 e 500 variabili, e diversi livelli di interazione (K da 5 a 20).

Abbiamo confrontato le performance di I-AεSεH e RεSAεH con quelle dell’AεSεH originale e con MOEA/D, un altro algoritmo molto popolare per l’ottimizzazione many-objective, basato su un approccio diverso (decomposizione). Per valutare i risultati, abbiamo usato diverse metriche:

• Hypervolume (HV): Misura quanto “volume” nello spazio degli obiettivi è coperto dalle soluzioni trovate (più è alto, meglio è).
• C-metric: Confronta due set di soluzioni e dice quale percentuale di uno è dominata dall’altro (utile per capire la convergenza relativa).
• Overall Spread (OS): Misura quanto sono “sparpagliate” le soluzioni estreme.
• Spacing (SP): Valuta l’uniformità della distanza tra soluzioni vicine (più è basso, più sono distribuite regolarmente).
• Distribution Metric (DM): Un’altra misura di diversità, sensibile a grandi “buchi” nella distribuzione.

I Risultati Parlano Chiaro

Allora, cosa abbiamo scoperto?

1. Precisione del Campionamento: Come sospettavamo, Rε-Sampling (sia in I-AεSεH che in RεSAεH) è molto più preciso dell’Adaptive ε-Sampling originale. La differenza tra il numero di soluzioni campionate e la dimensione target della popolazione è minima. Questo significa: molto meno affidamento sulla selezione casuale! Addio caso, benvenuta precisione.

2. RεSAεH vs I-AεSεH: Entrambi i nostri metodi migliorano AεSεH, ma RεSAεH (la sostituzione completa) si è rivelato generalmente superiore, specialmente all’aumentare del numero di obiettivi. Mostra una convergenza migliore (trova soluzioni più vicine al fronte di Pareto ideale, come indicato dalla C-metric) e una maggiore uniformità nella distribuzione (SP più basso). Curiosamente, a volte la metrica DM peggiora leggermente. Analizzando più a fondo, sembra che RεSAεH sia così bravo a trovare soluzioni estreme (le migliori per un singolo obiettivo) che a volte crea degli spazi vuoti tra queste e il resto del fronte. Ma nel complesso, i vantaggi superano questo piccolo neo.

3. Scalabilità: RεSAεH si comporta egregiamente anche quando aumentiamo la difficoltà, sia aumentando il numero di variabili (N=300, N=500) sia il numero di obiettivi (fino a 7). Anzi, il suo vantaggio rispetto a I-AεSεH diventa ancora più marcato in questi scenari più complessi. Sembra proprio che il nostro metodo scali bene!

4. Confronto con MOEA/D e AεSεH: Qui i risultati sono stati netti. Su questi problemi MNK, RεSAεH ha superato significativamente sia l’AεSεH originale che MOEA/D, sia in termini di Hypervolume (HV) che di convergenza (C-metric). Questo è un risultato importante, perché MOEA/D è un riferimento nel campo.

Conclusioni e Prossimi Passi

Insomma, il nostro Campionamento Ripetuto ε (Rε-Sampling) sembra essere un passo avanti notevole per la selezione di sopravvivenza negli algoritmi evolutivi many-objective. Sostituendo i metodi precedenti (come in RεSAεH), otteniamo campioni di soluzioni molto più accurati, ben distribuiti e, alla fine, performance migliori in termini di convergenza e diversità, specialmente su problemi complessi.

Certo, c’è sempre spazio per migliorare. Stiamo già pensando a come rendere il processo ancora più efficiente, magari adattando dinamicamente non solo ε ma anche il modo in cui calcoliamo la “distanza base” tra le soluzioni. Vogliamo anche esplorare come combinare Rε-Sampling con metodi di selezione dei genitori e di crossover più intelligenti, per andare a cercare attivamente soluzioni nelle zone del fronte di Pareto che potrebbero essere rimaste scoperte.

La strada dell’ottimizzazione multi-obiettivo è ancora lunga e piena di sfide, ma crediamo che Rε-Sampling sia uno strumento prezioso da aggiungere alla nostra cassetta degli attrezzi per affrontarle al meglio!

Fonte: Springer