Este projeto aborda uma solução computacional para o clássico Problema do Caixeiro Viajante (PCV) utilizando algoritmos genéticos, uma subárea da computação evolutiva. O objetivo é encontrar a rota mais curta que permite a um caixeiro visitar uma série de cidades uma única vez e retornar à cidade de origem, minimizando o custo total de viagem.
O Problema do Caixeiro Viajante é um problema NP-difícil na área de otimização combinatória, significando que não existe um algoritmo conhecido que o resolva em tempo polinomial. Assim, abordagens heurísticas como algoritmos genéticos se mostram valiosas, oferecendo soluções aproximadas em tempo razoável.
- Python: Linguagem de programação de alto nível, dinâmica e interpretada.
- DEAP (Distributed Evolutionary Algorithms in Python): Um framework de computação evolucionária que facilita a implementação de algoritmos evolutivos.
O algoritmo inicia com uma população de soluções aleatórias (rotas). Em cada geração, indivíduos (rotas) são selecionados com base em sua aptidão (distância total da rota) e combinados através de operações de cruzamento e mutação para formar uma nova geração. Esse processo se repete até que se atinjam critérios de parada pré-definidos, como um número máximo de gerações ou uma solução de aptidão satisfatória.
- Modelagem das Cidades: Utiliza uma representação gráfica onde as cidades são nós e as distâncias entre elas são arestas.
- Seleção: O algoritmo de seleção por torneio escolhe os indivíduos para reprodução.
- Cruzamento: O cruzamento parcialmente combinado (CPM) é utilizado para manter a validade das rotas geradas.
- Mutação: Uma simples troca de índices promove a diversidade genética.
- Avaliação: A função de aptidão avalia a qualidade das soluções baseada na distância total percorrida.
-
Pré-requisitos: Certifique-se de ter Python 3.x instalado em seu sistema.
-
Instale as dependências:
pip install deap numpy- Clone o repositório:
git clone git@github.com:felipeverones/Algoritmo-Genetico.git
cd Algoritmo-Genetico- Execute o script:
python problema_caixeiro_viajante.py- O algoritmo deve convergir para uma solução que representa uma das melhores rotas possíveis dadas as condições iniciais e os parâmetros do algoritmo.
- Estatísticas de execução como a melhor distância encontrada, média e desvio padrão das distâncias das rotas na população final serão apresentadas.
Este projeto demonstra a aplicabilidade e eficácia dos algoritmos genéticos para resolver problemas complexos de otimização, como o Problema do Caixeiro Viajante. Através do uso do DEAP, é possível implementar uma solução robusta e flexível, capaz de encontrar soluções aproximadas para instâncias do problema que seriam inabordáveis por métodos exatos devido à sua complexidade computacional.