Skip to content
Voltar aos resultados

NSGA-II — Algoritmo Genético de Ordenação Não Dominada II

Ano
2002
Tipo
Evolutionary multi-objective optimisation algorithm

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

O NSGA-II (Algoritmo Genético de Ordenação Não Dominada II) é o algoritmo de referência padrão para otimização evolutiva multiobjetivo, introduzido por Deb, Pratap, Agarwal e Meyarivan em 2002.

Em vez de colapsar múltiplos objetivos conflitantes em uma única pontuação, ele evolui uma população de soluções candidatas ao longo de gerações e retorna um conjunto de soluções de compromisso Pareto-ótimas — a frente de Pareto — utilizando ordenação rápida não dominada e uma métrica de distância de aglomeração para preservar a diversidade.

A intuição por trás do método

Imagine que você quer projetar um produto que seja simultaneamente o mais barato e o mais durável possível. Mais barato geralmente significa menos durável, então não há uma única resposta perfeita — há uma família de compromissos sensatos. O NSGA-II funciona como uma população de projetos concorrentes: a cada geração, os projetos mais fracos que são dominados por outros em todos os objetivos são eliminados, e os sobreviventes são espalhados para cobrir toda a gama de compromissos, em vez de se agrupar em um canto. Após gerações suficientes, você fica com um rico menu de opções — a frente de Pareto — a partir do qual escolhe o equilíbrio que se adequa às suas prioridades.

História

O NSGA-II foi publicado por Kalyanmoy Deb e colegas do Instituto Indiano de Tecnologia de Kanpur em 2002 como um sucessor corrigido e substancialmente aprimorado do NSGA original (Srinivas & Deb, 1994). As principais inovações foram um procedimento rápido de ordenação não dominada de complexidade O(MN²), um operador explícito de distância de aglomeração para manter a diversidade de soluções sem um parâmetro de compartilhamento, e um mecanismo de seleção elitista. O artigo de 2002 da IEEE Transactions on Evolutionary Computation tornou-se um dos trabalhos mais citados em computação evolutiva e estabeleceu o NSGA-II como o benchmark de fato para algoritmos evolutivos multiobjetivo. Variantes posteriores — NSGA-III (2014) e outras — estendem o framework para problemas com muitos objetivos.

Quando usar

O NSGA-II se aplica sempre que um problema tem duas ou mais funções objetivo conflitantes que não podem ser fundidas em um único critério sem perda de informação. As variáveis de decisão podem ser contínuas, binárias ou categóricas, e nenhuma suposição distribucional sobre o panorama objetivo é necessária. O algoritmo é adequado para projeto de engenharia, alocação de recursos, escalonamento e problemas de portfólio onde um espectro de soluções de compromisso é mais útil do que um único ótimo. Um número suficiente de gerações (tipicamente várias centenas ou mais) é necessário para alcançar uma boa cobertura da frente; executar poucas gerações é o principal modo de falha.

Limitações e considerações

  • O desempenho degrada à medida que o número de objetivos cresce além de três ou quatro — a distância de aglomeração se torna uma medida de diversidade pobre em altas dimensões.
  • Requer ajuste cuidadoso do tamanho da população e da contagem de gerações; poucas gerações impedem cobertura adequada da frente.
  • Avaliar funções objetivo que envolvem simulações caras torna o algoritmo computacionalmente custoso.
  • Os resultados são estocásticos: diferentes sementes aleatórias podem gerar diferentes frentes de Pareto, portanto, múltiplas execuções e comparação estatística (por exemplo, hipervolume) são recomendadas.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Produz um conjunto diversificado de soluções de compromisso Pareto-ótimas em uma única execução, evitando a necessidade de repetir a otimização com pesos diferentes.
  • A ordenação rápida não dominada é executada em tempo O(MN²) (M objetivos, N tamanho da população), tornando-a tratável para tamanhos de problema moderados.
  • A seleção elitista garante que boas soluções encontradas precocemente nunca sejam descartadas.
  • Aplicável a variáveis de decisão contínuas, binárias e categóricas sem suposições distribucionais.
  • Amplamente validado em domínios de engenharia, pesquisa operacional e ciência computacional.

Aplicações

  • Projeto de engenharia: minimizando simultaneamente o peso e maximizando a resistência estrutural em componentes mecânicos.
  • Sistemas ambientais e de energia: equilibrando custo, emissões e confiabilidade no planejamento de redes elétricas ou de energia renovável.
  • Saúde e pesquisa operacional: escalonamento que otimiza o tempo de espera do paciente, a utilização de recursos e o custo simultaneamente.
  • Otimização de portfólio em finanças e seleção de projetos em negócios: negociando retorno, risco e liquidez.
  • Ajuste de hiperparâmetros em aprendizado de máquina: otimizando a precisão contra a complexidade do modelo ou o tempo de inferência.

Como funciona

Como funciona

1

Uma população de soluções candidatas é criada amostrando variáveis de decisão aleatoriamente (ou por projeto) dentro de seus limites. O tamanho da população é definido como grande o suficiente para garantir a diversidade no espaço objetivo desde o início.

2

Cada solução candidata é decodificada em valores de variáveis de decisão e cada função objetivo é avaliada. O resultado é um vetor de pontuações de objetivo por indivíduo. Esta etapa é frequentemente o gargalo computacional quando os objetivos envolvem simulações ou modelos caros.

3

As soluções são classificadas por ordenação não dominada: a primeira frente contém todas as soluções que nenhuma outra solução domina em todos os objetivos; a segunda frente contém soluções dominadas apenas pelas da primeira frente; e assim por diante. Dentro de cada frente, uma pontuação de distância de aglomeração é calculada para medir o quão isolada uma solução está de seus vizinhos — maior distância de aglomeração significa que a solução ocupa uma região menos densa da frente.

4

Uma estratégia de seleção elitista mescla a população atual com os descendentes e retém os melhores N indivíduos, preenchendo as frentes em ordem e usando a distância de aglomeração para desempatar na última frente admissível. Isso garante que boas soluções encontradas em gerações anteriores nunca sejam perdidas.

5

Indivíduos selecionados se reproduzem através de operadores genéticos — seleção por torneio binário, cruzamento binário simulado (SBX) e mutação polinomial — produzindo uma nova população de descendentes. Esses operadores preservam a variação significativa enquanto exploram a vizinhança de soluções promissoras.

6

As etapas avaliam através de evoluir repetem por um número especificado de gerações. A convergência é julgada pela inspeção visual da frente de Pareto ou pelo rastreamento do indicador de hipervolume. A saída final é o conjunto de soluções não dominadas que aproxima a frente de Pareto verdadeira.

Erros comuns

  • Executar menos de várias centenas de gerações geralmente produz uma frente de Pareto incompleta; se o orçamento computacional for apertado, considere otimização mono-objetivo ponderada em vez disso.
  • Tratar um problema com um único objetivo como multiobjetivo é desnecessário — use um otimizador mono-objetivo.
  • Negligenciar a definição de limites sensatos para as variáveis leva a populações que nunca atingem regiões viáveis ou significativas do espaço de busca.
  • Relatar apenas uma solução da frente de Pareto sem divulgar a frente completa oculta a estrutura de compromisso que o NSGA-II foi projetado para revelar.

Perguntas frequentes

Quantas gerações o NSGA-II necessita?

Não há regra universal, mas executar menos de algumas centenas de gerações geralmente produz uma frente de Pareto incompleta. Uma abordagem prática é plotar o indicador de hipervolume ao longo das gerações e parar quando ele se estabilizar. Se o orçamento computacional impedir isso, um otimizador ponderado mono-objetivo é uma alternativa mais segura.

O que é a frente de Pareto?

A frente de Pareto é o conjunto de soluções onde nenhuma melhoria em um objetivo é possível sem piorar pelo menos outro. O NSGA-II aproxima essa frente, fornecendo o menu completo de compromissos equilibrados em vez de uma única resposta.

O NSGA-II pode lidar com mais de dois objetivos?

Sim, mas a distância de aglomeração — o mecanismo de diversidade — torna-se menos eficaz à medida que o número de objetivos excede três ou quatro (o regime de 'muitos objetivos'). Para problemas com cinco ou mais objetivos, o NSGA-III ou algoritmos baseados em decomposição como o MOEA/D são geralmente preferidos.

O NSGA-II é determinístico?

Não. Os operadores genéticos e a população inicial envolvem aleatoriedade, de modo que execuções diferentes com sementes aleatórias diferentes podem gerar aproximações diferentes da frente de Pareto. A melhor prática é executar o algoritmo várias vezes e comparar a qualidade da frente usando o indicador de hipervolume.

Métodos relacionados

Fontes

  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.

    Abrir referência DOI
    Copiado.
  2. Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.

    Abrir referência DOI
    Copiado.