NSGA-II — Non-dominated Sorting Genetic Algorithm II
- Anno
- 2002
- Tipo
- Evolutionary multi-objective optimisation algorithm
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
NSGA-II (Non-dominated Sorting Genetic Algorithm II) è l'algoritmo di riferimento standard per l'ottimizzazione evolutiva multi-obiettivo, introdotto da Deb, Pratap, Agarwal e Meyarivan nel 2002.
Invece di collassare molteplici obiettivi conflittuali in un singolo punteggio, esso evolve una popolazione di soluzioni candidate attraverso generazioni e restituisce un insieme di soluzioni di compromesso Pareto-ottimali — il fronte di Pareto — utilizzando la rapida ordinamento non dominato e una metrica di distanza di affollamento per preservare la diversità.
L’intuizione alla base del metodo
Immaginate di voler progettare un prodotto che sia simultaneamente il più economico e il più durevole possibile. Più economico di solito significa meno durevole, quindi non esiste una singola risposta perfetta — esiste una famiglia di compromessi sensati. NSGA-II funziona come una popolazione di progetti in competizione: ogni generazione, i progetti più deboli che sono dominati da altri su ogni obiettivo vengono eliminati, e i sopravvissuti vengono distribuiti in modo da coprire l'intera gamma di compromessi piuttosto che raggrupparsi attorno a un angolo. Dopo un numero sufficiente di generazioni, si rimane con un ricco menu di opzioni — il fronte di Pareto — da cui scegliere il bilanciamento che si adatta alle proprie priorità.
Storia
NSGA-II è stato pubblicato da Kalyanmoy Deb e colleghi dell'Indian Institute of Technology Kanpur nel 2002 come successore corretto e sostanzialmente migliorato dell'NSGA originale (Srinivas & Deb, 1994). Le innovazioni chiave sono state una procedura di ordinamento non dominato rapida di complessità O(MN²), un operatore esplicito di distanza di affollamento per mantenere la diversità delle soluzioni senza un parametro di condivisione e un meccanismo di selezione elitaria. L'articolo del 2002 su IEEE Transactions on Evolutionary Computation è diventato uno dei lavori più citati nell'ambito dell'evoluzione computazionale e ha stabilito NSGA-II come il benchmark de facto per gli algoritmi evolutivi multi-obiettivo. Varianti successive — NSGA-III (2014) e altre — estendono il framework a problemi con molti obiettivi.
Quando usarlo
NSGA-II si applica ogni volta che un problema ha due o più funzioni obiettivo conflittuali che non possono essere fuse in un singolo criterio senza perdita di informazioni. Le variabili decisionali possono essere continue, binarie o categoriche, e non è richiesta alcuna assunzione distributiva sul panorama degli obiettivi. L'algoritmo è adatto alla progettazione ingegneristica, all'allocazione delle risorse, alla pianificazione e ai problemi di portafoglio in cui uno spettro di soluzioni di compromesso è più utile di un singolo ottimo. È necessario un numero sufficiente di generazioni (tipicamente diverse centinaia o più) per ottenere una buona copertura del fronte; eseguire troppo poche generazioni è la principale modalità di fallimento.
Limiti e considerazioni
- Le prestazioni degradano all'aumentare del numero di obiettivi oltre tre o quattro — la distanza di affollamento diventa una scarsa misura di diversità in alta dimensionalità.
- Richiede un'attenta calibrazione della dimensione della popolazione e del numero di generazioni; troppo poche generazioni impediscono un'adeguata copertura del fronte.
- La valutazione di funzioni obiettivo che coinvolgono simulazioni costose rende l'algoritmo computazionalmente oneroso.
- I risultati sono stocastici: semi casuali diversi possono produrre fronti di Pareto differenti, quindi si raccomandano esecuzioni multiple e confronti statistici (ad es. ipervolume).
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Produce un insieme diversificato di soluzioni di compromesso Pareto-ottimali in un'unica esecuzione, evitando la necessità di ripetere l'ottimizzazione con pesi diversi.
- La rapida ordinamento non dominato viene eseguita in tempo O(MN²) (M obiettivi, N dimensione della popolazione), rendendola trattabile per dimensioni moderate del problema.
- La selezione elitaria garantisce che le buone soluzioni trovate precocemente non vengano mai scartate.
- Applicabile a variabili decisionali continue, binarie e categoriche senza assunzioni distributive.
- Ampiamente validato nei domini dell'ingegneria, della ricerca operativa e delle scienze computazionali.
Applicazioni
- Progettazione ingegneristica: minimizzare simultaneamente il peso e massimizzare la resistenza strutturale nei componenti meccanici.
- Sistemi ambientali ed energetici: bilanciare costi, emissioni e affidabilità nella pianificazione della rete elettrica o delle energie rinnovabili.
- Sanità e ricerca operativa: pianificazione che ottimizza simultaneamente il tempo di attesa dei pazienti, l'utilizzo delle risorse e i costi.
- Ottimizzazione di portafoglio in finanza e selezione di progetti in ambito aziendale: compromesso tra rendimento, rischio e liquidità.
- Ottimizzazione degli iperparametri nell'apprendimento automatico: ottimizzare l'accuratezza rispetto alla complessità del modello o al tempo di inferenza.
Come funziona
Come funziona
Viene creata una popolazione di soluzioni candidate campionando casualmente (o per progettazione) le variabili decisionali entro i loro limiti. La dimensione della popolazione è impostata sufficientemente ampia da garantire fin dall'inizio la diversità nello spazio degli obiettivi.
Ogni soluzione candidata viene decodificata in valori di variabili decisionali e ogni funzione obiettivo viene valutata. Il risultato è un vettore di punteggi obiettivo per individuo. Questo passaggio è spesso il collo di bottiglia computazionale quando gli obiettivi coinvolgono simulazioni o modelli costosi.
Le soluzioni vengono classificate mediante ordinamento non dominato: il primo fronte contiene tutte le soluzioni che nessuna altra soluzione domina su ogni obiettivo; il secondo fronte contiene le soluzioni dominate solo da quelle del primo fronte; e così via. All'interno di ciascun fronte, viene calcolato un punteggio di distanza di affollamento per misurare quanto una soluzione sia isolata dai suoi vicini — una distanza di affollamento maggiore significa che la soluzione occupa una regione meno affollata del fronte.
Una strategia di selezione elitaria fonde la popolazione corrente con gli offspring e conserva gli N migliori individui, riempiendo i fronti in ordine e utilizzando la distanza di affollamento per rompere i pareggi all'interno dell'ultimo fronte ammissibile. Ciò garantisce che le buone soluzioni trovate nelle generazioni precedenti non vengano mai perse.
Gli individui selezionati si riproducono attraverso operatori genetici — selezione a torneo binario, crossover binario simulato (SBX) e mutazione polinomiale — producendo una nuova popolazione di offspring. Questi operatori preservano una variazione significativa esplorando il vicinato di soluzioni promettenti.
I passaggi vengono valutati attraverso l'evoluzione e ripetuti per un numero specificato di generazioni. La convergenza viene giudicata dall'ispezione visiva del fronte di Pareto o dal monitoraggio dell'indicatore di ipervolume. L'output finale è l'insieme di soluzioni non dominate che approssima il vero fronte di Pareto.
Errori comuni
- Eseguire meno di diverse centinaia di generazioni di solito produce un fronte di Pareto incompleto; se il budget computazionale è limitato, considerare invece l'ottimizzazione mono-obiettivo pesata.
- Trattare un problema con un singolo obiettivo come multi-obiettivo è superfluo — utilizzare un ottimizzatore mono-obiettivo.
- Non impostare limiti sensati alle variabili porta a popolazioni che non raggiungono mai regioni fattibili o significative dello spazio di ricerca.
- Riportare una sola soluzione dal fronte di Pareto senza divulgare l'intero fronte nasconde la struttura di compromesso che NSGA-II è progettato per rivelare.
Domande frequenti
Quante generazioni sono necessarie per NSGA-II?
Non esiste una regola universale, ma eseguire meno di qualche centinaio di generazioni di solito produce un fronte di Pareto incompleto. Un approccio pratico è tracciare l'indicatore di ipervolume attraverso le generazioni e fermarsi quando si stabilizza. Se il budget computazionale lo impedisce, un ottimizzatore mono-obiettivo pesato è un'alternativa più sicura.
Cos'è il fronte di Pareto?
Il fronte di Pareto è l'insieme di soluzioni in cui nessun miglioramento su un obiettivo è possibile senza peggiorarne almeno un altro. NSGA-II approssima questo fronte, fornendovi l'intero menu di compromessi bilanciati anziché una singola risposta.
NSGA-II può gestire più di due obiettivi?
Sì, ma la distanza di affollamento — il meccanismo di diversità — diventa meno efficace quando il numero di obiettivi supera tre o quattro (il regime 'many-objective'). Per problemi con cinque o più obiettivi, sono generalmente preferiti NSGA-III o algoritmi basati sulla decomposizione come MOEA/D.
NSGA-II è deterministico?
No. Gli operatori genetici e la popolazione iniziale coinvolgono casualità, quindi esecuzioni diverse con semi casuali differenti possono produrre approssimazioni del fronte di Pareto differenti. La best practice è eseguire l'algoritmo più volte e confrontare la qualità del fronte utilizzando l'indicatore di ipervolume.
Metodi correlati
Fonti
Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
Apri il riferimento DOICopiato.Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.
Apri il riferimento DOICopiato.