Problema do Caixeiro Viajante abordado pelo Algoritmo de Evolução Diferencial

Abstract

Os problemas de otimização classificados como N P -hard podem apresentar dificuldades quando são abordados com métodos exatos, especialmente nos casos de dimensões elevadas, uma vez que o tempo computacional necessário para a obtenção do valor ótimo global cresce exponencialmente à medida que os dados de entrada aumentam. Os algoritmos de Evolução Diferencial (ED) são poderosos algoritmos de otimização evolucionária, propostos inicialmente, para problemas em espaços contı́nuos. Recentemente, tem sido propostas adaptações ao seu mecanismo de mutação diferencial para aplicação em problemas combinatórios. Neste trabalho, uma proposta deste tipo de adaptação é apresentada para este algoritmo, para resolver o Problema do Caixeiro Viajante (PCV). O estudo dos PCV’s se relaciona diretamente com problemas organizacionais da sociedade. Testes computacionais foram realizados com instâncias da literatura e os resultados encontrados sugerem que a técnica proposta é promissora e apropriada para a resolução dos problemas abordados.