Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/261832
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Algoritmo memetico para o problema do caixeiro viajante assimetrico como parte de um framework para algoritmos evolutivos
Author: Buriol, Luciana Salete
Advisor: França, Paulo Morelato, 1949-
Abstract: Resumo: Dentre a gama de técnicas heurísticas e exatas existentes para a resolução de problemas combinatórios, os algoritmos populacionais genéticos e meméticos têm se destacado devido a sua boa performance. Em especial, os algoritmos meméticos podem ser considerados atualmente como uma das técnicas melhores sucedidas para a resolução de vários problemas combinatórios, dentre eles, o problema do caixeiro viajante. Nesta dissertação será apresentado um algoritmo memético aplicado ao problema do caixeiro viajante assimétrico, com a proposta de uma nova busca local: Recursive Arc Insertion. Os resultados computacionais considerando as 27 instâncias assimétricas da TSPLIB são apresentados, analisados e comparados com resultados obtidos por outros métodos propostos para o problema. O mesmo algoritmo é também aplicado a 32 outras instâncias assimétricas e a 30 instâncias reduzidas do problema de ciclos hamiltonianos não direcionados. Um framework para algoritmos evolutivos é apresentado, já incluindo o algoritmo memético implementado e a redução de instâncias do problema de ciclos hamiltonianos não direcionados para o problema do caixeiro viajante simétrico. Além disso, dois geradores portáveis de instâncias com solução ótima conhecida são descritos: um para o problema do caixeiro viajante assimétrico e outro para o problema de ciclos hamiltonianos

Abstract: Among the range of heuristic and exact techniques for solving combinatorial problems, the genetic and memetic populational algorithms play an important role due to their good performance. In special, the memetic algorithms can be considered current1y as one of the best techniques to solve several combinatorial problems, especially, the traveling salesman problem. In this dissertation a memetic algorithm applied to the asymmetric traveling salesman problem is developed, and a new local search is proposed: Recursive Are Insertion. The computational results considering the 27 asymmetric instances from TSPLIB are presented, analyzed and compared with results attained by other methods recent1y published. The same algorithm is also applied to 32 other asymmetric instances and to 30 reduced instances from undirect hamiltonian cycle problem. A framework for evolutionary algorithms is also presented, including the memetic algorithm implemented and the codes which performs a reduction from the undirect hamiltonian cycle problem to the symmetric traveling salesman problem. Besides, two portable instances generators with a known optimal solution are described: one for asymmetric traveling salesman problem and other for hamiltonian cycle problem
Subject: Framework (Programa de computador)
Algoritmos genéticos
Problema do caixeiro viajante
Geradores (Programas de computador)
Language: Português
Editor: [s.n.]
Date Issue: 2000
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Buriol_LucianaSalete_M.pdf8.39 MBAdobe PDFView/Open


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