A otimização por enxame de partículas (PSO) é um método computacional em inteligência artificial e ciência computacional que otimiza um problema melhorando iterativamente uma população de soluções candidatas em relação a uma determinada medida de qualidade. Ela resolve um problema por meio de interações entre uma população de soluções candidatas, denominadas partículas, movendo-as no espaço de busca de acordo com fórmulas matemáticas simples que ajustam a posição e a velocidade de cada partícula. O movimento de cada partícula é influenciado pela sua melhor posição conhecida até o momento e pela melhor posição conhecida em sua vizinhança topológica, que pode incluir toda a população, se especificado. Os vetores são atualizados conforme melhores posições são encontradas, e espera-se que isso mova o enxame em direção a boas soluções.
PSO é uma meta-heurística porque faz poucas ou nenhuma suposição sobre o problema sendo otimizado e pode buscar espaços muito grandes de soluções candidatas. Ela não utiliza o gradiente do problema, portanto não exige que o problema de otimização seja diferenciável, ao contrário de métodos clássicos como a descida do gradiente ou métodos quase-Newton. No entanto, meta-heurísticas como a PSO não garantem que uma solução ótima será encontrada.
Origens e Desenvolvimento
A PSO foi originalmente atribuída a Kennedy e Eberhart, que a conceberam inicialmente para simular o comportamento social como uma representação estilizada do movimento de organismos em um bando de pássaros ou cardume de peixes, ou a evolução de atitudes em uma população humana. Observou-se que a simulação de princípios de comportamento social era capaz de resolver problemas matemáticos difíceis. O livro de Kennedy e Eberhart descreve muitos aspectos filosóficos da PSO e da inteligência de enxame. Uma extensa pesquisa sobre aplicações da PSO foi realizada por Poli, e em 2017 uma revisão abrangente sobre trabalhos teóricos e experimentais em PSO foi publicada por Bonyadi e Michalewicz.
Algoritmo
Uma variante básica do algoritmo PSO é inicializada com uma população conectada (chamada de enxame) de soluções candidatas (chamadas de partículas). Uma solução candidata é um vetor de valores numéricos que pode ser considerado como coordenadas de um ponto em um espaço de busca; como um ponto que se move iterativamente, pode ser conceituado como uma partícula. As partículas se movem no espaço de busca de acordo com algumas fórmulas simples. Cada partícula tem alguns vizinhos aos quais está conectada, onde a vizinhança pode ser alguns ou todos os outros membros da população. A próxima posição de uma partícula é estocasticamente determinada pela sua melhor posição até o momento no espaço de busca, bem como pela melhor posição até o momento do melhor vizinho da partícula. Quando uma posição melhorada é descoberta - uma que produz um resultado melhor na função objetivo - a melhor posição até o momento da partícula é atualizada. O processo é repetido e, ao fazê-lo, espera-se, mas não se garante, que uma solução satisfatória seja eventualmente descoberta.
Formalmente, seja \( f: \mathbb{R}^n \to \mathbb{R} \) a função de custo a ser minimizada. A função recebe uma solução candidata como argumento na forma de um vetor de números reais e produz um número real como saída indicando o valor da função objetivo. O gradiente de \( f \) não é conhecido. O objetivo é encontrar uma solução \( a \) para a qual \( f(a) \le f(b) \) para todo \( b \) no espaço de busca, significando que \( a \) é o mínimo global.
Seja \( S \) o número de partículas no enxame, cada uma tendo uma posição \( x_i \in \mathbb{R}^n \) e uma velocidade \( v_i \in \mathbb{R}^n \). Seja \( p_i \) a melhor posição conhecida da partícula \( i \), e seja \( g \) a melhor posição conhecida da vizinhança da partícula. Um algoritmo PSO básico para minimizar a função de custo é:
- Para cada partícula \( i = 1, \dots, S \):
- Inicialize a posição da partícula com um vetor aleatório uniformemente distribuído: \( x_i \sim U(b_{lo}, b_{up}) \).
- Inicialize a melhor posição conhecida da partícula como sua posição inicial: \( p_i \leftarrow x_i \).
- Se \( f(p_i) < f(g) \), atualize a melhor posição conhecida do enxame: \( g \leftarrow p_i \).
- Inicialize a velocidade da partícula: \( v_i \sim U(-|b_{up}-b_{lo}|, |b_{up}-b_{lo}|) \).
- Enquanto um critério de terminação não for atendido:
- Para cada partícula \( i = 1, \dots, S \):
- Para cada dimensão \( d = 1, \dots, n \):
- Escolha números aleatórios \( r_p, r_g \sim U(0,1) \).
- Atualize a velocidade da partícula: \( v_{i,d} \leftarrow w v_{i,d} + \phi_p r_p (p_{i,d} - x_{i,d}) + \phi_g r_g (g_d - x_{i,d}) \).
- Atualize a posição da partícula: \( x_i \leftarrow x_i + v_i \).
- Se \( f(x_i) < f(p_i) \), atualize a melhor posição conhecida da partícula: \( p_i \leftarrow x_i \).
- Se \( f(p_i) < f(g) \), atualize a melhor posição conhecida do enxame: \( g \leftarrow p_i \).
Os valores \( b_{lo} \) e \( b_{up} \) representam os limites inferior e superior do espaço de busca. O parâmetro \( w \) é o peso de inércia. Os parâmetros \( \phi_p \) e \( \phi_g \) são frequentemente chamados de coeficiente cognitivo e coeficiente social. O critério de terminação pode ser o número de iterações realizadas ou uma solução onde um valor adequado da função objetivo é encontrado. Os parâmetros \( w \), \( \phi_p \) e \( \phi_g \) são selecionados pelo praticante e controlam o comportamento e a eficácia do método PSO.
Seleção de Parâmetros
A escolha dos parâmetros da PSO pode ter um grande impacto no desempenho da otimização. Selecionar parâmetros que produzam bom desempenho tem sido objeto de muita pesquisa. Para evitar divergência ("explosão"), o peso de inércia deve ser menor que 1. Os outros dois parâmetros podem ser derivados usando a abordagem de constrição ou selecionados livremente, mas análises sugerem domínios de convergência para restringi-los. Valores típicos estão na faixa [1, 3]. Os parâmetros da PSO também podem ser ajustados usando outro otimizador sobreposto, um conceito conhecido como meta-otimização, ou até mesmo refinados durante a otimização, por exemplo, por meio de lógica fuzzy. Parâmetros também foram ajustados para vários cenários de otimização.
Vizinhanças 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 do enxame. Essa topologia permite que todas as partículas se comuniquem com todas as outras, então todo o enxame compartilha a mesma melhor posição \( g \) de uma única partícula. No entanto, essa abordagem pode levar o enxame a ficar preso em um mínimo local, então diferentes topologias foram usadas para controlar o fluxo de informações entre as partículas. Por exemplo, em topologias locais, as partículas só compartilham informações com um subconjunto de partículas. Esse 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 qualquer distância. Nesses casos, a variante da PSO é dita de melhor local (em oposição ao melhor global para a PSO básica). Uma topologia de enxame comumente usada é o anel, no qual cada partícula tem apenas dois vizinhos, mas existem muitas outras. A topologia não é necessariamente estática; pode mudar durante o processo de otimização.
Aplicações e Métodos Relacionados
A PSO foi aplicada a uma ampla gama de problemas de otimização em campos como engenharia, economia e aprendizado de máquina. É particularmente útil quando o espaço de busca é grande e a função objetivo é não diferenciável ou ruidosa. A PSO compartilha semelhanças com outras meta-heurísticas baseadas em população, como algoritmos genéticos e otimização por colônia de formigas, mas se distingue pelo seu mecanismo de atualização de velocidade inspirado no comportamento social. No contexto de aprendizado de máquina, a PSO pode ser usada para ajuste de hiperparâmetros ou treinamento de redes neurais, embora seja frequentemente comparada com métodos baseados em gradiente. Sua natureza estocástica e a falta de requisitos de gradiente a tornam uma ferramenta versátil no campo mais amplo da inteligência artificial.