Otimização de partículas

Universidade de São Paulo
Instituto de Ciências Matemáticas e de Computação

Otimização por Enxame de Partículas (PSO) e
Otimização por Colônias de Formigas (ASO) aplicadas ao Problema do Caixeiro Viajante (TSP)

Aluno: Fabricio Aparecido Breve
Prof.: Dr. André Ponce de Leon F. de Carvalho

São Carlos – São Paulo
Maio / 2007

Resumo
Este trabalho mostra a aplicação de dois algoritmos distintos: otimização por enxame de partículas (PSO) e Otimização por colônias de formigas (ASO) para resolver o tradicional problema do caixeiro viajante (TSP).

Introdução
Otimização por enxame de partículas (PSO) é uma forma de inteligência de enxames. Imagine um enxame de insetos, se um vê um caminho desejável para seguir (para obter comida, proteção, etc.) o restante dos elementos do enxame conseguirão segui-lo rapidamente, mesmo que estejam do outro lado do enxame. Por outro lado, para facilitar a exploração do espaço, tipicamente cada partícula deve ter um certo nível de aleatoriedade em seu movimento, para que o movimento do enxame tenha uma certa capacidade exploratória, ou seja, cada partícula deve ser influenciada pelo restante do enxame, mas também deve explorar independentemente até certa extensão.
As partículas modeladas em um espaço multidimensional tem posição e velocidade. Estas partículas estão voando no hiper-espaço e tem essencialmente duas capacidades: memorizar sua melhor posição e saber a melhor posição do enxame. Membros do enxame comunicam suas boas posições para os outros que ajustam suas própria posições e velocidades de acordo com essas boas posições.
Otimização por colônia de formigas (ACO), é uma técnica probabilística para resolver problemas computacionais, os quais podem ser reduzidos a encontrar bons caminhos em grafos. Esta técnica é inspirada no comportamento de formigas em procurar caminhos da colônia até fontes de alimento.
No mundo real, formigas inicialmente andam aleatoriamente em busca de comida, e quando