Maximum Dispersion, Maximum Concentration: Enhancing the Quality of MOP Solutions

Sintesi Tecnica: Massima Dispersione, Massima Concentrazione

Definizione del Problema
I problemi di ottimizzazione multi-obiettivo (MOP) richiedono un bilanciamento tra obiettivi contrastanti, mirando tipicamente ad approssimare la Frontiera di Pareto (PF) nello spazio degli obiettivi. Sebbene gli algoritmi evolutivi multi-obiettivo (MOEA) tradizionali convergano efficacemente alla PF, essi soffrono spesso di un limite critico: le soluzioni tendono a raggrupparsi in regioni specifiche dello spazio delle decisioni. Questa mancanza di diversità nello spazio delle decisioni ($\Omega$) crea un bias di implementazione, in cui i decisori vengono presentati con un set ristretto di opzioni che potrebbero diventare inapplicabili se le condizioni iniziali dovessero cambiare. Al contrario, sebbene esistano metodi basati sulle preferenze per concentrare gli sforzi di ricerca su una specifica Regione di Interesse (ROI) nello spazio degli obiettivi per migliorare la convergenza, questi raramente affrontano la necessità simultanea di massima dispersione nello spazio delle decisioni. Il documento identifica una lacuna nella letteratura riguardante l'ottimizzazione simultanea della concentrazione delle soluzioni nello spazio degli obiettivi e della dispersione nello spazio delle decisioni.

Metodologia: L'algoritmo C-DWU
Gli autori propongono l'algoritmo C-DWU (Cone-Dominance Weighted Uniformity), un adattamento dell'esistente approccio Dominance-Weighted Uniformity (DWU). La metodologia integra le preferenze di un decisore, definite da un cono di preferenza $C$ (caratterizzato da un vettore asse $v$ e un angolo di apertura $\theta$), nel processo evolutivo attraverso due modifiche specifiche:

1. Sorting Non Dominato Penalizzato: Durante la fase di sorting, le soluzioni situate al di fuori del cono di preferenza $C$ vengono penalizzate. La penalità è proporzionale alla distanza angolare ($\phi$) tra il vettore degli obiettivi della soluzione e l'asse del cono $v$. Ciò viene calcolato utilizzando una funzione di penalizzazione $P_{\alpha,\theta}(\phi) = \lfloor e^{\alpha(\phi-\theta)} \rfloor$, che aumenta il livello della frontiera di non-dominanza delle soluzioni esterne, spingendo efficacemente la ricerca verso la ROI.
2. Euristica di Selezione Modificata (C-wd): La standard euristica di selezione DWU, che massimizza l'uniformità nello spazio delle decisioni, viene modificata per incorporare il cono di preferenza. Una nuova funzione, C-wd, applica un termine di penalità $P_{\beta,\theta}(\phi)$ al calcolo dell'uniformità pesata per dominanza per le soluzioni al di fuori del cono. Ciò assicura che, mentre l'algoritmo cerca di massimizzare la distanza tra le soluzioni nello spazio delle decisioni (dispersione), esso dia priorità a quelle che soddisfano anche i vincoli di concentrazione all'interno della ROI nello spazio degli obiettivi.

L'algoritmo mira a trovare un sottoinsieme di soluzioni che siano Pareto-ottimali, concentrate entro la ROI definita nello spazio degli obiettivi e massimamente disperse nello spazio delle decisioni.

Configurazione Sperimentale e Risultati
Gli autori hanno valutato C-DWU rispetto a una versione modificata di NSGA-II (denotata come C-NSGAII), che applica lo stesso penalizzazione basata sul cono allo standard NSGA-II ma manca del meccanismo di dispersione dello spazio delle decisioni. Gli esperimenti sono stati condotti su problemi di ottimizzazione vincolata bi-obiettivo utilizzando le suite di test WFG4, WFG9 (multimodale) e DTLZ2 (unimodale) con dimensioni dello spazio delle decisioni di 5, 7 e 9.

• Convergenza (Spazio degli Obiettivi): Misurata tramite l'Inverted Generational Distance (IGD) relativa alla ROI. I risultati indicano che C-NSGAII ha ottenuto una convergenza leggermente migliore (valori IGD inferiori) nella maggior parte delle istanze.
• Dispersione (Spazio delle Decisioni): Misurata tramite una metrica di uniformità basata sulla distanza minima tra le soluzioni. C-DWU ha superato significativamente C-NSGAII, ottenendo valori di uniformità molto più elevati.
• Visualizzazione: La visualizzazione ad alta dimensione (usando CAP-VIZ) del problema WFG4 ha rivelato che le soluzioni di C-NSGAII si raggruppavano pesantemente in un singolo settore dello spazio delle decisioni (vicino all'asse $e_9$), mentre le soluzioni di C-DWU erano distribuite attraverso molteplici settori (7, 8 e 9) con maggiore variabilità sia nella distanza angolare che nella norma euclidea.

Contributi Chiave

• Ottimizzazione a Doppio Obiettivo: Il documento introduce un framework che massimizza simultaneamente la concentrazione delle soluzioni in una specifica ROI dello spazio degli obiettivi e la dispersione delle soluzioni nello spazio delle decisioni.
• Adattamento Algoritmico: Lo sviluppo di C-DWU, che modifica l'algoritmo DWU per accettare i vincoli del cono di preferenza senza sacrificare la diversità dello spazio delle decisioni.
• Mitigazione del Bias: L'approccio affronta il problema delle soluzioni "polarizzate" nello spazio delle decisioni, offrendo ai decisori un set diversificato di opzioni di implementazione che sono tutte ottimali all'interno di una regione preferita dello spazio degli obiettivi.

Significatività e Rivendicazioni
Gli autori sostengono che il metodo proposto migliori la qualità delle soluzioni MOP bilanciando diversità e accuratezza. Argomentano che, sebbene l'algoritmo C-DWU possa esibire una marginale riduzione dei tassi di convergenza rispetto a C-NSGAII, questo compromesso è giustificato dal sostanziale guadagno nella diversità delle soluzioni. La principale significatività risiede nel fornire ai decisori un set robusto di opzioni; soluzioni diverse nello spazio delle decisioni consentono flessibilità qualora si verifichino cambiamenti imprevisti nello scenario reale, evitando la necessità di costose ri-ottimizzazioni. Il documento conclude che definire una ROI tramite un cono di preferenza è un metodo efficace e facilmente regolabile per integrare le preferenze del decisore negli algoritmi evolutivi, preservando al contempo la rappresentatività del set di soluzioni.