O que é a otimização por enxame de partículas?
A otimizaçao por enxame de partículas (PSO) é um algoritmo meta-heurístico inspirado no comportamento social. Ela foi proposta por Kennedy e Eberhart em 1995, simulando bandos de pássaros ou cardumes. Cada partícula representa uma solução candidata no espaço de busca contínuo. Essas partículas voam pelo espaço ajustando suas posições com base em duas referências. A primeira é a melhor posição que a própria partícula já visitou (memória individual). A segunda é a melhor posição encontrada por qualquer partícula do enxame (memória social). A combinação dessas influências guia o enxame em direção ao ótimo global. Diferentemente dos algoritmos genéticos, o PSO não usa seleção ou crossover. Ele é simples, rápido e requer poucos parâmetros para ser configurado. Portanto, o PSO é uma ferramenta popular para otimização contínua e multimodal.
Características fundamentais do PSO
O PSO possui três características principais que definem seu comportamento. Primeiro, cada partícula tem uma posição (x) e uma velocidade (v) no espaço. A velocidade é atualizada usando uma equação com três componentes: inércia, cognitiva e social. O componente inercial mantém a direção anterior, evitando mudanças bruscas. O componente cognitivo puxa a partícula em direção ao seu melhor histórico pessoal (pbest). O componente social a atrai para a melhor posição global do enxame (gbest). Dois coeficientes (c₁ e c₂) controlam a força de cada componente. Além disso, números aleatórios introduzem estocasticidade para explorar novas regiões. Segundo, o PSO não tem operadores de mutação ou recombinação. Terceiro, ele é completamente paralelizável, pois cada partícula é independente. Essas características tornam o PSO eficiente e fácil de implementar.
Vantagens e aplicações típicas
O PSO é amplamente usado em engenharia, finanças e aprendizado de máquina. Ele é excelente para funções contínuas com muitas variáveis e mínimos locais. Uma grande vantagem é a convergência rápida nas primeiras iterações. Além disso, ele requer pouca memória e é facilmente adaptável a restrições. Contudo, o PSO pode convergir prematuramente para ótimos locais em alguns casos. Para evitar isso, variantes com inércia adaptativa ou enxames multi-objetivo foram criadas. Ainda assim, o PSO é uma das meta-heurísticas mais usadas na indústria.
A dinâmica do PSO é governada por equações de atualização simples. A velocidade é calculada como: v(t+1) = w*v(t) + c₁*r₁*(pbest – x) + c₂*r₂*(gbest – x). A posição é atualizada por: x(t+1) = x(t) + v(t+1). O parâmetro w (inércia) controla o equilíbrio entre exploração e explotação. Valores altos de w incentivam a busca global; valores baixos refinam a busca local. Os coeficientes c₁ e c₂ geralmente são iguais (≈ 1.5 a 2.0) para equilíbrio. As variáveis r₁ e r₂ são números aleatórios uniformes entre 0 e 1. O pbest é atualizado sempre que a partícula encontra uma posição melhor. O gbest é atualizado quando qualquer partícula supera o melhor global atual. Esse mecanismo simples produz um comportamento emergente surpreendente. O enxame converge para o mínimo (ou máximo) sem controle centralizado. O PSO também pode ser usado para problemas com restrições usando penalidades. Ele é frequentemente comparado a algoritmos genéticos e estratégias evolutivas. Assim, o PSO é uma abordagem elegante e poderosa para otimização.
Um exemplo clássico é minimizar a função de Rastrigin em 2 dimensões. Ela tem muitos mínimos locais, mas o mínimo global está em (0,0). O PSO encontra esse ponto com alta precisão após algumas dezenas de iterações. A inércia e os componentes social/cognitivo guiam as partículas até o vale central.
Enunciado do exemplo clássico
Implemente o PSO para minimizar a função de Ackley em 2 dimensões: f(x,y) = -20*exp(-0.2*sqrt(0.5*(x²+y²))) – exp(0.5*(cos(2πx)+cos(2πy))) + 20 + e, com domínio [-5,5]. Use 30 partículas, 200 iterações, w=0.7, c₁=c₂=1.5. Armazene o melhor fitness global e a posição correspondente a cada iteração. Plote a curva de convergência e a trajetória de todas as partículas no plano 2D (com contornos).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
import numpy as np import matplotlib.pyplot as plt # Função de Ackley (minimização) def ackley(x, y): term1 = -20 * np.exp(-0.2 * np.sqrt(0.5 * (x**2 + y**2))) term2 = -np.exp(0.5 * (np.cos(2*np.pi*x) + np.cos(2*np.pi*y))) return term1 + term2 + 20 + np.e # Parâmetros PSO num_particulas = 30 iteracoes = 200 w = 0.7 c1 = 1.5 c2 = 1.5 limites = [-5, 5] dim = 2 # Inicialização posicoes = np.random.uniform(limites[0], limites[1], (num_particulas, dim)) velocidades = np.random.uniform(-1, 1, (num_particulas, dim)) pbest_pos = posicoes.copy() pbest_fit = np.array([ackley(p[0], p[1]) for p in posicoes]) gbest_idx = np.argmin(pbest_fit) gbest_pos = pbest_pos[gbest_idx].copy() gbest_fit = pbest_fit[gbest_idx] # Históricos melhor_fit_hist = [gbest_fit] melhor_pos_hist = [gbest_pos.copy()] trajetorias = [posicoes.copy()] for it in range(iteracoes): # Atualizar velocidade e posição for i in range(num_particulas): r1, r2 = np.random.random(dim), np.random.random(dim) velocidades[i] = (w * velocidades[i] + c1 * r1 * (pbest_pos[i] - posicoes[i]) + c2 * r2 * (gbest_pos - posicoes[i])) posicoes[i] += velocidades[i] posicoes[i] = np.clip(posicoes[i], limites[0], limites[1]) # Avaliar nova aptidão fit_atual = np.array([ackley(p[0], p[1]) for p in posicoes]) # Atualizar pbest for i in range(num_particulas): if fit_atual[i] < pbest_fit[i]: pbest_fit[i] = fit_atual[i] pbest_pos[i] = posicoes[i].copy() # Atualizar gbest if np.min(fit_atual) < gbest_fit: gbest_idx = np.argmin(fit_atual) gbest_fit = fit_atual[gbest_idx] gbest_pos = posicoes[gbest_idx].copy() melhor_fit_hist.append(gbest_fit) melhor_pos_hist.append(gbest_pos.copy()) trajetorias.append(posicoes.copy()) print(f"Melhor fitness encontrado: {gbest_fit:.6f}") print(f"Melhor posição: x={gbest_pos[0]:.6f}, y={gbest_pos[1]:.6f}") # Gráficos plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.semilogy(melhor_fit_hist, 'b-', linewidth=2) plt.title('Convergência do PSO - Ackley') plt.xlabel('Iteração') plt.ylabel('Melhor fitness (escala log)') plt.grid(True) plt.subplot(1, 2, 2) # Contornos x_vals = np.linspace(limites[0], limites[1], 200) y_vals = np.linspace(limites[0], limites[1], 200) X, Y = np.meshgrid(x_vals, y_vals) Z = ackley(X, Y) plt.contourf(X, Y, Z, levels=40, cmap='viridis', alpha=0.6) plt.colorbar(label='f(x,y)') # Trajetórias (plotar a cada 5 iterações para não poluir) for i in range(num_particulas): traj = np.array([t[i] for t in trajetorias[::5]]) plt.plot(traj[:,0], traj[:,1], 'w-', linewidth=0.5, alpha=0.3) plt.scatter(gbest_pos[0], gbest_pos[1], color='red', s=120, edgecolor='white', label='Melhor global') plt.scatter(0, 0, color='white', marker='*', s=200, label='Ótimo teórico') plt.title('Trajetórias das Partículas - PSO') plt.xlabel('x') plt.ylabel('y') plt.legend() plt.grid(True) plt.tight_layout() plt.show() |
Este código implementa o PSO clássico com inércia constante. A curva de convergência mostra uma rápida queda do erro nas primeiras iterações. O gráfico de trajetórias exibe como as partículas exploram o espaço e convergem. Mesmo com muitos mínimos locais, o enxame encontra o ótimo global. Para iniciantes, o PSO demonstra a inteligência coletiva de forma visual e intuitiva. A otimização por enxame de partículas é, portanto, uma técnica acessível e eficaz.