Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo

• Ano de defesa: 2017
• Autor(a) principal: Moraes, Deyvid Heric de
• Orientador(a): Sanches, Danilo Sipoli
• Banca de defesa: Sanches, Danilo Sipoli, Constantino, Ademir Aparecido, Rocha, Josimar da Silva
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Tecnológica Federal do Paraná; Cornelio Procopio
• Programa de Pós-Graduação: Programa de Pós-Graduação em Informática
• País: Brasil
• Palavras-chave em Português: Caixeiros-viajantes; Otimização combinatória; Algorítmos computacionais; Traveling sales personnel; Combinatorial optimization; Computer algorithms
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA
• Link de acesso: http://repositorio.utfpr.edu.br/jspui/handle/1/3237

Neste trabalho é apresentada uma nova abordagem de algoritmo evolutivo multiobjetivo, denominado MOEA/NSM (do inglês, Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). O algoritmo preserva em geral, características de um algoritmo evolutivo, concentrando qualidades de outras abordagens de sucesso na literatura em uma única abordagem, para que elas trabalhem em conjunto, por meio de subpopulações. O objetivo do estudo foi combinar as principais características dos algoritmos NSGA-II, SPEA2 e MOEA/D, e incluir ainda uma técnica de busca local para melhorar a busca no espaço de objetivos. O algoritmo MOEA/NSM foi comparado às demais abordagens clássicas utilizando 9 datasets para o problema do caixeiro viajante biobjetivo. Além disso, foram realizados experimentos aplicando também a busca local nas abordagens clássicas, resultando em considerável melhora nos resultados para esses algoritmos. A partir das fronteiras de Pareto resultantes dos experimentos, foram aplicadas as métricas de avaliação por Hipervolume, Epsilon (ε), R2, EAF, além do teste de hipótese estatístico Shapiro-Wilk. Os resultados apontaram um melhor desempenho do MOEA/NSM em relação aos demais, mesmo aplicando a busca local nas outras abordagens. Nesse sentido, o MOEA/NSM pode ser considerado um algoritmo que consegue encontrar soluções não denominadas de qualidade, tanto quanto os algoritmos clássicos da literatura.