Otimização por Colônia de Formigas Distribuído do Problema do Caixeiro Viajante.

Otimização por Colônia de Formigas Distribuído do Problema do Caixeiro Viajante.

Projeto Sistemas Distribuídos
Luis Fernando Vieira

Introdução

O problema do caixeiro-viajante (PCV), travelling salesman problem (TSP) pertence à categoria NP-Completo que o remete para um campo de complexidade exponencial, isto é, o esforço computacional necessário para a sua resolução cresce exponencialmente com o tamanho do problema sendo considerado O(n!). Assim para instancias grandes determinar a solução ótima desta classe de problemas é praticamente impossível então os métodos de resolução desses tipos de problemas utilizam heurísticas como a otimização por colônia de formigas que, do ponto de vista matemático, não asseguram a obtenção de uma solução ótima porem resolvem o problema com uma solução quase ótima. Porem mesmo com a resolução por heurísticas é possível aumentar o poder computacional para a resolução do problema utilizando vários computadores interligados, ou seja, um sistema distribuído.
O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando em qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.
O algoritmo da otimização da colônia de formigas (ACO, do inglês ant colony optimization algorithm), é uma heurística baseada em probabilidade, criada para solução de problemas computacionais que envolvem procura de caminhos em grafos como o TSP. Este algoritmo foi inspirado na observação do comportamento das formigas ao saírem de sua colônia para encontrar comida.
No mundo real, as formigas andam sem rumo até que, encontrada comida, elas retornam à colônia deixando um rastro de feromônio. Se outras formigas encontram um desses rastros, elas tendem a não seguir mais caminhos aleatórios. Em vez disso, seguem a trilha encontrada, retornando e inclusive enfatizando se acharam alimento.
Com o transcorrer do tempo, entretanto, as trilhas de