Otimização por Nuvem de
Partículas
Maurice Cler
Traduzido por
A. Pozo
Os
“inventores” (1)
Russell
Eberhart
[email protected]
Os “inventores” (2)
James
Kennedy
[email protected]
Parte 1: United we stand
Exemplo de Cooperação
Inicialização. Posições and
velocidades
Vizinhanças
geografica
social
A Vizinhança circular
1
Partícula 1’s 3vizinhos
2
8
3
7
Circulo Virtual
4
6
5
Compromisso Psychosocial
Meu melhor
perf.
pi
Aqui estou!
x
pg
v
A melhor perf.
dos vizinhos
O Histórico Algoritmo
A cada passo t
Para cada partícula
Para cada componente d
vd t  1 
atualize v t 
 d
a
 rand0,   p  x t 
1
i,d
d
velocidade 
 rand0,  2  p g , d  xd t 

então
x(t  1)  xt   vt  1
Proximidade Aleatória
Hyperparallelepipedo => Biased
pi
x
pg
v
Ilustração Animada
Ótimo
Global
Parte 2: Como escolher os
parametros
Tipe 1
v(t  1)   (v(t )   ( p  x(t )))

 x(t  1)  v(t  1)  x(t )
com
  rand(0, 1 )  rand(0,  2 )   '1  '2
p
 '1 pi   ' 2 p g
 '1  ' 2
2

for   4


    2   2  4


else 
Valores usuais:
k=1
=4.1
=> =0.73
Pop.=20
Num. vz=3
Alugmas Funções ...
Griewank
Rastrigin
Rosenbrock
... E alguns resultados
Otimo=0, dimensão=30
Melhores resultados após 40 000 avaliações
30D funções
PSO Tipo
AE.(Angeline 98)
Griewank [±300]
0.003944
0.4033
Rastrigin [±5]
82.95618
46.4689
Rosenbrock [±10] 50.193877
1610.359
Beat the swarm!
Part 3: Por dentro dos
números reais
1
8
0
2
0
1
3
1
2
4
0
2
3
0
5
1
3
4
1
6
4
0
2
2
1
3
3
2
4
Bingo!
8
Requisitos Mínimos
( x, x' )  H  H ,  f x   f x'   f x   f x'
Operadores Algébricos

coefficient , velocity 
velocity

velocity, velocity 
velocity

 position, position 
velocity

 position, velocity 
position
Fifty-fifty


xi  1...N

i  j  xi  x j
D / 2
D

xi
 xi 

 1
D / 21
 

N=100, D=20. Espaço de busca: [1,N]D
105 avaliações:
63+90+16+54+71+20+23+60+38+15
=
12+48+13+51+36+42+86+26+57+79 (=450)

Knapsack


x  1...N
 i

i  j  xi  x j



xi  S
iI , I  D, I 1, N 

 

N=100, D=10, S=100,
870 avaliações:
run 1 => (9, 14, 18, 1, 16, 5, 6, 2, 12, 17)
run 2 => (29, 3, 16, 4, 1, 2, 6, 8, 26, 5)
Problema do Grafo
1
2
0
+
2
5
5
3
5
1
=
-1
-1
0
-3
2
1
1
4
1
5
4
5
1
2
5
O Caixeiro Viajante
Exemplo de posição: X=(5,3,4,1,2,6)
Examplo de velocidade: v=((5,3),(2,5),(3,1))
Parte 5: Aplicações
Reais(híbrido)
Diagnostico Medico
Misturadoras industrias
Geradores Elétricos
Veículo Elétrico
Aplicações Reais
Cockshott A. R., Hartman B. E., "Improving the fermentation medium for
Echinocandin B production. Part II: Particle swarm optimization", Process
biochemistry, vol. 36, 2001, p. 661-669.
He Z., Wei C., Yang L., Gao X., Yao S., Eberhart R. C., Shi Y., "Extracting
Rules from Fuzzy Neural Network by Particle Swarm Optimization", IEEE
International Conference on Evolutionary Computation, Anchorage, Alaska,
USA, 1998.
Secrest B. R., Traveling Salesman Problem for Surveillance Mission using
Particle Swarm Optimization, AFIT/GCE/ENG/01M-03, Air Force Institute of
Technology, 2001.
Yoshida H., Kawata K., Fukuyama Y., "A Particle Swarm Optimization for
Reactive Power and Voltage Control considering Voltage Security
Assessment", IEEE Trans. on Power Systems, vol. 15, 2001, p. 1232-1239.
Para conhecer mais
THE site:
Particle Swarm Central, http://www.particleswarm.net
Self advert
Clerc M., Kennedy J., "The Particle Swarm-Explosion,
Stability, and Convergence in a Multidimensional
Somplex space", IEEE Transaction on Evolutionary
Computation, 2002,vol. 6, p. 58-73.
Clerc M., "L'optimisation par essaim particulaire.
Principes et pratique", Hermès, Techniques et
Science de l'Informatique, 2002.