Este repositório destina-se a uma prova de conceito (poc) de algoritmos genéticos, focalizando a criação de possíveis itinerários turísticos nas capitais brasileiras.
O desafio do caixeiro viajante (tsp) é um dos problemas clássicos frequentemente abordados por algoritmos genéticos.
Se trata de uma pessoa que busca vender seus produtos ao percorrer cidades, enfrentando algumas restrições notáveis:
-
Visitar todas as cidades e retornar à origem.
-
Evitar revisitar uma cidade já visitada.
-
Percorrer o caminho mais curto possível.
Este é reconhecido como um problema de np-difícil/complexo, com uma complexidade de n(!nC). Ao adicionar novos caminhos, as possibilidades de rotas aumentam exponencialmente. Para abordar as 26 capitais e o Distrito Federal, junto com o ponto de origem teríamos n(!28), totalizando 304.888.344.611.713.860.501.504.000.000 (trezentos e quatro octilhões, oitocentos e oitenta e oito setilhões, trezentos e quarenta e quatro sextilhões, seiscentos e onze quintilhões, setecentos e treze quatrilhões, oitocentos e sessenta trilhões, quinhentos e um bilhões, quinhentos e quatro milhões) possibilidades. Algoritmos de estruturas de dados convencionais enfrentariam desafios ao analisar e calcular todas essas rotas em tempo hábil.
A aplicação de algoritmos genéticos nesse cenário permite resolver o problema de forma eficaz, encontrando uma solução válida em pouco tempo, sem recorrer à força bruta em todos os casos.
Este repositório servirá como base para a criação de uma prova de conceito (poc) de algoritmos genéticos, implementando gradualmente o caixeiro viajante em python.
A intenção é abordar conceitos teóricos, como elitismo, seleção de pais, cruzamentos, mutações e suas respectivas taxas. Além disso, exploraremos características específicas do problema em questão.
Além da implementação, pretendo buscar maneiras de criar uma interface iterativa amigável para visualizar os dados usando o google maps. A rota gerada pelo algoritmo genético será representada através de pontos que simbolizam as cidades e linhas que denotam as rotas. Isso não apenas enriquecerá a experiência visual, mas também proporcionará uma compreensão mais profunda da teoria estudada.
A permissão é concedida por meio deste, gratuitamente, a qualquer pessoa que obtenha uma cópia deste software e dos arquivos de documentação associados (o "Software"), para lidar com o Software sem restrições, incluindo, sem limitação, os direitos de usar, copiar, modificar, mesclar, publicar, distribuir, sublicenciar e/ou vender cópias do Software, e permitir que as pessoas a quem o Software é fornecido o façam, sujeitas às seguintes condições:
O aviso de direitos autorais acima e este aviso de permissão devem ser incluídos em todas as cópias ou partes substanciais do Software.
O software é fornecido "como está", sem garantia de qualquer tipo, expressa ou implícita, incluindo, mas não se limitando a garantias de comercialização, adequação a uma finalidade específica e não violação. Em nenhum caso os autores ou detentores de direitos autorais serão responsáveis por qualquer reclamação, danos ou outra responsabilidade, quer em uma ação contratual, delitual ou de outra forma, decorrente de, ou em conexão com, o software ou o uso ou outras operações no software.