Ú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.