Speeding Up the NSGA-II via Dynamic Population Sizes

Sintesi Tecnica: Accelerare l'NSGA-II tramite Dimensioni della Popolazione Dinamiche

Enunciato del Problema
Gli algoritmi evolutivi multi-obiettivo (MOEA), in particolare il Non-dominated Sorting Genetic Algorithm II (NSGA-II), sono ampiamente utilizzati per risolvere problemi di ottimizzazione multi-obiettivo. Una sfida centrale nella loro applicazione è la gestione della dimensione della popolazione ($N$). Per rappresentare efficacemente la frontiera di Pareto (l'insieme dei trade-off ottimali), la popolazione deve essere sufficientemente grande. Tuttavia, una popolazione troppo grande rallenta l'algoritmo perché l'NSGA-II valuta $N$ soluzioni per iterazione. Ciò crea un dilemma progettuale: una popolazione troppo piccola non riesce a coprire la frontiera di Pareto in modo efficiente, mentre una popolazione troppo grande comporta costi computazionali non necessari. Recenti analisi matematiche hanno dimostrato che l'NSGA-II statico con una dimensione della popolazione fissa ottimale ha un tempo di esecuzione di $\Theta(n^2 \log n)$ sul benchmark OneMinMax (OMM), il quale è considerato subottimale rispetto ai limiti inferiori teorici per certe classi di algoritmi.

Metodologia
Gli autori propongono l'NSGA-II Dinamico, una variante del classico algoritmo che affronta il dilemma della dimensione della popolazione partendo da una piccola popolazione iniziale e aumentandola nel tempo.

• Struttura dell'Algoritmo: L'algoritmo inizia con una dimensione della popolazione $N=4$. Esegue un numero fisso di valutazioni della funzione, denotato da un parametro $\tau$ specificato dall'utente, prima di tentare di raddoppiare la dimensione della popolazione. Questo raddoppio continua fino a quando non viene raggiunta una dimensione massima della popolazione definita dall'utente, $N_{max}$. Fondamentalmente, il raddoppio è innescato dal numero di valutazioni della funzione piuttosto che dalle iterazioni, garantendo che ogni "fase" dell'algoritmo riceva un budget computazionale approssimativamente uguale indipendentemente dalla dimensione attuale della popolazione.
• Meccanismo di Selezione: Gli autori utilizzano una specifica variante di NSGA-II che impiega la distanza di crowding corrente (current crowding distance) per la risoluzione dei pareggi (tie-breaking). Questo meccanismo, precedentemente dimostrato come capace di migliorare la distribuzione delle soluzioni, rimuove iterativamente gli individui con la minima distanza di crowding e ricalcola le distanze, portando a una diffusione più equidistante delle soluzioni.
• Varianti:
  1. NSGA-II Dinamico Standard: Raddoppia la popolazione ogni $\tau$ valutazioni.
  2. NSGA-II Dinamico con Fase Iniziale Più Lunga: Estende la durata della fase iniziale (dove $N=4$) per eguagliare il budget computazionale totale di tutte le fasi successive. Ciò consente all'algoritmo di trascorrere più tempo nella fase iniziale altamente efficiente senza aumentare l'ordine del tempo di esecuzione asintotico.
  3. Strategia Senza Parametri (Algoritmo 3): Per eliminare la necessità di una regolazione manuale di $\tau$, gli autori propongono una strategia di esecuzione concorrente. Questo framework lancia molteplici istanze dell'NSGA-II dinamico con diversi valori di $\tau$ (potenze di due) e alloca dinamicamente le risorse all'istanza che ha impiegato il minor sforzo computazionale totale finora.

Contributi Chiave e Risultati
Il documento fornisce analisi rigorose del tempo di esecuzione per gli algoritmi proposti su due benchmark standard: OneMinMax (OMM) e OneJumpZeroJump (OJZJ$_k$).

1. Benchmark OMM:

   • L'NSGA-II Dinamico standard con $\tau$ ottimale raggiunge un tempo di esecuzione di $O(n \log^2 n)$ valutazioni della funzione con alta probabilità. Questo è un miglioramento significativo rispetto al tempo di esecuzione $\Theta(n^2 \log n)$ dell'NSGA-II statico.
   • La variante con la Fase Iniziale Più Lunga raggiunge un tempo di esecuzione di $O(n \log n)$. Questo è asintoticamente ottimale per una vasta classe di algoritmi black-box non viziati, eguagliando il limite inferiore teorico per la ricerca della stringa "all-ones".
   • La strategia concorrente senza parametri (Algoritmo 3) raggiunge tempi di esecuzione di $O(n \log^3 n)$ (standard) e $O(n \log(N_{max}) \log(n \log N_{max}))$ (fase iniziale più lunga), incorrendo solo in una penalità di un fattore logaritmico rispetto alle versioni con $\tau$ ottimale.

2. Benchmark OJZJ$_k$ (con dimensione del gap $k$):

   • L'NSGA-II Dinamico standard raggiunge un tempo di esecuzione di $O(nk \log^2 n)$, migliorando il tempo noto di $\Theta(nk+1)$ dell'NSGA-II statico.
   • La variante con la Fase Iniziale Più Lunga raggiunge $O(nk \log n)$.
   • La strategia senza parametri produce tempi di esecuzione rispettivamente di $O(kn^k \log^3 n)$ e $O(kn^k \log(N_{max}) \log(nk \log N_{max}))$.

3. Robustezza e Indipendenza dai Parametri:

   • Le garanzie di tempo di esecuzione per le varianti dinamiche sono ampiamente indipendenti dalla dimensione massima della popolazione $N_{max}$, a patto che $N_{max}$ sia leggermente superiore alla dimensione della frontiera di Pareto (ad esempio, $N_{max} \ge n+4$).
   • Se $\tau$ viene scelto in modo subottimale (troppo piccolo), l'algoritmo ritorna alle prestazioni dell'NSGA-II statico con popolazione $N_{max}$, garantendo che una scelta errata del parametro non sia catastrofica.
   • La strategia di esecuzione concorrente elimina efficacementamente la necessità per l'utente di selezionare $\tau$, creando un algoritmo "senza parametri" riguardo alle dinamiche della dimensione della popolazione.

Significatività e Rivendicazioni
Gli autori affermano che questo lavoro è il primo ad analizzare matematicamente un MOEA con parametri dinamici, dimostrando che la natura multi-obiettivo dei problemi permette miglioramenti significativi attraverso strategie di crescita della popolazione.

• Avanzamento Teorico: Il documento stabilisce che la dimensione dinamica della popolazione può rompere la barriera $\Theta(n^2 \log n)$ per l'NSGA-II su OMM, raggiungendo tempi di esecuzione quasi ottimali ($O(n \log n)$) quando la fase iniziale viene estesa.
• Implicazioni Pratiche: Dimostrando che una semplice strategia di esecuzione concorrente può raggiungere prestazioni quasi ottimali senza la regolazione manuale dei parametri, gli autori suggeriscono una strada verso MOEA più robusti e "senza parametri".
• Confronto con gli Archivi: Gli autori notano che, sebbene altri lavori abbiano proposto l'uso di archivi per memorizzare le soluzioni e consentire popolazioni più piccole, il loro approccio dinamico è teoricamente preferibile in certi contesti (specificamente riguardo alla mutazione bit a bit senza crossover) perché evita il rischio che la popolazione diventi insufficiente per generare nuove soluzioni sulla frontiera di Pareto.

Il documento conclude che l'NSGA-II dinamico offre un miglioramento provabile di $\tilde{\Omega}(n)$ rispetto all'NSGA-II statico e che l'estensione della fase iniziale migliora ulteriormente le prestazioni verso i limiti teorici dell'ottimizzazione black-box non viziata. Si suggerisce di investigare se tali vantaggi si mantengano anche per altri scenari popolari, come il benchmark LOTZ.