Nuvem de Partículas
PSO - Particle Swarm Optimization (1995)

Desenvolvida por James Kennedy (psicólogo)
e Russell Eberhart (engenheiro), com base no
comportamento de pássaros em revoadas
modelado pelo biólogo Frank Heppner.

Inspirado no comportamento e na dinâmica
dos movimentos dos pássaros, insetos e
peixes;

Originalmente desenvolvido para problemas
de otimização com variáveis contínuas;

Desempenho similar ao dos Algoritmos
Genéticos;
Otimização Nuvem de
Partículas
Otimização Nuvem de
Partículas
PSO

Elementos do algoritmo:

A : população de agentes.

xi : posição do agente ai no espaço de soluções.

f : função de avaliação.

vi : velocidade do agente ai.

V(ai) : conjunto fixo de vizinhos do agente ai.

Todos os agentes estão conectados, direta ou
indiretamente
Otimização Nuvem de
Partículas

Vantagens







Insensível a mudança de escala das variáveis;
Implementação simples;
Adaptável a computadores paralelos;
Não requer cálculo de derivadas;
Poucos parâmetros para serem definidos pelo usuário;
Bom para encontrar o mínimo global;
Desvantagens

Rápido para localizar a bacia de atração das boas
soluções, mas lento no ajuste fino da solução (como nos
algoritmos genéticos).
 Baseia-se no comportamento social dos pássaros em
revoadas, cardumes de peixes e enxames de abelhas
 Algoritmicamente, tem-se um conjunto de partículas que
percorrem o espaço de busca apresentando comportamentos
aleatórios em relação à individualidade e à sociabilidade
 A individualidade de uma partícula está relacionada à ênfase
dada, em seus movimentos, à melhor solução já encontrada por
ela mesma, enquanto sua sociabilidade reflete o grau de
importância dado por ela à melhor solução já encontrada por
seus vizinhos
 O conceito de vizinhança em PSO não é o mesmo utilizado
pelas meta-heurísticas de busca por entornos, pois cada
partícula, associada a uma solução que evolui, é vizinha de um
conjunto de partículas que nunca é alterado
 A estrutura de vizinhanças é construída de forma que os
progressos obtidos em cada região tenham influência,
potencialmente, em todas as partículas
Aplicações de PSO


Aplicações comuns:

Evolução de redes neurais artificiais

Extração de regras de RNAs

Escalonamento de tarefas (Multi-objective Job shop scheduling)

Roteamento de veículos (Capacitated Vehicle Routing)
Aplicação recente:


Bandwidth Minimization Problem - BMP (2003).
Algumas aplicações recentes (2004):

Caminho ótimo para operações de perfuração automatizadas.

Mineração de dados para tarefas de classificação.

Posicionamento de bases em computação móvel.

Aproximação poligonal ótima de curvas digitais.
Imitando a natureza
Separação: usada para evitar
aglomerações de partículas
Alinhamento: encaminhar a
busca para a partícula
“representante” do grupo
Coesão: uma partícula
movimenta-se na “média”
dos seus vizinhos

PSO é um método baseado em população, como o Algoritmo
Genético

Entretanto, o conceito básico é cooperação em vez da
rivalidade

Apesar da semelhança com AG, esta técnica não usa
operadores genéticos (crossover, mutação, etc)

Uma partícula movimenta-se com velocidade

Usando a própria experiência

Além da experiência de todas as partículas

A idéia é similar ao bando de pássaros (ou cardume de peixes
ou enxame de abelhas) procurando comida

Habilidade de troca de informações entre vizinhos

Habilidade de memorizar uma posição anterior

Habilidade de usar informações para tomada de decisões
Notação
Notação
Atualização da velocidade
Três termos definem uma nova velocidade para
uma partícula:
 Força a partícula a mover-se na
mesma direção
 Tendência para seguir a própria
direção com a mesma
1. Termo de inércia
velocidade
 Melhora o indivíduo
 Força a partícula a voltar a uma
2. Termo cognitivo
posição anterior que seja
melhor do que a atual
 Tendência conservativa
3. Termo de
 Força a partícula a seguir a
direção de seus melhores
aprendizado social
vizinhos
 Como em todo rebanho, mas
seguindo os melhores
Idéia básica: comportamento
cognitivo
Qual a melhor
direção?
comida: 8
comida: 5
comida: 10
Um indivíduo lembra do conhecimento passado
Idéia básica: comportamento
social
pássaro 1
Qual a
melhor
direção?
pássaro 3
comida: 2
comida: 1
pássaro 2
comida: 3
pássaro 4
comida: 4
Um indivíduo adquire conhecimento dos
demais membros do grupo
Atualização de velocidade e posição
PSO tradicional – Eberhart, R. C. and Kennedy, J. (1995)
Para cada agente ai :
inércia
cognitivo
aprendizado social
vi = wvi + η1.rand().(pbesti - xi) + η2.rand().(gbesti - xi)
xi = xi + vi
onde:
pbesti é a melhor posição em que a partícula ai já esteve
gbesti é a melhor posição em que algum vizinho de ai já
esteve.
w é o peso de inércia

http://www.macs.hw.ac.uk/~dwcorne/mypages/a
pps/pso.html
Melhoramentos e Variantes

Redução linear da ponderação de inércia;

Fator de constrição;

Modelos com Vizinhanças.
Fator de Constrição

Fator de Constrição foi introduzido por Clerc e Kennedy
(2002).

Tornou-se muito popular nos algoritmos recentes de
nuvem de partícula.
Modelos com Vizinhanças

A cada partícula é atribuído uma vizinhança;

As vizinhanças tornam mais lento a transmissão da
melhor posição atráves da nuvem;

Converge mais lentamente, mas melhora a
diversificação.
Armadilhas da técnica PSO

As partículas tendem a se agrupar, ou seja,
devido a uma convergência rápida demais,
a solução fica presa em um ponto ótimo
local

O movimento de alguma partícula pode
ser levado a um ponto de solução
infactível

As partículas poder mapear um espaço
inapropriado de soluções factíveis
Problema: Partículas tendem a se agrupar, reduzindo a
capacidade de movimentos da nuvem para soluções melhores.
Solução: reiniciar algumas partículas em novas posições, as
quais podem mover-se para áreas com soluções melhores. As
demais partículas podem mover-se para estas áreas.
!
Início
Inicialize as partículas em posições
aleatórias e velocidades nulas
Calcule os valores fitness
SIM
Achou um critério
de busca local?
Busca
local
NÃO
Compare/atualize os valores dos
fitness pbest e gbest
Critério de
parada?
SIM
Fim
NÃO
Atualize velocidades e
posições das partículas
NÃO
Critério de
reinicialização?
SIM
Reinicialize algumas
partículas
Restrições da técnica

Mapeamento das partículas em direção às soluções

Dimensões

Função de fitness

Número de partículas

Estrutura do aprendizado social

Valores dos parâmetros (1 2 w)

Como eliminar partículas em regiões infactíveis

Critério de parada
Principais elementos

Intensificação é a exploração das soluções encontradas
em procuras anteriores

Diversificação é a busca por soluções ainda não visitadas
Intensificação
Encontra rapidamente a
melhor solução de uma
região
Encontrar
o equilíbrio
Diversificação
Identifica rapidamente
regiões com potencial para
melhores soluções
Exemplo
Utilizar o algoritmo de PSO para encontrar pontos de mínimo
da função abaixo, usando as 3 partículas dadas abaixo:
partículas
x
1 2,5
2 5,6
3 10,5
v
1
2
3
1
600
0
0
0
500
400
300
200
Minimizar
f(x)=(x-4)^2-(x-8)^3+5
100
0
-100 0
1
2
3
4
5
6
7
8
9 10 11 12 13
pso
Pesquisas atuais de PSO
 PSO com termos sociais múltiplos
 Diferentes índices de medidas para PSO
 Partículas heterogêneas
 PSO hierárquico
 PSO para o problema de escalonamento de tarefas(JSS)
 PSO para roteamento de veículos
 PSO para extração de regras de RNA
 PSO para problemas com restrições de recursos
Adaptações da PSO para o PCV
[M. Clerc, 2004; T. R. Machado e H. S. Lopes, 2005]

Partículas

Em PCV procuramos ciclos com N+1 vértices. Logo uma partícula
consiste em um ciclo com as cidades do PCV:
x = (n1, n2, …, nN, nN+1)


Esta partícula somente é aceita se todos os arcos (ni, ni+1) existem
Função de fitness
N
c

Velocidade

i 1
ni , ni 1
Definir um operador v que quando aplicado a uma partícula retorna
uma outra posição.
 Definimos então uma lista de transposições de elementos da
partícula. Estas transposições são trocas de 2 a 2:
v = {(ik, jk)}, onde ik, jk  {1, 2,…, N}
que significa: troque os elementos (i1, j1), depois (i2, j2), até k.
 Movimento
 O movimento da partícula é obtido aplicando-se a velocidade à
partícula: x’=x + v.
Exemplo: x=(1, 2, 3, 4, 5, 1), v={(1, 2), (2, 3)}
com a primeira troca (1, 2), temos: x’=(2, 1, 3, 4, 5, 2)
com a segunda troca (2, 3), temos x’=(3, 1, 2, 4, 5, 3)
 Subtração
 A diferença xi – xj é definida como a velocidade que deve ser aplicada
na posição xj para obter a posição xi. Quando xi = xj, temos v = 0
 Adição
 O resultado da soma de duas velocidade vi + vj é a lista de
transposições primeiro de vi, depois de vj.
 Multiplicação de escalar por vetor
 quando c = 0, temos cv =
 quando c  [0, 1], trunca-se v.
Exemplo:
c = 0,6; e v = {(1, 2), (3, 5), (17, 23), (7, 3), (8, 19)}
logo, cv = {(1, 2), (3, 5), (17, 23)}
 quando c > 1, defina c = k + c’, onde k  N, e c’ [0, 1].
logo, cv = v + v +…+ v + c’v
k vezes
vi = wvi + η1.rand().(pbesti - xi) + η2.rand().(pgbesti xi)
xi = xi + vi
PSO com estruturas de
múltiplos grupos sociais
[Pongchairerks, Kachitvichyanukul, 2006]
A combinação dos vetores pbest, pgbest, lbest e nbest
direciona uma partícula para melhores posições do que
um PSO padrão.
pbest
PSO padrão
pbest
PSO com múltiplas
estruturas sociais
pgbest
pgbest
nbest
lbest
Mais aplicações


PSO trata-se de uma técnica atrativa, porque é:

computacionamente “barata”

robusta

simples
Outras aplicações:

Controle de veículos por controle remoto

Controle para detectar e eliminar tumores

O filme da Disney “O Rei Leão” foi o primeiro a usar tecnologia de
nuvem de partículas para fazer a cena da debandada de pássaros. O
filme da New Line Cinema “O Senhor dos Anéis” também utilizou
técnicas semelhantes nas cenas de batalhas.

Réplica de dados em grade