Algoritmo memetico para o problema do caixeiro viajante assimetrico como parte de um framework para algoritmos evolutivos

AUTOR(ES)
DATA DE PUBLICAÇÃO

2000

RESUMO

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

ASSUNTO(S)

geradores (programas de computador) framework (programa de computador) problema do caixeiro viajante algoritmos geneticos

ACESSO AO ARTIGO

Documentos Relacionados