Imagem da capa

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

This work presents a new approach to the multiobjective evolutionary algorithm, called MOEA/NSM (Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). The algorithm preserves, in general, the characteristics of an evolutionary algorithm, concentrating qualities of ot...

ver descrição completa

Autor principal: Moraes, Deyvid Heric de
Formato: Dissertação
Idioma: Português
Publicado em: Universidade Tecnológica Federal do Paraná 2018
Assuntos:
Caixeiros-viajantes
Otimização combinatória
Algorítmos computacionais
Traveling sales personnel
Combinatorial optimization
Computer algorithms
CNPQ::CIENCIAS EXATAS E DA TERRA
Ciência da Computação
Acesso em linha: http://repositorio.utfpr.edu.br/jspui/handle/1/3237
Tags: Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
id riut-1-3237
recordtype dspace
spelling riut-1-32372018-06-15T20:14:54Z Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo A new approach based on a multiobjective evolutionary algorithm applied to the biobjective traveling salesman problem Moraes, Deyvid Heric de Sanches, Danilo Sipoli http://lattes.cnpq.br/6377657274398145 Sanches, Danilo Sipoli Constantino, Ademir Aparecido Rocha, Josimar da Silva Caixeiros-viajantes Otimização combinatória Algorítmos computacionais Traveling sales personnel Combinatorial optimization Computer algorithms CNPQ::CIENCIAS EXATAS E DA TERRA Ciência da Computação This work presents a new approach to the multiobjective evolutionary algorithm, called MOEA/NSM (Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). The algorithm preserves, in general, the characteristics of an evolutionary algorithm, concentrating qualities of other approaches of success in the literature in a single approach, so that they work together, through subpopulations. The objective of the study was to combine the main characteristics of the NSGA-II, SPEA2 and MOEA/D algorithms, and also to include a local search technique to improve the objective space search. The MOEA/NSM algorithm was compared to the other classical approaches using 9 datasets for the biobjective traveling salesman problem. In addition, experiments were carried out also applying the local search in the classical approaches, resulting in a considerable improvement in the results for these algorithms. From the Pareto frontiers resulting from experiments, we applied the evaluation metrics by Hypervolume, Epsilon (ε), R2, EAF, in addition to the Shapiro-Wilk statistical hypothesis test. The results showed a better performance of the MOEA/NSM in relation to the others, even applying the local search in the others approaches. In this sense, the MOEA/NSM can be considered an algorithm that is able to find solutions not dominated of quality, as much as the classic algorithms of the literature. 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. 2018-06-15T20:14:54Z 2018-06-15T20:14:54Z 2017-08-02 masterThesis MORAES, Deyvid Heric de. Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo. 2017. 102 f. Dissertação (Mestrado em Informática) - Universidade Tecnológica Federal do Paraná, Cornélio Procópio, 2017. http://repositorio.utfpr.edu.br/jspui/handle/1/3237 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Cornelio Procopio Brasil Programa de Pós-Graduação em Informática UTFPR
institution Universidade Tecnológica Federal do Paraná
collection RIUT
language Português
topic Caixeiros-viajantes
Otimização combinatória
Algorítmos computacionais
Traveling sales personnel
Combinatorial optimization
Computer algorithms
CNPQ::CIENCIAS EXATAS E DA TERRA
Ciência da Computação
spellingShingle Caixeiros-viajantes
Otimização combinatória
Algorítmos computacionais
Traveling sales personnel
Combinatorial optimization
Computer algorithms
CNPQ::CIENCIAS EXATAS E DA TERRA
Ciência da Computação
Moraes, Deyvid Heric de
Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo
description This work presents a new approach to the multiobjective evolutionary algorithm, called MOEA/NSM (Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). The algorithm preserves, in general, the characteristics of an evolutionary algorithm, concentrating qualities of other approaches of success in the literature in a single approach, so that they work together, through subpopulations. The objective of the study was to combine the main characteristics of the NSGA-II, SPEA2 and MOEA/D algorithms, and also to include a local search technique to improve the objective space search. The MOEA/NSM algorithm was compared to the other classical approaches using 9 datasets for the biobjective traveling salesman problem. In addition, experiments were carried out also applying the local search in the classical approaches, resulting in a considerable improvement in the results for these algorithms. From the Pareto frontiers resulting from experiments, we applied the evaluation metrics by Hypervolume, Epsilon (ε), R2, EAF, in addition to the Shapiro-Wilk statistical hypothesis test. The results showed a better performance of the MOEA/NSM in relation to the others, even applying the local search in the others approaches. In this sense, the MOEA/NSM can be considered an algorithm that is able to find solutions not dominated of quality, as much as the classic algorithms of the literature.
format Dissertação
author Moraes, Deyvid Heric de
author_sort Moraes, Deyvid Heric de
title Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo
title_short Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo
title_full Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo
title_fullStr Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo
title_full_unstemmed Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo
title_sort uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo
publisher Universidade Tecnológica Federal do Paraná
publishDate 2018
citation MORAES, Deyvid Heric de. Uma nova abordagem baseada em algoritmos evolutivos multiobjetivo aplicado ao problema do caixeiro viajante biobjetivo. 2017. 102 f. Dissertação (Mestrado em Informática) - Universidade Tecnológica Federal do Paraná, Cornélio Procópio, 2017.
url http://repositorio.utfpr.edu.br/jspui/handle/1/3237
_version_ 1805318235428487168
score 10,814766

Registros relacionados