Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/handle/123456789/17962
Title: Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante
Authors: Prestes, álvaro Nunes
Keywords: Otimização;Problemas do caixeiro viajante;Análise experimental;Heurísticas;Optimization;Traveling salesman problem;Experimental analysis;Heuristics
Issue Date: 27-Jul-2006
Publisher: Universidade Federal do Rio Grande do Norte
Citation: 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.
Portuguese Abstract: 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
Abstract: 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
URI: https://repositorio.ufrn.br/jspui/handle/123456789/17962
Appears in Collections:PPGSC - Mestrado em Sistemas e Computação

Files in This Item:
File Description SizeFormat 
AlvaroNP.pdf751.58 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.