Otimização Nuvem De particulas(particle Swarm)

Embed Size (px)

Citation preview

  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    1/27

    A OtimizaoNuvem de Partculas(particle swarm)

    Estfane G. M. de Lacerda

    Departamento de Engenharia da Computao e Automao

    UFRN

    20/06/2007

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    2/27

  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    3/27

    Otimizao Nuvem de Partculas

    Desenvolvido pelo psiclogo social JamesKennedy e o engenheiro eletricista RusselEberhart em 1995;

    Inspirado no comportamento e na dinmica

    dos movimentos dos pssaros, insetos epeixes;

    Originalmente desenvolvido para

    problemas de otimizao com variveiscontnuas; Desempenho similar ao dos Algoritmos

    Genticos;

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    4/27

    Otimizao Nuvem de Partculas

    Estudos apontam que um bando de

    passros encontra alimento por meio deesforo conjunto. Isto sugere que elescompartilham informaes.

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    5/27

    Otimizao Nuvem de Partculas

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    6/27

    Otimizao Nuvem de Partculas

    No incio as partculas voam aleatoriamentepelo espao de busca.

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    7/27

    Otimizao Nuvem de Partculas

    Vantagens Insensvel a mudana de escala das variveis; Implementao simples; Adaptvel a computadores paralelos;

    No requer clculo de derivadas; Poucos parmetros para serem definidos pelousurio;

    Bom para encontrar o mnimo global;

    Desvantagens Rpido para localizar a bacia de atrao das

    boas solues, mas lento no ajuste fino dasoluo (como nos algoritmos genticos).

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    8/27

    Notao

    xi =

    xi,1xi,2

    ...xi,n

    , posio da partcula i (coordenadas)

    vi =

    vi,1vi,2

    ...vi,n

    , velocidade da partcula i

    f(xi), aptido da partcula im, tamanho da populao de partculas

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    9/27

    Notao

    pi pbesti (personal best)a melhor posio encontrada pela partcula i

    g gbest(global best)

    a melhor posio encontrada portodas as partculasc1, c2 parmetros cognitivo e social

    (tambm chamados de taxas de aprendizado)w ponderao de inrcia

    r1j, r2j nmeros aleatrios entre 0 e 1

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    10/27

    Atualizao de Posio e Velocidade

    Atualizao de velocidade na iterao k

    vk+1ij = wvkij + c1r1j(p

    kij x

    kij ) + c2r2j(g

    kj x

    kij )

    para i = 1, . . . , m e j = 1, . . . , n.Atualizao de posio na iterao k

    xk+1i = x

    ki + v

    k+1i

    para i = 1, . . . , m

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    11/27

    Componentes Cognitivo e Social

    (pki xki ) o componente cognitivo:

    representa a experincia individual da

    partcula de onde a soluo est. (gk xki ) o componente social:

    representa a experincia da nuvem deonde a soluo est.

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    12/27

    Algoritmo Nuvem de Partculasinicialize a nuvem de partculasrepita

    para i = 1 at mse f(xi) < f(pi) ento

    pi = xise f(xi) < f(g) ento

    g = xifim se

    fim separa j = 1 at n

    r1 = rand() , r2 = rand()vij = wvij + c1r1(pi xij) + c2r2(gj xij)

    fim paraxi = xi + vi

    fim para

    at satisfazer o critrio de parada

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    13/27

    Alguns Detalhes de Implementao

    Limites superior e inferior. xij [xmin, xmax]. Caso xij saia deste intervalo

    fazer xij = xmin ou xij = xmax (conforme o caso).Fazer tambm vij = 0;

    Velocidade mxima. vmax vij vmax.

    Em geral, no necessrio armazenar g

    no computador, basta armazenar o ndice ital que pi = g.

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    14/27

    Interpretao Geomtrica

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    15/27

    Interpretao Geomtrica

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    16/27

    Diversificao e Intensificao

    Nuvem de partculas fornece um mecanismobem balanceado entre diversificao eintensificao:

    vk+1ij = wvkij

    diversificao+ c1r1j(p

    kij x

    kij ) + c2r2j(g

    kj x

    kij )

    intensificao

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    17/27

    Melhoramentos e Variantes

    Reduo linear da ponderao de inrcia; Fator de constrio; Modelos com Vizinhanas.

    R d Li d P d d

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    18/27

    Reduo Linear da Ponderao deInrcia

    A cada iterao k a ponderao reduzida:

    wk+1 = wmax k

    wmax wmin

    kmax

    onde kmax o nmero mximo de iteraes.

    Shi e Eberhart (1998) relataram que

    wmax =

    0, 9wmin = 0, 4

    c1 = c2 = 2

    deu bons resultados em uma variedade de problemas.

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    19/27

    Fator de Constrio

    Fator de Constrio foi introduzido por

    Clerc e Kennedy (2002). Tornou-se muito popular nos algoritmos

    recentes de nuvem de partcula.

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    20/27

    Fator de Constrio

    Atualizao de velocidade:

    vk+1ij =

    vkij + c1r1j(pkij x

    kij ) + c2r2j(g

    kj x

    kij )

    =

    2

    |2

    2 4|

    onde o fator de constrio, = c1 + c2, > 4.

    Valores usuais, = 1, = 4, 1 = 0, 73.c1 = c2 = 2, 05.

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    21/27

    Modelos com Vizinhanas

    A cada partcula atribudo umavizinhana;

    As vizinhanas tornam mais lento atransmisso da melhor posio atrves danuvem;

    Converge mais lentamente, mas melhora a

    diversificao.

    M d l Vi i h

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    22/27

    Modelos com Vizinhanas Na nuvem de partcula, a vizinhana

    social, ou seja, no baseada naproximidade geogrfica.

    M d l Vi i h

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    23/27

    Modelos com Vizinhanas

    li o local best(lbesti) e representa amelhor posio encontrada na vizinhana

    da partcula i; Substitua g (gbest) por li (lbesti), ou seja,

    vk+1

    ij

    = wvk

    ij

    + c1r1(pk

    ij

    xk

    ij

    ) + c2r2(lk

    i

    xk

    ij

    )

    Vi i h S t

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    24/27

    Vizinhanas Soprepostas

    A nuvem dividida em vizinhanassoprepostas.

    Exemplo: se h 8 partculas a,b,c,d,e,f,g,he o tamanho da vizinhana 2 ento asvizinhanas so:

    (h,a,b) - (a,b,c) - (b,c,d) - (c,d,e)

    (d,e,f) - (e,f,g) - (f,g,h) - (g,h,a)

    Vi i h S t

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    25/27

    Vizinhanas Soprepostas

    Se o tamanho da vizinhana dois, entopartculas so arranjadas na forma de um anel.

    O Conceito de Vizinhana em Nuvem

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    26/27

    O Conceito de Vizinhana em Nuvemde Partculas

    Este conceito de vizinhana nada tem

    haver com a idia de proximidade noespao de busca; De fato, vizinhos podem estar bem

    distantes um do outro no espao de busca.

    O tras Topologias de Vi inhanas

    http://find/http://goback/
  • 8/7/2019 Otimizao Nuvem De particulas(particle Swarm)

    27/27

    Outras Topologias de Vizinhanas

    Estrela Grade

    http://find/http://goback/