Otimização por enxame de partículas – PSO

Otimização por enxame de partículas (do ingês: Particle Swarm Optmization, abreviado por PSO) é um algoritmo heurístico (assim como o DE) baseado no comportamento social de um bando de pássaros. O método foi proposto por Eberhart e Kennedy em 1995 [1], tem como objetivo buscar a solução ótima, em um espaço de busca, através da troca de informações entre indivíduos de uma população determinando qual trajetória cada um deles deverá tomar no espaço de busca (veja o post sobre otimização).

No PSO, as partículas são os indivíduos da população. Fazendo uma analogia, são os pássaros da de um bando. Esses pássaros exploram uma região, determinado pela função objetivo (ou fitness), a fim de encontrar a solução ótima para o problema. A posição da melhor partícula da população será a melhor posição individual.

 

espbirds

Figura 1: analogia de um bando de pássaros em um espaço de busca de 3D. Considerando um problema de maximização, o pássaro azul é a partícula de solução ótima do problema.

Segundo Eberhart e Shi (2011), a grande vantagen de utilizar o PSO é a sua fácil implementação, usando somente estruturas primitivas e operadores matemáticos sem grande custo computacional. Obviamente, como toda heurística, o PSO não garante a solução ótima e é comum o método cair em mínimos locais. Por conta disso, existem diversas modificações no algoritmo canônico do PSO (mas nenhuma garante o ótimo). A versão apresentada a seguir é o algoritmo padrão. Antes de iniciar o algoritmo,  como já mencionado, o PSO também é baseado em população de indivíduos. Esse conceito já foi introduzido no post relacionado ao algoritmo de otimização DE, portanto, caso não conheça esse conceito de uma olhada no segundo parágrafo do link do post.

O algoritmo do PSO

O algoritmo do PSO é simples e são necessários poucos parâmetros para ajustes. O primeiro dele é o tamanho da população. Normalmente é utilizado uma população 10x a dimensão do problema, por exemplo, se estivermos otimizando a curva da Figura 1, uma boa escolha da população será 30, pois a função a ser otimizada possui 3 dimensões, (x,y,z).

topologiasPSO

Figura 2: topologias do PSO

Existem duas formas básicas de organizar a população. Essa formas são conhecidas como topologia do algoritmo e são elas: topologia global e topologia local, como mostra a Figura 2a e 2b, respectivamente. Na topologia global, todas as partículas, representadas pelas bolinhas da figura, possuem informações sobre todas as demais. Já na topologia local, uma partícula só possui informações de sua vizinha esquerda e direita. A escolha da topologia pode evitar que o algoritmo caia em mínimos locais. Por exemplo, se a função a ser otimizada é multimodal, ou seja, possui muitos máximos e/ou mínimos, uma topologia global pode convergir para um mínima/máximo local de maneira mais fácil do que a topologia local. Pode ser que agora você não tenha entendido esse conceito, mas tudo vai ficar mais claro a seguir, no qual apresentamos a equação que rege o PSO.

Bom, sabemos que o PSO busca a solução ótima alterando as trajetórias dos indivíduos de sua população. Para fazer isso o algoritmo atualiza a velocidade e a posição de cada partícula. Considere uma população com K partículas. As variáveis v_k e x_k serão a velocidade e posição da particula k , respectivamente. A velocidade e posição de cada partícula, deve ser atualizada de acordo com as equações:

   v_{k+1} = wv_k +c_1r_1 (p_{best_k}-x_k) + c_2r_2 (g_{best} - x_k)   \\  \\   x_{k+1} = x_{k} + v_{k}

 

A variáveis v_{k+1} e x_{k+1} serão, respectivamente, a velocidade e a posição atualizada da partícula de acordo com:

  • w : coeficiente de inércia.
  • p_{best_k}: melhor posição conhecida da partícula k
  • g_{best}: melhor posição conhecida dentre todas as partículas
  • c_1 e c_2: constantes de aceleração referentes ao melhor individual e global, respectivamente.
  • r_1r_2: números aleatórios extraídos do intervalo [0,1]

Os valores das constantes são escolhidos de maneira empírica, de acordo com o problema em questão. Segundo [1] bons valores a serem escolhidos são: c_1 e c_2 iguais a 2.05 e w igual a 0.5, mas nada impede de tentar outros. As variáveis aleatórias r_1 e $latex r_2, deverão ser extraídas de uma distribuição uniforme e são atualizadas a cada cálculo de velocidade da população. Obviamente as melhores posições, individual e global, são obtidas através da função de fitness.

Portanto, o passo a passo do algoritmo PSO será:

  1. Inicializar uma população de K indíviduos de dimensão D . Essa inicialização deve ser uniforme, se o espaço de busca for conhecido. Caso contrário, inicialize aleatoriamente.
  2. Determinar os valores das constantes
  3. Verificar se o critério de parada foi atingido, e esse critério pode ser um valor pré-determinado ou número de iterações. Se sim, finalizar o algoritmo.
  4. Sortear os números aleatórios para r_1r_2
  5. Determinar a melhor posição global e individual
  6. Atualizar a velocidade das particulas
  7. Atualizar as posições das partículas
  8. Voltar no tópico 3

Dado o algoritmos e suas duas simples equações, observamos que o PSO nada mais é do que uma atualização de velocidade e posição no espaço de busca até que uma solução suficientemente boa seja encontrada. Por fim, faço algumas observações:

  • Quanto a função de fitness: obviamente você deve defini-la previamente, ela vai mudar de problema para problema. É ela que vai determinar qual é o seu espaço de busca e o quão difícil ele é. É ela que você deseja otimizar.
  • Quanto a topologia: voltando a discussão de topologia, agora deve ficar claro o porque ela influência no problema. Observe que a versão apresentada utiliza a topologia global, pois todas as partículas são atualizadas a partir da melhor posição global. Isso pode ser ruim, dependendo do problema. Com já disse, se a função a ser otimizada possui muitos máximos e/ou mínimos, pode acontecer de uma partícula cair em um mínimo/máximo local, e influenciar todas as outras a irem para lá. Com isso, o algoritmo terá uma convergência prematura, atrapalhando no desempenho do mesmo. A topologia local ajuda a evitar esse problema, mas a convergência pode ficar mais lenta. Como as partículas possuem a informação de melhor posição apenas de seus vizinhos, o risco delas convergirem para a mesma posição ao mesmo tempo é mínimo.

 

Como de costume, deixo em anexo um código em MATLAB. Para utilizá-lo, basta alterar a função de fitness e suas constantes, caso queira. Faça bom uso e até a próxima.

Download código MATLAB

Referência

[1] Eberhart, R. C. and Kennedy, J. (1995). A new optimizer using particle swarm theory. In Proceedings of the sixth international symposium on micro machine and human science, volume 1, pages 39–43. New York, NY.

Gostou? Então compartilhe!