Otimização por Nuvem de Partículas Maurice Cler Traduzido por A. Pozo

Otimização por Nuvem de Partículas

Maurice Cler

Traduzido por A. Pozo

Os “inventores” (1)

Russell Eberhart

eberhart@engr.iupui.edu

Os “inventores” (2)

James Kennedy

Kennedy_Jim@bls.gov

Parte 1: United we stand

Exemplo de Cooperação

Inicialização. Posições and velocidades

Vizinhanças

geografica socia

l

A Vizinhança circular

Circulo Virtual

1

5

7

6 4

3

8 2Partícula

1’s 3-vizinhos

Compromisso Psychosocial

Aqui estou! A melhor perf. dos vizinhos

Meu melhor perf.

xpg

pi

v

i-proximidade

g-proximidade

O Histórico Algoritmo

txprand

txprandtv

tv

ddg

ddi

d

d

,2

,1

,0

,0

1

Para cada partícula

atualizea

velocidade

1)1( tvtxtxentão

Para cada componente d

A cada passo t

Aleatoriedade

dentro do laço

Proximidade Aleatória

xpg

pi

v

i-proximidade

g-proximidade

Hyperparallelepipedo => Biased

Ilustração AnimadaÓtimo Global

Parte 2: Como escolher os parametros Direção correta

Esta direção

Ou esta direção

Tipe 1

2121 ''),0(),0( randrand

21

21

''''

gi pp

p

)()1()1()))(()(()1(

txtvtxtxptvtv

com

4for 42

22

else

Valores usuais:k=1=4.1=> =0.73Pop.=20Num. vz=3

Criterio de não-divergência

Coefciente Global

Alugmas Funções ...

Rosenbrock

Griewank Rastrigin

... E alguns resultados

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

Otimo=0, dimensão=30Melhores resultados após 40 000 avaliações

Beat the swarm!

Your current position

Your best perf.Best perf.

of the swarm

Part 3: Por dentro dos números reais

0

1

2

3

4

0

1

2

3

0

1

2

3

4

1

2

3

4

5

6 0

1

2

0

1

2

3

4

8 8Bingo!

Requisitos Mínimos

'',)',( xfxfxfxfHHxx

positionvelocityposition

velocitypositionposition

velocityvelocityvelocity

velocityvelocitytcoefficien

,

,

,

,

Operadores Algébricos

Fifty-fifty

xi 1...N i j xi xj

xi xiD/21

D

1

D /2

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)

granularity=1

Knapsack

xi 1...N i j xi xj

xi SiI , 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)

granularity=1

Problema do Grafo

1

45

2

11

55

3

22

1

1

5

5

5 0

2

0

-1

4-3

-1

-1+

=

pos -+ -vel

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

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.

Particle Swarm Central, http://www.particleswarm.netTHE site:Self advert