|
A. Ciências Exatas e da Terra - 2. Ciência da Computação - 17. Ciência da Computação |
|
UM ALGORITMO GENÉTICO COM INFECÇÃO VIRAL PARA O
PROBLEMA DO CAIXEIRO VIAJANTE |
|
Allison da Costa Batista Guedes 1, Jéssica Neiva De Figueiredo Leite 1 e Dario Jose Aloise 1 |
|
1 - Depto de Informática e Matemática Aplicada - UFRN, UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE - UFRN |
|
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, que se mostrou com melhor performance do que o AG Padrão. Para se
chegar a essa conclusão foram feitos testes com diversas instâncias disponibilizadas na
TSPLIB. |
|
|
|
Trabalho de Iniciação Científica
|
|
Palavras-chave:
Problema do Caixeiro Viajante; Algoritmo Genético; Infecção Viral |
|