segunda-feira, 6 de abril de 2015

Problema do Caixeiro Viajante com Otimização por enxame de partículas - Particle Swarm Optimization (PSO)

Olá pessoal, nesse post irei abordar o problema do caixeiro viajante utilizando o algoritmo de otimização por enxame de partículas (particle swam optimization) - PSO.

PSO é um algoritmo de inteligência por enxame inspirado no comportamento dos pássaros, "swarm" significa enxame e coletiva quer dizer "bando".

Cada partícula é uma possível solução para o problema, a partícula seria cada pássaro. Já o espaço de busca é a área sobrevoada pelos pássaros. Os pássaros buscam encontrar por exemplo a comida ou o ninho, no nosso caso é a solução ótima.

O nosso "fitness" é dado pela função que irá avaliar o desempenho das partículas. No caso do caixeiro viajante, o "fitness" é o custo de um percurso (caminho). Para alcançar o alvo, os pássaros fazem uso de suas próprias experiências e da experiência do bando.

A melhor experiência (melhor solução) de cada partícula (pássaro) é guardada numa variável comumente chamada de pbest (experiência individual). A melhor solução encontrada pelo bando é chamada de gbest (experiência coletiva).

Cada partícula possui um vetor de posição associado a ela e um vetor de velocidade que é responsável por guiar as mudanças da posição das partículas.

As partículas (pássaros) ficam voando pelo espaço de busca atualizando suas velocidades de acordo com experiências individuais e coletiva.

O algoritmo é simples e está descrito no link abaixo:


Para aplicar o PSO para resolver o TSP precisamos fazer algumas modificações, é importantíssimo que você leia o seguinte paper que foi por onde me baseei para implementar:

Clique aqui para visualizar o paper

Veja também os slides para fixar as explicações do paper lido anteriormente:

Clique aqui para visualizar os slides

Leia com calma para entender perfeitamente. Apesar do código está comentado, é importante saber a teoria para um melhor entendimento do código. O artigo e os slides são importantíssimos para entender como implementar uma solução para o TSP utilizando PSO.

A primeira coisa a fazer é inicializar randomicamente a população. A cada iteração você irá percorrer todas as partículas do enxame.

Para cada partícula, o gbest (melhor solução do enxame) será comparado à solução da partícula para gerar os operadores de troca (swap operators), a probabilidade de incluir os operadores gerados é dada por beta (é gerado um número randômico entre 0 e 1 e comparado com o beta). A mesma coisa é feita em relação ao pbest, só que a probabilidade de incluir todos os operadores é dada por um alfa (é gerado um número randômico entre 0 e 1 e comparado com o alfa).

A atualização da posição (nova solução) é feita aplicando todos os operadores de troca (swap operators) na solução da partícula.

Por exemplo, digamos que temos um gbest "E":


E = (1,2,3,4)

E temos uma partícula "A" com a solução:

A = (4,2,3,1)

O primeiro elemento da partícula "A" é diferente do primeiro elemento da partícula "E" (4 é diferente de 1), então eu pego o índice do primeiro elemento da partícula "A" com o índice do primeiro elemento da partícula "A" na partícula "E" gerando o operador: (1,4) (índices começando do 1). Vai gerando os operadores quando os elementos forem diferentes na posição.

Se eu gerei o swap operator SO(1,4), então E' fica (trocando o elemento da posição 1 com o elemento da posição 4):

E' = (4,2,3,1)

Isso é o que o paper chama de "subtraction permutation". Perceba que o segundo elemento de "A" ´é igual a E' (2 igual a 2), então não gera operador.

O paper e os slides explicam bem o que é um operador de troca, adição de permutação, subtração de permutação enfim.

Simples não é mesmo? A implementação foi feita em Python, segue o link do repositório:



Nenhum comentário: