Otimização por Enxame de Partículas Estocástico — Busca Global Aleatória Baseada em Enxame
- Proposto por
- Kennedy, J. and Eberhart, R. (base PSO); stochastic extensions by Clerc, Kennedy and community
- Ano
- 1995–2002
- Tipo
- Metaheuristic optimization — stochastic swarm intelligence
- Família
- Simulation / optimization
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
A Otimização por Enxame de Partículas Estocástico (PSO Estocástico) é uma meta-heurística de inteligência de enxame que estende o framework padrão de PSO ao incorporar elementos estocásticos explícitos — pesos de inércia aleatórios, reinicializações probabilísticas de velocidade ou injeções de ruído — para escapar de ótimos locais e manter a diversidade da população ao longo da busca.
É amplamente aplicada a problemas de otimização contínuos, mistos e ruidosos em engenharia, pesquisa operacional e projeto baseado em simulação.
A intuição por trás do método
Imagine um bando de pássaros procurando comida, onde cada pássaro se lembra de sua melhor localização pessoal e também segue o ponto mais conhecido do grupo. No PSO padrão, os coeficientes aleatórios r1 e r2 já injetam estocasticidade, mas o PSO Estocástico amplifica ou estrutura deliberadamente essa aleatoriedade — variando o peso de inércia aleatoriamente a cada iteração, adicionando ruído Gaussiano às posições ou reinicializando probabilisticamente partículas estagnadas — para que o enxame continue explorando amplamente em vez de convergir prematuramente para uma região subótima.
História
A Otimização por Enxame de Partículas foi introduzida por Kennedy e Eberhart em 1995, inspirada pelo comportamento social de bandos de pássaros e cardumes de peixes. Clerc e Kennedy (2002) formalizaram a variante do coeficiente de constrição e analisaram a estabilidade, lançando as bases teóricas. Extensões estocásticas — pesos de inércia aleatórios, velocidades aumentadas por ruído, reinicializações probabilísticas — surgiram ao longo do final dos anos 1990 e 2000 à medida que pesquisadores identificaram a convergência prematura como a principal fraqueza prática do algoritmo original.
Quando usar
Use PSO Estocástico quando o cenário de busca for multimodal, ruidoso ou de alta dimensionalidade e o PSO padrão tender à convergência prematura. É particularmente adequado para otimização baseada em simulação onde a função objetivo é estocástica ou cara de avaliar, e para problemas de projeto de engenharia com muitos mínimos locais. Prefira-o a variantes determinísticas quando a manutenção da diversidade for crítica. NÃO o use quando o problema tiver uma função objetivo convexa e unimodal com avaliações baratas — métodos baseados em gradiente ou exatos serão mais rápidos e precisos. Evite-o também quando a reprodutibilidade de cada execução for essencial sem uma política de semente aleatória fixa, pois o ruído estocástico complica a replicação exata.
Limitações e considerações
- Sensibilidade a hiperparâmetros: os parâmetros de ruído e a distribuição do peso de inércia afetam fortemente a velocidade de convergência e a qualidade da solução.
- Nenhuma garantia teórica de encontrar o ótimo global em tempo finito para problemas não convexos arbitrários.
- Reinicializações estocásticas podem descartar partículas promissoras, ocasionalmente desperdiçando avaliações de fitness.
- O desempenho degrada em espaços de muito alta dimensionalidade (maldição da dimensionalidade) em relação a métodos específicos do problema.
- Múltiplas execuções podem ser necessárias para construir confiança na qualidade da solução, aumentando o custo computacional total.
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
- Mantém a diversidade da população através de aleatoriedade controlada, reduzindo substancialmente a convergência prematura em comparação com o PSO padrão.
- Não requer informação de gradiente e lida com funções objetivo não suaves, descontínuas ou de caixa preta.
- Facilmente paralelizado: cada avaliação de partícula é independente dentro de uma iteração.
- Flexível: o grau de estocasticidade (nível de ruído, distribuição de inércia) pode ser ajustado para equilibrar exploração e explotação.
- Lida naturalmente com funções de fitness estocásticas ou baseadas em simulação onde as avaliações carregam ruído inerente.
- Conceitualmente simples com poucos hiperparâmetros (tamanho do enxame N, coeficientes cognitivo c1, social c2 e parâmetros de ruído).
Aplicações
- Otimização de projeto de engenharia: ajuste de forma aerodinâmica, projeto de arranjo de antenas, otimização estrutural sob incerteza.
- Treinamento de redes neurais: otimização de pesos para redes feedforward e recorrentes em conjuntos de dados ruidosos.
- Cadeia de suprimentos e escalonamento: escalonamento estocástico de job-shop, otimização de estoque sob incerteza de demanda.
- Otimização de portfólio financeiro: maximização de retorno ajustado ao risco com modelos de mercado estocásticos.
- Otimização baseada em simulação: calibração de modelos baseados em agentes ou de dinâmica de sistemas a dados empíricos.
- Ajuste de hiperparâmetros para pipelines de aprendizado de máquina onde a superfície de perda de validação é ruidosa.
Como funciona
Como funciona
Inicialize um enxame de N partículas com posições x_i e velocidades v_i amostradas uniformemente ao acaso dentro do espaço de busca factível. Avalie a função objetivo f(x_i) para cada partícula e defina o melhor pessoal p_i = x_i e o melhor global g = argmin f(x_i).
Atualize a velocidade de cada partícula usando a regra estocástica: v_i(t+1) = omega * v_i(t) + c1*r1*(p_i - x_i) + c2*r2*(g - x_i), onde r1, r2 ~ Uniform(0,1) são novas extrações aleatórias a cada iteração. No PSO Estocástico, o próprio omega pode ser extraído de uma distribuição (por exemplo, Uniform(0.4, 0.9)) ou um termo de ruído Gaussiano epsilon ~ N(0, sigma^2) é adicionado para manter a diversidade.
Fórmula
v_i(t+1) = \omega v_i(t) + c_1 r_1 (p_i - x_i(t)) + c_2 r_2 (g - x_i(t))
Mova cada partícula para sua nova posição candidata: x_i(t+1) = x_i(t) + v_i(t+1). Aplique tratamento de limites (reflexão, limitação ou envolvimento toroidal) para manter as partículas dentro do domínio factível.
Fórmula
x_i(t+1) = x_i(t) + v_i(t+1)
Aplique mecanismos estocásticos adicionais dependendo da variante: (a) peso de inércia aleatório extraído a cada iteração, (b) perturbação Gaussiana dos melhores pessoais para escapar de bacias de atração locais, ou (c) reinicialização aleatória de partículas cuja taxa de melhoria cai abaixo de um limiar, restaurando a capacidade de exploração.
Avalie f(x_i(t+1)) para todas as partículas; atualize os melhores pessoais e o melhor global. Repita a atualização de velocidade através da verificação de convergência por T iterações ou até que um critério de parada seja atendido (por exemplo, melhoria de fitness < epsilon em K iterações consecutivas). Retorne o melhor global g como a solução.
Erros comuns
- Definir a variância do ruído muito alta transforma o algoritmo em busca quase aleatória; muito baixa não oferece benefício sobre o PSO padrão — calibre em um problema de validação primeiro.
- Ignorar o tratamento de limites na etapa de perturbação estocástica pode empurrar partículas para fora da região factível, produzindo soluções inválidas ou sem sentido.
- Comparar PSO Estocástico contra baselines determinísticos em uma única execução é enganoso; sempre relate estatísticas (média, desvio padrão) sobre múltiplas execuções independentes.
- Usar uma semente aleatória fixa em todas as partículas remove o benefício da diversidade — certifique-se de que cada partícula use fluxos aleatórios independentes.
Perguntas frequentes
Como o PSO Estocástico difere do PSO padrão?
O PSO padrão já utiliza coeficientes aleatórios r1 e r2 extraídos uniformemente a cada iteração. O PSO Estocástico estrutura ou amplifica deliberadamente essa aleatoriedade — por exemplo, amostrando o peso de inércia omega de uma distribuição de probabilidade a cada iteração, adicionando ruído Gaussiano às posições das partículas ou reinicializando probabilisticamente partículas estagnadas — para fornecer uma manutenção de diversidade mais forte.
Quantas partículas devo usar?
Um ponto de partida comum é de 20 a 50 partículas para problemas de até ~30 dimensões. Enxames maiores (50–200) melhoram a cobertura em espaços de alta dimensionalidade ou altamente multimodais ao custo de mais avaliações de função por iteração.
Como escolho a variância do ruído para perturbações estocásticas?
Calibre em uma instância representativa da sua classe de problema. Uma heurística prática é definir o desvio padrão do ruído aditivo para aproximadamente 1–5% da largura do espaço de busca por dimensão, e então ajustar com base em diagnósticos de convergência — a métrica de diversidade não deve colapsar para perto de zero antes que o orçamento seja esgotado.
Quando devo preferir PSO Estocástico em vez de Algoritmos Genéticos ou Evolução Diferencial?
O PSO Estocástico tende a convergir mais rapidamente em problemas contínuos de baixa a média dimensionalidade e é muito simples de implementar. A Evolução Diferencial e os Algoritmos Genéticos geralmente lidam melhor com estruturas combinatórias ou discretas. Se o seu problema for puramente contínuo e multimodal, o PSO Estocástico é uma forte primeira escolha.
O PSO Estocástico é adequado para problemas multiobjetivo?
A variante de objetivo único descrita aqui não é projetada diretamente para problemas multiobjetivo. Para esses, use PSO Multiobjetivo (MOPSO) ou NSGA-II, que mantêm um arquivo explícito de soluções Pareto-não dominadas.
Métodos relacionados
Fontes
Kennedy, J., Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN'95 - International Conference on Neural Networks, Vol. 4, pp. 1942-1948. IEEE.
Abrir referência DOICopiado.Clerc, M., Kennedy, J. (2002). The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58-73.
Abrir referência DOICopiado.