Artigo do CV Gen tico

Resolvendo o Problema do Caixeiro Viajante usando um algoritmo genético.

Abstract. This paper explains one of the oldest problems of computing the Traveling Salesman Problem (TSP), which is to visit all the cities of a certain cycle, and return to the starting point in the shortest possible distance. The best way for this problem consists of a thorough implementation of exponential complexity. The solution proposed in this work consists in using a Genetic Algorithm (GA) to find a way acceptable in a reasonable time. As a conclusion it can present the greater number of generations this implicitly linked to a better result, but in a longer run.

Keywords: Genetic Algorithms, Traveling Salesman Problem.
Resumo. Este artigo explica um dos problemas mais antigos da Computação o Problema do Caixeiro Viajante (PCV), que consiste em visitar todas as cidades de um determinado ciclo, e retornar ao ponto inicial na menor distância possível. O melhor caminho para este problema consiste em uma execução exaustiva de complexidade exponencial. A solução proposta neste trabalho consiste em usar de um Algoritmo Genético (AG), para achar um caminho aceitável em um tempo razoável. Como conclusão pode-se apresentar que o maior número de gerações este implicitamente ligado a um melhor resultado, porém em um maior tempo de execução.

Palavras-Chave: Algoritmos Genéticos, Problema do Caixeiro Viajante.
1. Introdução
Neste trabalho vamos explicar um pouco sobre o Problema do Caixeiro Viajante (PVC), e propor uma solução usando um algoritmo genético, onde buscamos uma heurística aceitável para esta aplicação.
O PCV é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando cada uma pelo menos uma vez), retornando à cidade de origem. Ele é um problema de otimização NP-Completo inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os