Skip to content
Torna ai risultati

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

Dimensione del carattere

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

1

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.

2

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.

3

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.

4

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.

5

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.

6

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

  1. 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 DOI
    Copiato.
  2. Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.

    Apri il riferimento DOI
    Copiato.