Sistema Eletrônico de Administração de Conferências, VII CONNEPI - Congresso Norte Nordeste de Pesquisa e Inovação

Tamanho da fonte: 
Um algoritmo memético para a solução do TSP
Tayná Gonçalves, Roberto de Moraes Rego Filho, Omar Andres Carmona Cortes

Última alteração: 2012-08-30

Resumo


O problema do caixeiro viajante é um problema clássico de otimização combinatorial, cuja resolução por busca exaustiva é inviável em alguns casos, como por exemplo, se considerarmos um número grande de cidades. Por ser aplicável a muitos problemas da vida real, o TSP é amplamente estudado e sempre se busca uma abordagem mais eficiente para solucioná-lo. Neste trabalho é proposto um algoritmo memético para solução do TSP. O objetivo é mostrar que o uso de tal algoritmo possibilita encontrar uma solução satisfatório para uma instância do TSP em um tempo aceitável. O algoritmo memético se mostra adequado nessa circunstância pois combina operadores genéticos tradicionais com operadores de busca local, aumentando significativamente a qualidade das soluções. Serão apresentadas comparações entre diferentes combinações de representações de indivíduos e operadores. Ainda,no intuito de comprovar a eficiência do algoritmo proposto, serão apresentados resultados de testes que utilizam uma função de benchmark da conhecida biblioteca TSPLIB.


Texto completo: PDF