O algoritmo Non-dominated Sorting Genetic Algorithm II (NSGA-II)

Métodos Heurísticos Populacionais

Rodrigo Hermont Ozon

Conteúdo

 

…em até 15 minutinhos, pretendo abordar brevemente

  • Contextualização (Introdução)

  • Histórico da evolução do NSGAII

  • Avanços e marcos teóricos de seu desenvolvimento

  • Funcionamento do NSGAII

  • Algumas aplicações do NSGAII na minha pesquisa

  • Esclarecimento de dúvidas

  • Meus Contatos

Intro

  • O NSGA-II, ou “Non-dominated Sorting Genetic Algorithm II”, é um algoritmo evolutivo popular usado para otimização multiobjetivo.

  • Ele é projetado para resolver problemas onde há múltiplos objetivos em conflito, e a solução ideal é um conjunto de soluções, conhecido como “Frente ou Fronteira de Pareto”.

  • O NSGA-II é amplamente reconhecido por sua eficiência e capacidade de encontrar um conjunto diversificado de soluções na fronteira de Pareto.

  • Ele supera muitos de seus predecessores em termos de velocidade, precisão e diversidade das soluções.

  • É aplicado em uma variedade de campos, desde engenharia, bioinformática (para otimização de redes metabólicas) até economia, devido à sua capacidade de lidar com complexidades e múltiplos objetivos.

Breve Histórico

  • O NSGA[1] (Non-dominated Sorting Genetic Algorithm) é um algoritmo evolutivo desenvolvido para otimização multiobjetivo. Ele utiliza uma abordagem baseada em dominância para classificar e selecionar soluções, identificando aquelas que estão na fronteira de Pareto, o conjunto ideal de soluções em problemas multiobjetivo. Para garantir uma distribuição diversificada de soluções ao longo desta fronteira, o NSGA incorpora o conceito de “compartilhamento de nicho”. Combinando essas características com operadores genéticos tradicionais, como seleção, cruzamento e mutação, o NSGA busca soluções ótimas em problemas onde múltiplos objetivos estão em conflito.

  • O NSGA original foi introduzido em 1995 e, embora fosse eficaz, tinha algumas limitações, especialmente em termos de compartilhamento de nicho e complexidade computacional.

  • *Compartilhamento de nicho é uma técnica usada em algoritmos genéticos e outros algoritmos evolutivos para manter a diversidade na população durante o processo de evolução. A ideia é evitar a convergência prematura para uma solução subótima e garantir que várias regiões do espaço de busca sejam exploradas.

  • O NSGA-II[2] foi proposto em 2002 por Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal e T. Meyarivan como uma melhoria significativa do algoritmo original, abordando suas limitações.

Inspiração e evolução

Inspiração:

  • Baseado em algoritmos genéticos, o NSGA foi desenvolvido para abordar a otimização multiobjetivo, onde múltiplos objetivos muitas vezes estão em conflito.
  • A necessidade de encontrar um conjunto diversificado de soluções na fronteira de Pareto levou ao desenvolvimento do NSGA e, posteriormente, do NSGA-II.

Evolução:

  • NSGA: Introduzido em 1995, focado na otimização multiobjetivo, mas tinha limitações em compartilhamento de nicho e complexidade.
  • NSGA-II: Proposto em 2002 como uma melhoria significativa, introduzindo conceitos como elitismo\(^1\), compartilhamento de nicho aprimorado e uma estratégia de seleção mais eficiente.
  • Desenvolvimentos Subsequentes: Ao longo dos anos, várias melhorias e variações do NSGA-II foram propostas para abordar cenários específicos e limitações percebidas.

  1. Elitismo é um conceito usado em algoritmos genéticos e outras técnicas de otimização evolutiva. Refere-se à prática de preservar as melhores soluções (indivíduos) de uma geração para a próxima, garantindo que os indivíduos de alta qualidade não sejam perdidos devido a operações de cruzamento ou mutação. Em outras palavras, o elitismo garante que a qualidade da população não degrade ao longo das gerações.

Evolução desde o artigo original

Ano Título Descrição
\(\pm\) 60´s Algoritmos Ponderados Abordagem clássica para otimização multiobjetivo convertendo em problemas de objetivo único.
\(\pm\) 70´s Algoritmo de Otimização Vetorial (VGA) Abordagem clássica em otimização multiobjetivo otimizando todos os objetivos simultaneamente.
\(\pm\) 70´s Método de Otimização de Função Escalar (SFMO) Abordagem que tenta otimizar uma combinação escalar dos objetivos.
\(\pm\) 70´s e 80´s Algoritmo de Otimização de Compromisso (TCGA) Busca soluções que sejam um compromisso entre diferentes objetivos.
1995 Multi-objective genetic algorithms: Problem difficulties and construction of test problems [Deb, 1995] Introdução do NSGA original. Aborda otimização multiobjetivo e suas dificuldades.
2002 A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II [Deb et al., 2002] Melhoria significativa do NSGA original. Aborda compartilhamento de nicho e complexidade computacional.
Anos subsequentes Vários estudos e melhorias [ Hort, M., Sarro, F. (2021), Wang, Y. et al. (2019), El-Abbasy, M. S., Elazouni, A., Zayed, T. (2020), Ouyang, J., Yang, F., Yang, S., Nie, Z. (2008), Ardakan, M. A., Rezvan, M. T. (2018), Fettaka, S., Thibault, J., Gupta, Y. (2015) ] Estudos propuseram melhorias no NSGA-II para abordar suas limitações em cenários específicos, desde otimização de minas de metal até otimização de portfólio.

Comparação com outros algoritmos

  • O NSGA-II é frequentemente comparado a outros algoritmos de otimização multiobjetivo, como o SPEA2 (Strength Pareto Evolutionary Algorithm 2) e o MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition). Em muitos benchmarks e aplicações, o NSGA-II demonstrou ter uma performance superior em termos de encontrar uma fronteira de Pareto mais diversificada e precisa.

  • A complexidade computacional do NSGA-II é principalmente influenciada pela operação de ordenação não dominada. Para uma população de tamanho \(N\), a complexidade é da ordem de \(O(N^2)\), tornando-o eficiente para muitos problemas práticos, embora possa ser desafiador para problemas com grandes populações ou muitos objetivos.

Razões para Comparação:

  • Avaliar eficiência e uso de recursos.
  • Determinar qualidade e proximidade da fronteira de Pareto.
  • Medir diversidade das soluções.
  • Testar generalidade em diferentes problemas.

Comparativos geralmente presentes na literatura

Desafios e Limitações

  • Eficiência em Problemas de Grande Escala: Em alguns estudos, variantes melhoradas do NSGA-II foram propostas para otimização de problemas de grande escala, indicando que o NSGA-II padrão pode não ser o mais eficiente para tais problemas Xiaowei Gu et al., 2020.

  • Comparação com NSGA-III: Em certos problemas multiobjetivos, o NSGA-III, uma versão subsequente do NSGA-II, mostrou desempenho superior em métricas como distância central, métrica de espaçamento e eficiência computacional Yihan Wang et al., 2019. No entanto, em outros estudos, foi observado que o NSGA-III não supera sempre o NSGA-II, mesmo para problemas com muitos objetivos H. Ishibuchi et al., 2016.

  • Comparação com Outros Algoritmos: Em alguns cenários, o NSGA-II foi superado por outros algoritmos em termos de eficiência e qualidade de solução. Por exemplo, o 2-phase NSGA II superou o NSGA-II em otimização de portfólio Seyedeh Elham Eftekharian et al., 2017. Em outro estudo, o NSGA-II teve um desempenho melhor do que o MOPSO em problemas de pequena escala, mas pode não ser o caso em problemas de maior escala Nima Farmand et al., 2021.

  • Necessidade de Melhorias e Modificações: Vários estudos propuseram melhorias e modificações no NSGA-II para abordar suas limitações. Por exemplo, um estudo propôs uma versão melhorada do NSGA-II para otimizar o processo de produção de minas de metal Xiaowei Gu et al., 2020. Outro estudo apresentou um NSGA-II híbrido que superou todos os métodos de decomposição em um problema de agendamento M. Rabbani et al., 2017.

Funcionamento do NSGA-II

Passos do NSGA-II:

  1. Inicialização: Gere uma população inicial aleatoriamente e calcule a aptidão (fitness) de cada indivíduo.

  2. Classificação: Classifique a população com base na dominância. Aqueles que não são dominados por outros são colocados na primeira frente, os próximos na segunda frente e assim por diante.

  3. Cálculo da Distância de Aglomeração: Para cada frente, calcule a distância de aglomeração para cada indivíduo. Isso ajuda a manter a diversidade na população.

  4. Seleção: Use operadores de seleção, como torneio binário, para selecionar pais para cruzamento.

  5. Cruzamento e Mutação: Aplique operadores de cruzamento (crossover) e mutação para gerar descendentes.

  6. Combinação: Combine a população atual com os descendentes gerados.

  7. Seleção da Próxima Geração: Selecione os melhores indivíduos com base na classificação de dominância e distância de aglomeração para formar a próxima geração.

  8. Repetição: Repita os passos de 2 a 7 até que o número máximo de gerações seja atingido ou outro critério de parada seja satisfeito.

Passos e Funcionamento do NSGA-II

Exemplos de aplicação do NSGA-II

 

Considerações finais

  • O NSGA-II é um algoritmo evolutivo robusto e eficiente para otimização multiobjetivo, com uma rica história de desenvolvimento e aplicação em diversos campos.

  • Ele supera muitos de seus predecessores e competidores em termos de velocidade, precisão e diversidade das soluções, embora tenha suas próprias limitações e desafios.

  • Histórico e Evolução: Desde sua introdução em 1995, o NSGA e sua versão melhorada, NSGA-II, têm sido referências em otimização multiobjetivo.

  • Funcionamento: O NSGA-II combina classificação baseada em dominância, cálculo de distância de aglomeração e operadores genéticos tradicionais para encontrar soluções ótimas.

  • Aplicações: O NSGA-II tem sido aplicado em uma variedade de campos, desde engenharia até economia, demonstrando sua versatilidade e eficácia.

  • O NSGA-II continua sendo uma ferramenta valiosa para pesquisadores e profissionais que lidam com problemas de otimização multiobjetivo. Seu legado e impacto na comunidade científica são inegáveis.

  • Como em qualquer ferramenta ou método, é essencial entender suas forças e limitações, adaptando-o conforme necessário para atender às demandas específicas de cada problema.

Referências


Deb, K. (1995). Multi-objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 7(3), 205-230. [Link]

Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II. [Link]

Drezewski, Rafal & Doroz, Krzysztof. (2017). An Agent-Based Co-Evolutionary Multi-Objective Algorithm for Portfolio Optimization. Symmetry. 9. 168. [Link]

Qu, B., Zhou, Q., Xiao, J., & Suganthan, P. N. (2017). Large-scale portfolio optimization using multiobjective evolutionary algorithms and preselection methods. Mathematical Problems in Engineering, 2017, 1-14. [Link]

Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-Report 103. [Link]

Zhang, Q., Li, H. (2007). MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712-731. [Link]

Knowles, J., & Corne, D. (2000). Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy. Evolutionary Computation, 8(2), 149-172. [Link]

Sierra, M. R., & Coello, C. A. C. (2005). Improving PSO-based multi-objective optimization using crowding, mutation and ε-dominance. In Proceedings of the 3rd international conference on Evolutionary Multi-Criterion Optimization (pp. 505-519). Springer, Berlin, Heidelberg. [Link]

Chang, Yuqing & Bouzarkouna, Zyed & Devegowda, Deepak. (2015). Multi-objective optimization for rapid and robust optimal oilfield development under geological uncertainty. Computational Geosciences. 19. 933-950. [Link]

Filho, Rui & Vergilio, Silvia. (2016). A multi-objective test data generation approach for mutation testing of feature models. Journal of Software Engineering Research and Development. 4. [Link]

Obrigado!

 

Rodrigo Hermont Ozon

\(\Rightarrow\) Ao professor Roberto Zanetti Freire pela oportunidade de contribuir com os novos pesquisadores;

\(\Rightarrow\) Agradecimentos aos pesquisadores do PPGEPS/PUCPR, aos ouvintes e em especial ao meu orientador, prof. Dr. Gilberto Reynoso Meza

– PPGEPS/UTFPR , Oct 6th 2023 – [ Rodrigo Hermont Ozon – PhD Researcher at PPGEPS/PUCPR]