Otimização por Colônia de Formigas (Ant Colony Optimization - ACO) aplicado ao problema do caixeiro viajante (Traveling Salesman Problem - TSP).
O projeto contém apenas um arquivo de código chamado "tsp_aco.py". Foi implementado em Python, funciona nas versões do Python 2.x e 3.x.
Esse código utiliza a heurística Colônia de Formigas para resolver o problema do Caixeiro Viajante que é um problema onde não se conhece um algoritmo polinomial que obtenha a solução ótima.
O uso de heurísticas é de suma importância para atacar esses problemas. A heurística não garante uma solução ótima, mas, se tiver bem implementada e com parâmetros bem ajustados, garante uma boa solução.
A pasta "referências" contém as referências que foram utilizadas como base para a implementação.
O arquivo "grafo.png" é a matriz de distâncias que foi utilizada para testar a implementação.
Um dos menores caminhos para esse grafo é:
7 -> 3 -> 2 -> 5 -> 1 -> 8 -> 4 -> 6 | custo: 140
1 representa o "A", 2 representa o "B" e assim por diante.
Alguns parâmetros podem ser ajustados tais como a quantidade de formigas (recomendável ser igual ao número de vértices), o "alfa" que é a importância do feromônio, "beta" que é a importância heurística, quantidade de iterações e a taxa de evaporação do feromônio. É aconselhável consultar as referências para um melhor entendimento da heurística.
Inicialmente, a quantidade de feromônio depositada nas arestas leva em conta o custo de uma construção gulosa. O artigo descreve bem isso. É feita uma distribuição estratificada das formigas nos vértices.
Quaisquer dúvidas, entre em contato :)