Speeding Up the NSGA-II via Dynamic Population Sizes

Resumo Técnico: Acelerando o NSGA-II via Tamanhos de População Dinâmicos

Definição do Problema
Algoritmos evolutivos multiobjetivo (MOEAs), particularmente o Non-dominated Sorting Genetic Algorithm II (NSGA-II), são amplamente utilizados para resolver problemas de otimização multiobjetivo. Um desafio central em sua aplicação é o gerenciamento do tamanho da população ($N$). Para representar efetivamente a fronteira de Pareto (o conjunto de compensações ideais), a população deve ser suficientemente grande. No entanto, uma população grande retarda o algoritmo porque o NSGA-II avalia $N$ soluções por iteração. Isso cria um dilema de design: uma população que é pequena demais falha em cobrir a fronteira de Pareto de forma eficiente, enquanto uma população que é grande demais incorre em custos computacionais desnecessários. Análises matemáticas recentes mostraram que o NSGA-II estático com um tamanho de população fixo ideal possui um tempo de execução de $\Theta(n^2 \log n)$ no benchmark OneMinMax (OMM), o que é considerado subótimo em comparação aos limites inferiores teóricos para certas classes de algoritmos.

Metodologia
Os autores propõem o NSGA-II Dinâmico, uma variante do algoritmo clássico que aborda o dilema do tamanho da população começando com uma população inicial pequena e aumentando-a ao longo do tempo.

• Estrutura do Algoritmo: O algoritmo começa com um tamanho de população de $N=4$. Ele realiza um número fixo de avaliações de função, denotado pelo parâmetro $\tau$ especificado pelo usuário, antes de tentar dobrar o tamanho da população. Esse dobramento continua até que um tamanho máximo de população definido pelo usuário, $N_{max}$, seja alcançado. Crucialmente, o dobramento é disparado pelo número de avaliações de função em vez de iterações, garantindo que cada "fase" do algoritmo receba um orçamento computacional aproximadamente igual, independentemente do tamanho atual da população.
• Mecanismo de Seleção: Os autores utilizam uma variante específica do NSGA-II que emprega a distância de crowding atual para desempate. Este mecanismo, anteriormente demonstrado como capaz de melhorar a distribuição das soluções, remove iterativamente indivíduos com a menor distância de crowding e recomputa as distâncias, levando a uma dispersão de soluções mais equidistante.
• Variantes:
  1. NSGA-II Dinâmico Padrão: Dobra a população a cada $\tau$ avaliações.
  2. NSGA-II Dinâmico com Fase Inicial Longa: Estende a duração da fase inicial (onde $N=4$) para corresponder ao orçamento computacional total de todas as fases subsequentes combinadas. Isso permite que o algoritmo passe mais tempo na fase inicial altamente eficiente sem aumentar a ordem do tempo de execução assintótico.
  3. Estratégia Sem Parâmetros (Algoritmo 3): Para eliminar a necessidade de ajuste manual de $\tau$, os autores propõem uma estratégia de execução concorrente. Este framework lança múltiplas instâncias do NSGA-II dinâmico com diferentes valores de $\tau$ (potências de dois) e aloca recursos dinamicamente para a instância que gastou o menor esforço computacional total até o momento.

Contribuições Principais e Resultados
O artigo fornece análises rigorosas de tempo de execução para os algoritmos propostos em dois benchmarks padrão: OneMinMax (OMM) e OneJumpZeroJump (OJZJ$_k$).

1. Benchmark OMM:

   • O NSGA-II Dinâmico padrão com $\tau$ ótimo alcança um tempo de execução de $O(n \log^2 n)$ avaliações de função com alta probabilidade. Isso é uma melhoria significativa em relação ao tempo de execução de $\Theta(n^2 \log n)$ do NSGA-II estático.
   • A variante com a Fase Inicial Longa alcança um tempo de execução de $O(n \log n)$. Isso é assintoticamente ótimo para uma ampla classe de algoritmos de caixa-preta não enviesados, correspondendo ao limite inferior teórico para encontrar a string de todos os uns (all-ones string).
   • A estratégia concorrente sem parâmetros (Algoritmo 3) alcança tempos de execução de $O(n \log^3 n)$ (padrão) e $O(n \log(N_{max}) \log(n \log N_{max}))$ (fase inicial longa), incorrendo em apenas um fator logarítmico de penalidade em comparação às versões com ajuste ótimo.

2. Benchmark OJZJ$_k$ (com tamanho de gap $k$):

   • O NSGA-II Dinâmico padrão alcança um tempo de execução de $O(nk \log^2 n)$, melhorando o tempo de execução conhecido de $\Theta(nk+1)$ do NSGA-II estático.
   • A variante com a Fase Inicial Longa alcança $O(nk \log n)$.
   • A estratégia sem parâmetros produz tempos de execução de $O(kn^k \log^3 n)$ e $O(kn^k \log(N_{max}) \log(nk \log N_{max}))$, respectivamente.

3. Robustez e Independência de Parâmetros:

   • As garantias de tempo de execução para as variantes dinâmicas são amplamente independentes do tamanho máximo de população $N_{max}$, desde que $N_{max}$ seja ligeiramente maior que o tamanho da fronteira de Pareto (por exemplo, $N_{max} \ge n+4$).
   • Se $\tau$ for escolhido de forma subótima (muito pequeno), o algoritmo retorna ao desempenho do NSGA-II estático com população $N_{max}$, garantindo que uma escolha ruim de parâmetro não seja catastrófica.
   • A estratégia de execução concorrente elimina efetivamente a necessidade de o usuário selecionar $\tau$, criando um algoritmo "sem parâmetros" em relação à dinâmica do tamanho da população.

Significância e Alegações
Os autores alegam que este trabalho é o primeiro a analisar matematicamente um MOEA com parâmetros dinâmicos, demonstrando que a natureza multiobjetivo dos problemas permite acelerações significativas através de estratégias de crescimento de população.

• Avanço Teórico: O artigo estabelece que o dimensionamento dinâmico de população pode quebrar a barreira de $\Theta(n^2 \log n)$ para o NSGA-II no OMM, alcançando tempos de execução que são quase ótimos ($O(n \log n)$) quando a fase inicial é estendida.
• Implicações Práticas: Ao mostrar que uma estratégia simples de execução concorrente pode alcançar um desempenho próximo do ótimo sem ajuste manual de parâmetros, os autores sugerem um caminho para MOEAs mais robustos e "sem parâmetros".
• Comparação com Arquivos (Archives): Os autores observam que, embora outros trabalhos tenham proposto o uso de arquivos para armazenar soluções e permitir populações menores, sua abordagem dinâmica é teoricamente preferível em certos contextos (especificamente em relação à mutação bit a bit sem crossover) porque evita o risco de a população tornar-se insuficiente para gerar novas soluções na fronteira de Pareto.

O artigo conclui que o NSGA-II dinâmico oferece um ganho de velocidade provável de $\tilde{\Omega}(n)$ sobre o NSGA-II estático e que estender a fase inicial ainda mais melhora o desempenho em direção aos limites teóricos da otimização de caixa-preta não enviesada. Sugere-se que trabalhos futuros investiguem se essas vantagens se mantêm para outros cenários populares, como o benchmark LOTZ.