quarta-feira, 29 de abril de 2015

[Python] - Otimização por Colônia de Formigas (Ant Colony Optimization) aplicado ao problema do Caixeiro Viajante (Traveling Salesman Problem)

Olá pessoal, nesse post iremos colocar uma implementação nossa para resolver o problema do caixeiro viajante (traveling salesman problem - TSP) utilizando a heurística de otimização por colônia de formigas (ant colony optimization - ACO).

O problema do caixeiro é bem simples, você tem que visitar todas os vértices de um grafo e só pode passar por cada vértice uma única vez. Qual o menor caminho?

Esse problema é de fácil entendimento (nós já abordamos ele em outros posts), mas a sua complexidade cresce absurdamente ao aumentar o número de vértices.

Existem várias heurísticas que você pode utilizar para atacar esse problema, temos algoritmos genéticos, otimização por enxame de partículas etc.

Nesse post iremos utilizar a heurística da colônia de formigas (ACO) para resolver o problema do caixeiro viajante.

Heurísticas não garantem a solução ótima, mas se for bem implementada e com parâmetros bem ajustados, consegue-se bons resultados.

A implementação foi feita em Python, as referências e o código estão no Github, segue o endereço do projeto:


Esperamos que ajude quem está interessado em saber mais sobre heurísticas, computação evolutiva, caixeiro viajante enfim. Deixem seu feedback, até a próxima!


Nenhum comentário: