Um algoritmo genético com infecção viral para o problema do caixeiro viajante

Resumo

O Problema do Caixeiro Viajante (PCV) é um problema clássico da área de otimização combinatória, NP-árduo, cujo objetivo é encontrar o ciclo hamiltoniano de menor custo em um grafo ponderado. Devido í  sua complexidade computacional, o PCV tem sido amplamente abordado no desenvolvimento de algoritmos aproximativos e metaheurí­sticas. No presente trabalho, é apresentado um Algoritmo Genético (AG) com Infecção Viral para esse problema, no qual, se mostrou com melhor performance e eficiência do que o AG padrão. Para se chegar a essa conclusão foram feitos testes e análises dos resultados com instâncias disponibilizadas na TSPLIB.

Palavras-chave: Problema do Caixeiro Viajante, Algoritmo Genético, Infecção Viral.