Skip to content
Voltar aos resultados

Otimização por Enxame de Partículas (PSO)

Ano
1995
Tipo
Population-based metaheuristic / swarm intelligence

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

A Otimização por Enxame de Partículas (PSO) é um algoritmo meta-heurístico baseado em população, introduzido por Kennedy e Eberhart em 1995, inspirado no movimento coletivo de bandos de pássaros e cardumes de peixes.

Cada solução candidata — chamada de partícula — move-se através do espaço de busca atualizando sua velocidade e posição com base em sua própria melhor experiência e na melhor experiência de todo o enxame, permitindo uma convergência rápida em problemas de otimização contínua.

A intuição por trás do método

Imagine um bando de pássaros procurando em um grande campo a fonte de alimento mais rica. Nenhum pássaro individual tem um mapa, mas cada um se lembra do melhor local que visitou pessoalmente e está ciente do melhor local encontrado por qualquer pássaro próximo. Cada pássaro direciona seu voo parcialmente para sua própria melhor localização lembrada e parcialmente para o melhor coletivo do enxame, ajustando a velocidade de acordo. Ao longo de muitos ajustes, todo o bando converge para a área mais rica. A PSO funciona exatamente assim: cada partícula é uma solução candidata, sua posição é a própria solução, e o enxame converge para o ótimo ao compartilhar memória individual e social.

História

A PSO foi introduzida por James Kennedy e Russell Eberhart na IEEE International Conference on Neural Networks de 1995, baseando-se diretamente em modelos de simulação de comportamento social em bandos de pássaros e cardumes de peixes. O artigo fundamental de 1995 estabeleceu as equações de atualização de velocidade e posição que permanecem centrais para o algoritmo. Em 1998, Shi e Eberhart introduziram o parâmetro de peso de inércia na atualização de velocidade, melhorando significativamente o controle de convergência e tornando-se a modificação padrão adotada por pesquisas subsequentes. A PSO rapidamente ganhou tração como uma alternativa prática aos algoritmos genéticos para otimização contínua, devido à sua simplicidade e velocidade de convergência competitiva, e desde então tem sido aplicada em engenharia, ajuste de hiperparâmetros de aprendizado de máquina, processamento de sinais e modelagem científica.

Quando usar

A PSO é adequada para problemas de otimização contínua onde a função de aptidão pode ser avaliada em qualquer ponto do espaço de busca, mas pode ser não diferenciável, multimodal ou cara de calcular analiticamente. Ela não requer suposição de normalidade nem tamanho mínimo de amostra, tornando-a aplicável em diversos domínios. O método funciona melhor quando os limites do espaço de busca são conhecidos antecipadamente, quando o peso de inércia e os coeficientes de aceleração são ajustados cuidadosamente, e quando um número suficiente de iterações é alocado. Se a contagem de iterações for muito baixa (menos de algumas centenas em problemas não triviais), a convergência prematura é provável e a otimização Bayesiana pode ser uma alternativa mais segura.

Limitações e considerações

  • Projetada para espaços de busca contínuos; não aplicável diretamente a problemas discretos ou combinatórios sem modificação.
  • Convergência prematura é um risco conhecido: o enxame pode se agrupar em torno de um ótimo local se o peso de inércia e os coeficientes forem mal escolhidos.
  • A velocidade de convergência e a qualidade da solução são sensíveis à escolha do peso de inércia e dos coeficientes de aceleração.
  • Nenhuma garantia teórica de encontrar o ótimo global em um número finito de iterações.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Convergência rápida em espaços de busca contínuos em relação a muitos métodos baseados em população.
  • Pouquíssimos parâmetros para ajustar — principalmente o peso de inércia e dois coeficientes de aceleração.
  • Não requer informação de gradiente ou derivada, tornando-a aplicável a funções de aptidão não diferenciáveis e de caixa preta.
  • Escala naturalmente para problemas contínuos de alta dimensionalidade.
  • Conceitualmente simples e direta de implementar.

Aplicações

  • Ajuste de hiperparâmetros para modelos de aprendizado de máquina em espaços de parâmetros contínuos.
  • Otimização de projeto de engenharia — projeto estrutural, aerodinâmico e de sistemas elétricos.
  • Treinamento de pesos de redes neurais e busca de arquitetura.
  • Processamento de sinais e projeto de antenas.
  • Despacho econômico e otimização de sistemas de energia.
  • Estimativa de parâmetros em modelos científicos e de simulação.

Como funciona

Como funciona

1

Um enxame de partículas é posicionado aleatoriamente dentro do espaço de busca definido, e cada partícula recebe uma velocidade inicial aleatória. Cada partícula também registra sua posição pessoal ótima — a melhor solução que encontrou até agora — e o enxame rastreia a posição global ótima encontrada por qualquer partícula. O peso de inércia, o coeficiente cognitivo e o coeficiente social são definidos antes do início da execução, pois seu equilíbrio governa diretamente se o enxame explora amplamente ou explora regiões boas conhecidas.

2

A função de aptidão é calculada para cada partícula em sua posição atual. Esta é a única etapa específica do problema: a PSO não impõe restrições à forma da função de aptidão além do requisito de que ela possa ser avaliada em qualquer ponto do espaço de busca contínuo. A melhor posição pessoal de cada partícula e a melhor posição global do enxame são atualizadas sempre que uma nova posição produz um valor de aptidão melhor.

3

A velocidade de cada partícula é atualizada usando três componentes: o termo de inércia (velocidade anterior escalonada, promovendo momentum), o termo cognitivo (atração em direção à melhor posição pessoal da partícula) e o termo social (atração em direção à melhor posição global do enxame). A nova posição é então calculada adicionando a velocidade atualizada à posição atual. O peso de inércia controla o equilíbrio entre exploração e explotação: um valor mais alto favorece a exploração ampla, enquanto um valor mais baixo promove a explotação detalhada de regiões boas conhecidas.

4

As etapas de avaliação e atualização são repetidas pelo número prescrito de iterações. O enxame estreita progressivamente sua busca em torno da região mais promissora. A execução é concluída quando o limite de iterações é atingido, momento em que a posição global ótima é reportada como a solução. Uma contagem de iterações suficiente — tipicamente pelo menos algumas centenas a mil para problemas não triviais — é necessária para permitir que o enxame convirja; parar muito cedo arrisca retornar um resultado subótimo.

Erros comuns

  • Executar poucas iterações — em problemas não triviais, iterações insuficientes impedem o enxame de convergir; prefira otimização Bayesiana quando o orçamento computacional é muito apertado.
  • Escolher um peso de inércia muito alto mantém as partículas explorando indefinidamente e atrasa a convergência; muito baixo causa agrupamento prematuro em torno de um ótimo local.
  • Ignorar os limites do espaço de busca — partículas que se desviam para fora dos limites pretendidos exploram regiões irrelevantes e distorcem o melhor global.
  • Tratar a PSO como adequada para problemas discretos ou combinatórios sem adaptação — as equações padrão de atualização de velocidade e posição assumem um espaço contínuo.
  • Convergência prematura passa despercebida se o progresso da aptidão não for monitorado ao longo das iterações; sempre rastreie a aptidão global ótima versus a contagem de iterações.

Perguntas frequentes

Como a PSO difere de um algoritmo genético?

Ambos são meta-heurísticas baseadas em população para otimização, mas diferem no mecanismo. Um algoritmo genético evolui uma população através de operadores de seleção, cruzamento e mutação inspirados na evolução biológica. A PSO, em vez disso, move partículas através de um espaço contínuo atualizando velocidades com base na memória pessoal e social — não há cruzamento ou mutação. A PSO tipicamente tem menos parâmetros para ajustar e frequentemente converge mais rápido em problemas contínuos, enquanto algoritmos genéticos podem ser adaptados de forma mais natural a espaços discretos ou combinatórios.

Quais são os parâmetros chave e como devem ser definidos?

Os três parâmetros centrais são o peso de inércia (w), que controla quanta velocidade anterior é retida; o coeficiente cognitivo (c1), que escala a atração pela melhor posição pessoal de uma partícula; e o coeficiente social (c2), que escala a atração pela melhor posição global. Um ponto de partida comum da literatura é w em torno de 0.7–0.9, c1 e c2 em torno de 1.5–2.0. O peso de inércia é frequentemente diminuído linearmente ao longo das iterações para mudar o enxame da exploração no início para a explotação mais tarde.

A PSO pode lidar com problemas discretos ou combinatórios?

A PSO padrão é definida para espaços de busca contínuos e aplica atualizações de velocidade e posição que assumem coordenadas de valor real. Variantes discretas ou combinatórias existem — como a PSO binária — mas estas requerem modificações não triviais nas equações de atualização. Para problemas puramente combinatórios como roteamento ou agendamento, a Otimização por Colônia de Formigas é frequentemente a escolha mais natural.

Como sei se o enxame convergiu prematuramente?

Rastreie o valor da aptidão global ótima ao longo das iterações. Se a curva se achatar muito antes que o orçamento de iterações seja esgotado e a solução reportada não for satisfatória, a convergência prematura provavelmente ocorreu. Remédios comuns incluem aumentar o peso de inércia, reiniciar o enxame de novas posições aleatórias ou aumentar o tamanho do enxame. Se o orçamento computacional não permitir mais iterações, a otimização Bayesiana pode ser uma alternativa mais eficiente.

Métodos relacionados

Fontes

  1. Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Networks (ICNN), 1942-1948.

    Abrir referência DOI
    Copiado.
  2. Shi, Y. & Eberhart, R. (1998). A Modified Particle Swarm Optimizer. IEEE Congress on Evolutionary Computation (CEC).

    Abrir referência da publicação
    Copiado.