Uso de Algoritmo Cultural com uma Nova Abordagem Memética por meio do Simulated Annealing para o Problema do Caixeiro Viajante
Data
2014
Título da Revista
ISSN da Revista
Título de Volume
Editor
INSTITUTO DE TECNOLOGIA
Resumo
O artigo propõe um algoritmo híbrido combinando Algoritmos Culturais (ACs) e Algoritmos Genéticos (AGs), com busca local via simulated annealing e heurísticas 2-opt e 3-opt, para resolver o Problema do Caixeiro Viajante (TSP). O objetivo é superar convergências prematuras e aprisionamentos em ótimos locais, comumente enfrentados por meta-heurísticas tradicionais. Experimentos com instâncias de 442 e 532 cidades demonstraram que a abordagem alcançou soluções próximas ao ótimo conhecido, superando outros métodos da literatura.
Abstract
The paper proposes a hybrid algorithm combining Cultural Algorithms (CAs) and Genetic Algorithms (GAs), with local search via simulated annealing and 2-opt/3-opt heuristics, to solve the Traveling Salesman Problem (TSP). The aim is to overcome premature convergence and local optima traps common in traditional metaheuristics. Experiments with 442 and 532-city instances showed that the approach achieved solutions close to the known optimum, outperforming other methods in the literature.
Descrição
Palavras-chave
Algoritmos Culturais, Algoritmos Genéticos, Simulated Annealing, Problema do Caixeiro Viajante, Computação Memética
Citação
SILVA, Deam J. A.; SILVA, Joaquim A. L.; AFFONSO, Carolina M.; OLIVEIRA, Roberto C. L. Uso de Algoritmo Cultural com uma Nova Abordagem Memética por meio do Simulated Annealing para o Problema do Caixeiro Viajante. Revista SODEBRAS, v.