Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante

Mostrar outras versões (1)

Due to great difficulty of accurate solution of Combinatorial Optimization Problems, some heuristic methods have been developed and during many years, the analysis of performance of these approaches was not carried through in a systematic way. The proposal of this work is to make a statistical analy...

ver descrição completa

Na minha lista:
Detalhes bibliográficos
Autor principal: Prestes, álvaro Nunes
Outros Autores: Gouvêa, Elizabeth Ferreira
Formato: Dissertação
Idioma:por
Publicado em: Universidade Federal do Rio Grande do Norte
Assuntos:
Otimização
Problemas do caixeiro viajante
Análise experimental
Heurísticas
Optimization
Traveling salesman problem
Experimental analysis
Heuristics
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Endereço do item:https://repositorio.ufrn.br/jspui/handle/123456789/17962
Tags: Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
id ri-123456789-17962
record_format dspace
spelling ri-123456789-179622017-11-04T13:13:46Z Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante Prestes, álvaro Nunes Gouvêa, Elizabeth Ferreira http://lattes.cnpq.br/3479036429463819 http://lattes.cnpq.br/2888641121265608 Ramos, Iloneide Carlos de Oliveira http://lattes.cnpq.br/0613948277011672 Goldbarg, Marco César http://lattes.cnpq.br/1371199678541174 Oliveira, Carla Silva http://lattes.cnpq.br/0691141675196929 Otimização Problemas do caixeiro viajante Análise experimental Heurísticas Optimization Traveling salesman problem Experimental analysis Heuristics CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO Due to great difficulty of accurate solution of Combinatorial Optimization Problems, some heuristic methods have been developed and during many years, the analysis of performance of these approaches was not carried through in a systematic way. The proposal of this work is to make a statistical analysis of heuristic approaches to the Traveling Salesman Problem (TSP). The focus of the analysis is to evaluate the performance of each approach in relation to the necessary computational time until the attainment of the optimal solution for one determined instance of the TSP. Survival Analysis, assisted by methods for the hypothesis test of the equality between survival functions was used. The evaluated approaches were divided in three classes: Lin-Kernighan Algorithms, Evolutionary Algorithms and Particle Swarm Optimization. Beyond those approaches, it was enclosed in the analysis, a memetic algorithm (for symmetric and asymmetric TSP instances) that utilizes the Lin-Kernighan heuristics as its local search procedure Devido à grande dificuldade de solução exata dos Problemas de Otimização Combinatória, vários métodos heurísticos têm sido desenvolvidos e durante muitos anos, a análise de desempenho dessas abordagens não foi realizada de maneira sistemática. A proposta deste trabalho é fazer uma análise estatística de abordagens heurísticas aplicadas ao Problema do Caixeiro Viajante. O foco da análise é avaliar o desempenho de cada abordagem em relação ao tempo computacional necessário até a obtenção da solução ótima para uma determinada instância do PCV. Para essa análise, foi utilizada uma metodologia estatística chamada Análise de Sobrevivência, auxiliada por métodos para o teste da hipótese de igualdade entre funções. Para uma melhor compreensão, as abordagens avaliadas foram divididas em três classes: Algoritmos Lin-Kernighan, Algoritmos Evolucionários e Algoritmos de Otimização por Nuvem de Partículas. Além das abordagens já existentes, foi incluído na análise, um algoritmo memético (para instâncias simétricas e assimétricas do PCV) que utiliza o algoritmo de Lin e Kernighan como procedimento de busca local 2014-12-17T15:47:44Z 2008-02-26 2014-12-17T15:47:44Z 2006-07-27 masterThesis PRESTES, álvaro Nunes. Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante. 2006. 85 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Rio Grande do Norte, Natal, 2006. https://repositorio.ufrn.br/jspui/handle/123456789/17962 por Acesso Aberto application/pdf application/pdf Universidade Federal do Rio Grande do Norte BR UFRN Programa de Pós-Graduação em Sistemas e Computação Ciência da Computação
institution Repositório Institucional
collection RI - UFRN
language por
topic Otimização
Problemas do caixeiro viajante
Análise experimental
Heurísticas
Optimization
Traveling salesman problem
Experimental analysis
Heuristics
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
spellingShingle Otimização
Problemas do caixeiro viajante
Análise experimental
Heurísticas
Optimization
Traveling salesman problem
Experimental analysis
Heuristics
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Prestes, álvaro Nunes
Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante
description Due to great difficulty of accurate solution of Combinatorial Optimization Problems, some heuristic methods have been developed and during many years, the analysis of performance of these approaches was not carried through in a systematic way. The proposal of this work is to make a statistical analysis of heuristic approaches to the Traveling Salesman Problem (TSP). The focus of the analysis is to evaluate the performance of each approach in relation to the necessary computational time until the attainment of the optimal solution for one determined instance of the TSP. Survival Analysis, assisted by methods for the hypothesis test of the equality between survival functions was used. The evaluated approaches were divided in three classes: Lin-Kernighan Algorithms, Evolutionary Algorithms and Particle Swarm Optimization. Beyond those approaches, it was enclosed in the analysis, a memetic algorithm (for symmetric and asymmetric TSP instances) that utilizes the Lin-Kernighan heuristics as its local search procedure
author2 Gouvêa, Elizabeth Ferreira
author_facet Gouvêa, Elizabeth Ferreira
Prestes, álvaro Nunes
format masterThesis
author Prestes, álvaro Nunes
author_sort Prestes, álvaro Nunes
title Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante
title_short Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante
title_full Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante
title_fullStr Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante
title_full_unstemmed Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante
title_sort uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante
publisher Universidade Federal do Rio Grande do Norte
publishDate 2014
url https://repositorio.ufrn.br/jspui/handle/123456789/17962
work_keys_str_mv AT prestesalvaronunes umaanaliseexperimentaldeabordagensheuristicasaplicadasaoproblemadocaixeiroviajante
_version_ 1773966030769487872

Registros relacionados