Otimização de enxame de particulas - Particle swarm optimization

Um enxame de partículas em busca do mínimo global de uma função
Parte de uma série no
Algoritmo evolutivo
Algoritmo genético
Programação genética

Em ciência da computação , a otimização por enxame de partículas ( PSO ) é um método computacional que otimiza um problema tentando melhorar iterativamente uma solução candidata com relação a uma determinada medida de qualidade. Ele resolve um problema tendo uma população de soluções candidatas, aqui chamadas de partículas , e movendo essas partículas no espaço de busca de acordo com uma fórmula matemática simples sobre a posição e velocidade da partícula . O movimento de cada partícula é influenciado por sua posição local mais conhecida, mas também é orientado para as posições mais conhecidas no espaço de busca, que são atualizadas conforme as melhores posições são encontradas por outras partículas. Espera-se que isso mova o enxame em direção às melhores soluções.

PSO é originalmente atribuído a Kennedy , Eberhart e Shi e foi inicialmente planejado para simular o comportamento social , como uma representação estilizada do movimento de organismos em um bando de pássaros ou cardume de peixes . O algoritmo foi simplificado e observou-se que estava realizando uma otimização. O livro de Kennedy e Eberhart descreve muitos aspectos filosóficos do PSO e da inteligência de enxame . Um extenso levantamento das aplicações PSO é feito pela Poli . Recentemente, uma revisão abrangente sobre trabalhos teóricos e experimentais sobre PSO foi publicada por Bonyadi e Michalewicz.

PSO é uma metaheurística , pois faz poucas ou nenhuma suposição sobre o problema que está sendo otimizado e pode pesquisar espaços muito grandes de soluções candidatas. Além disso, o PSO não usa o gradiente do problema que está sendo otimizado, o que significa que o PSO não exige que o problema de otimização seja diferenciável, conforme exigido pelos métodos de otimização clássicos, como os métodos de gradiente descendente e quase newton . No entanto, metaheurísticas como PSO não garantem que uma solução ótima seja encontrada.

Algoritmo

Uma variante básica do algoritmo PSO funciona tendo uma população (chamada de enxame) de soluções candidatas (chamadas de partículas). Essas partículas são movidas no espaço de busca de acordo com algumas fórmulas simples. Os movimentos das partículas são guiados por sua própria posição mais conhecida no espaço de busca, bem como pela posição mais conhecida de todo o enxame. Quando posições melhoradas forem descobertas, elas passarão a guiar os movimentos do enxame. O processo é repetido e, ao fazê-lo, espera-se, mas não é garantido, que uma solução satisfatória seja eventualmente descoberta.

Formalmente, seja f : ℝ n  → ℝ a função de custo que deve ser minimizada. A função pega uma solução candidata como um argumento na forma de um vetor de números reais e produz um número real como saída que indica o valor da função objetivo da solução candidata dada. O gradiente de f não é conhecido. O objetivo é encontrar uma solução a para a qual f ( a ) ≤  f ( b ) para todo b no espaço de busca, o que significaria que a é o mínimo global.

Seja S o número de partículas no enxame, cada uma tendo uma posição x i  ∈ ℝ n no espaço de busca e uma velocidade v i  ∈ ℝ n . Seja p i a posição mais conhecida da partícula i e seja g a posição mais conhecida de todo o enxame. Um algoritmo PSO básico é então: 

for each particle i = 1, ..., S do
    Initialize the particle's position with a uniformly distributed random vector: xi ~ U(blo, bup)
    Initialize the particle's best known position to its initial position: pi ← xi
    if f(pi) < f(g) then
        update the swarm's best known position: g ← pi
    Initialize the particle's velocity: vi ~ U(-|bup-blo|, |bup-blo|)
while a termination criterion is not met do:
    for each particle i = 1, ..., S do
        for each dimension d = 1, ..., n do
            Pick random numbers: rp, rg ~ U(0,1)
            Update the particle's velocity: vi,d ← w vi,d + φp rp (pi,d-xi,d) + φg rg (gd-xi,d)
        Update the particle's position: xi ← xi + vi
        if f(xi) < f(pi) then
            Update the particle's best known position: pi ← xi
            if f(pi) < f(g) then
                Update the swarm's best known position: g ← pi

Os valores b lo e b up representam os limites inferior e superior do espaço de busca, respectivamente. O parâmetro w é o peso de inércia. Os parâmetros φ p e φ g são freqüentemente chamados de coeficiente cognitivo e coeficiente social.

O critério de término pode ser o número de iterações realizadas ou uma solução onde o valor adequado da função objetivo é encontrado. Os parâmetros w, φ p e φ g são selecionados pelo profissional e controlam o comportamento e a eficácia do método PSO ( abaixo ).

Seleção de parâmetros

Cenário de desempenho que mostra como uma variante simples de PSO atua de forma agregada em vários problemas de benchmark ao variar dois parâmetros de PSO.

A escolha dos parâmetros do PSO pode ter um grande impacto no desempenho da otimização. A seleção de parâmetros de PSO que geram bom desempenho tem sido, portanto, o assunto de muitas pesquisas.

Para evitar divergência ("explosão"), o peso da inércia deve ser menor que 1. Os outros dois parâmetros podem ser derivados graças à abordagem de constrição, ou selecionados livremente, mas as análises sugerem domínios de convergência para restringi-los. Os valores típicos estão em .

Os parâmetros do PSO também podem ser ajustados usando outro otimizador de sobreposição, um conceito conhecido como meta-otimização , ou mesmo ajustados durante a otimização, por exemplo, por meio de lógica fuzzy.

Os parâmetros também foram ajustados para vários cenários de otimização.

Bairros e topologias

A topologia do enxame define o subconjunto de partículas com as quais cada partícula pode trocar informações. A versão básica do algoritmo usa a topologia global como estrutura de comunicação de enxame. Essa topologia permite que todas as partículas se comuniquem com todas as outras partículas, portanto, todo o enxame compartilha a mesma melhor posição g de uma única partícula. No entanto, essa abordagem pode fazer com que o enxame fique preso a um mínimo local, portanto, diferentes topologias têm sido usadas para controlar o fluxo de informações entre as partículas. Por exemplo, em topologias locais, as partículas compartilham informações apenas com um subconjunto de partículas. Este subconjunto pode ser geométrico - por exemplo, "as m partículas mais próximas" - ou, mais frequentemente, social, ou seja, um conjunto de partículas que não depende de nenhuma distância. Nesses casos, a variante do PSO é considerada a melhor local (versus a melhor global para o PSO básico).

Uma topologia de enxame comumente usada é o anel, em que cada partícula tem apenas dois vizinhos, mas existem muitos outros. A topologia não é necessariamente estática. De fato, como a topologia está relacionada à diversidade de comunicação das partículas, alguns esforços têm sido feitos para criar topologias adaptativas (SPSO, APSO, estrela estocástica, TRIBES, Cyber ​​Swarm e C-PSO).

Trabalhos internos

Existem várias escolas de pensamento sobre por que e como o algoritmo PSO pode realizar a otimização.

Uma crença comum entre os pesquisadores é que o comportamento do enxame varia entre o comportamento exploratório, ou seja, pesquisar uma região mais ampla do espaço de busca, e o comportamento exploratório, ou seja, uma pesquisa orientada localmente para se aproximar de um (possivelmente local) ótimo. Essa escola de pensamento prevalece desde o início do PSO. Esta escola de pensamento afirma que o algoritmo PSO e seus parâmetros devem ser escolhidos de forma a equilibrar adequadamente entre a exploração e a exploração para evitar a convergência prematura para um ótimo local e ainda garantir uma boa taxa de convergência para o ótimo. Essa crença é o precursor de muitas variantes do PSO, veja abaixo .

Outra escola de pensamento é que o comportamento de um enxame de PSO não é bem compreendido em termos de como ele afeta o desempenho de otimização real, especialmente para espaços de busca de dimensão superior e problemas de otimização que podem ser descontínuos, barulhentos e variáveis ​​no tempo. Esta escola de pensamento apenas tenta encontrar algoritmos e parâmetros de PSO que causam bom desempenho, independentemente de como o comportamento do enxame pode ser interpretado em relação, por exemplo, à exploração e à exploração. Esses estudos levaram à simplificação do algoritmo PSO, veja abaixo .

Convergência

Em relação ao PSO, a palavra convergência normalmente se refere a duas definições diferentes:

  • Convergência da sequência de soluções (também conhecida como análise de estabilidade, convergência ) em que todas as partículas convergiram para um ponto no espaço de busca, que pode ou não ser o ideal,
  • A convergência para um ótimo local onde todos os melhores pessoais p ou, alternativamente, a posição g mais conhecida do enxame , se aproxima de um ótimo local do problema, independentemente de como o enxame se comporta.

A convergência da sequência de soluções foi investigada para PSO. Essas análises resultaram em diretrizes para a seleção de parâmetros de PSO que, segundo se acredita, causam convergência a um ponto e evitam a divergência das partículas do enxame (as partículas não se movem ilimitadamente e convergirão para algum lugar). No entanto, as análises foram criticadas por Pedersen por serem supersimplificadas por assumirem que o enxame tem apenas uma partícula, que não usa variáveis ​​estocásticas e que os pontos de atração, ou seja, a posição mais conhecida da partícula pe a posição mais conhecida do enxame g , permanecem constantes durante todo o processo de otimização. Porém, foi demonstrado que essas simplificações não afetam os limites encontrados por esses estudos para o parâmetro onde o enxame é convergente. Um esforço considerável foi feito nos últimos anos para enfraquecer a suposição de modelagem utilizada durante a análise de estabilidade do PSO, com o resultado generalizado mais recente aplicando-se a inúmeras variantes de PSO e utilizando o que se mostrou ser as suposições de modelagem mínimas necessárias.

A convergência para um ótimo local foi analisada para PSO em e. Está provado que o PSO precisa de algumas modificações para garantir encontrar um ótimo local.

Isso significa que a determinação das capacidades de convergência de diferentes algoritmos e parâmetros de PSO ainda depende de resultados empíricos . Uma tentativa de abordar esta questão é o desenvolvimento de uma estratégia de "aprendizagem ortogonal" para um uso melhorado da informação já existente na relação entre p e g , de modo a formar um exemplo convergente líder e ser eficaz com qualquer topologia PSO. Os objetivos são melhorar o desempenho geral do PSO, incluindo convergência global mais rápida, solução de qualidade superior e robustez mais forte. No entanto, tais estudos não fornecem evidências teóricas para realmente provar suas afirmações.

Mecanismos adaptativos

Sem a necessidade de um trade-off entre convergência ('exploração') e divergência ('exploração'), um mecanismo adaptativo pode ser introduzido. A otimização adaptativa de enxame de partículas (APSO) apresenta melhor eficiência de pesquisa do que o PSO padrão. O APSO pode realizar pesquisas globais em todo o espaço de pesquisa com uma velocidade de convergência mais alta. Ele permite o controle automático do peso de inércia, coeficientes de aceleração e outros parâmetros algorítmicos em tempo de execução, melhorando assim a eficácia e eficiência da pesquisa ao mesmo tempo. Além disso, o APSO pode atuar na melhor partícula globalmente para saltar do provável ótimo local. No entanto, o APSO irá introduzir novos parâmetros de algoritmo, mas não apresenta um design adicional ou complexidade de implementação.

Variantes

São possíveis inúmeras variantes até mesmo de um algoritmo PSO básico. Por exemplo, existem diferentes maneiras de inicializar as partículas e velocidades (por exemplo, começar com velocidades zero em vez disso), como amortecer a velocidade, atualizar apenas p i e g depois que todo o enxame foi atualizado, etc. Algumas dessas escolhas e seus possível impacto no desempenho foram discutidos na literatura.

Uma série de implementações padrão foi criada por pesquisadores líderes ", destinadas ao uso como uma linha de base para testes de desempenho de melhorias na técnica, bem como para representar PSO para a comunidade de otimização mais ampla. Ter um conhecido e estritamente definido o algoritmo padrão fornece um valioso ponto de comparação que pode ser usado em todo o campo de pesquisa para testar melhor os novos avanços. " O mais recente é o Standard PSO 2011 (SPSO-2011).

Hibridização

Variantes de PSO novas e mais sofisticadas também são continuamente introduzidas na tentativa de melhorar o desempenho de otimização. Existem certas tendências nessa pesquisa; um é fazer um método de otimização híbrido usando PSO combinado com outros otimizadores, por exemplo, PSO combinado com otimização baseada em biogeografia e a incorporação de um método de aprendizagem eficaz.

Algoritmos PSO baseados em gradiente

A capacidade do algoritmo PSO de explorar com eficiência múltiplos mínimos locais pode ser combinada com a capacidade dos algoritmos de busca local baseados em gradiente para calcular efetivamente um mínimo local preciso para produzir algoritmos PSO baseados em gradiente. Em algoritmos PSO baseados em gradiente, o algoritmo PSO é usado para explorar muitos mínimos locais e localizar um ponto na bacia de atração de um mínimo local profundo. Em seguida, algoritmos de busca local baseados em gradiente eficientes são usados ​​para localizar com precisão o mínimo local profundo. O cálculo de gradientes e Hessianos de funções complexas de custo de alta dimensão costuma ser caro do ponto de vista computacional e manualmente impossível em muitos casos, evitando a adoção generalizada de algoritmos PSO baseados em gradiente. No entanto, nos últimos anos, a disponibilidade de software de diferenciação automática simbólica (AD) de alta qualidade levou ao ressurgimento do interesse em algoritmos de PSO baseados em gradiente.

Aliviar a convergência prematura

Outra tendência de pesquisa é tentar aliviar a convergência prematura (ou seja, estagnação de otimização), por exemplo, invertendo ou perturbando o movimento das partículas de PSO, outra abordagem para lidar com a convergência prematura é o uso de múltiplos enxames ( otimização multi-enxame ). A abordagem multi-enxame também pode ser usada para implementar a otimização multi-objetivo. Finalmente, existem desenvolvimentos na adaptação dos parâmetros comportamentais do PSO durante a otimização.

Simplificações

Outra escola de pensamento é que o PSO deve ser simplificado tanto quanto possível, sem prejudicar seu desempenho; um conceito geral frequentemente referido como navalha de Occam . A simplificação do PSO foi originalmente sugerida por Kennedy e foi estudada mais extensivamente, onde parecia que o desempenho da otimização foi aprimorado e os parâmetros eram mais fáceis de ajustar e eles funcionavam de forma mais consistente em diferentes problemas de otimização.

Outro argumento a favor da simplificação do PSO é que as metaheurísticas só podem ter sua eficácia demonstrada empiricamente por meio de experimentos computacionais em um número finito de problemas de otimização. Isso significa que uma metaheurística como PSO não pode ser provada como correta e isso aumenta o risco de cometer erros em sua descrição e implementação. Um bom exemplo disso apresentou uma variante promissora de um algoritmo genético (outra metaheurística popular), mas posteriormente foi considerada defeituosa, pois foi fortemente enviesada em sua busca de otimização para valores semelhantes para diferentes dimensões no espaço de busca, que por acaso era o ótimo dos problemas de benchmark considerados. Esse viés foi devido a um erro de programação e agora foi corrigido.

A inicialização de velocidades pode exigir entradas extras. A variante PSO Bare Bones foi proposta em 2003 por James Kennedy e não precisa usar velocidade.

Outra variante mais simples é a otimização acelerada por enxame de partículas (APSO), que também não precisa usar velocidade e pode acelerar a convergência em muitas aplicações. Um código de demonstração simples de APSO está disponível.

Otimização multi-objetivo

PSO também tem sido aplicado a problemas multiobjetivo , nos quais a comparação da função objetivo leva em conta a dominância de pareto ao mover as partículas de PSO e soluções não dominadas são armazenadas de modo a aproximar a frente de pareto.

Binário, discreto e combinatório

Como as equações de PSO fornecidas acima funcionam com números reais, um método comumente usado para resolver problemas discretos é mapear o espaço de busca discreto para um domínio contínuo, para aplicar um PSO clássico e, em seguida, desmapear o resultado. Esse mapeamento pode ser muito simples (por exemplo, usando apenas valores arredondados) ou mais sofisticado.

Porém, pode-se notar que as equações do movimento fazem uso de operadores que realizam quatro ações:

  • calculando a diferença de duas posições. O resultado é uma velocidade (mais precisamente um deslocamento)
  • multiplicando uma velocidade por um coeficiente numérico
  • adicionando duas velocidades
  • aplicando uma velocidade a uma posição

Normalmente, uma posição e uma velocidade são representadas por n números reais e esses operadores são simplesmente -, *, + e novamente +. Mas todos esses objetos matemáticos podem ser definidos de uma maneira completamente diferente, a fim de lidar com problemas binários (ou mais geralmente discretos), ou mesmo combinatórios. Uma abordagem é redefinir os operadores com base em conjuntos.

Veja também

Referências

links externos