Aprenda Otimização por Enxame de Partículas | Algoritmos Baseados em Enxames

Definição

O Particle Swarm Optimization (PSO) é um algoritmo bioinspirado baseado em população que se inspira no comportamento coletivo de bandos de pássaros e cardumes de peixes. No PSO, trabalha-se com um enxame de agentes simples chamados de partículas. Cada partícula representa uma solução potencial para o problema de otimização e se move pelo espaço de busca atualizando sua posição e velocidade.

Conceitos Centrais

O movimento de cada partícula é influenciado por dois fatores principais:

Melhor Pessoal: A melhor posição conhecida que a própria partícula encontrou até o momento;
Melhor Global: A melhor posição conhecida encontrada por todo o enxame em qualquer ponto durante a busca.

Essa dinâmica permite que o enxame explore o espaço de soluções de forma eficiente, equilibrando exploração (busca em novas áreas) e exploração (refinamento de áreas já conhecidas como boas), à medida que as partículas se comunicam e aprendem umas com as outras.

Conceitos-chave no PSO:

Partículas: agentes que representam soluções possíveis;
Posição: a localização atual de uma partícula no espaço de busca;
Velocidade: direção e velocidade do movimento da partícula;
Melhor posição pessoal: a melhor posição encontrada por cada partícula até o momento;
Melhor posição global: a melhor posição encontrada por qualquer partícula do enxame.

Ao atualizar iterativamente posições e velocidades com base nesses princípios, o PSO permite resolver problemas complexos de otimização de maneira flexível e eficiente.

Exemplo: Implementação Básica de PSO


              123456789101112131415161718192021222324252627282930313233343536373839404142434445
            
import numpy as np

# Objective function: simple 1D quadratic (minimum at x=3)
def objective(x):
    return (x - 3) ** 2 + 2

# PSO parameters
num_particles = 20
num_iterations = 50
w = 0.5  # Inertia coefficient
c1 = 1.5  # Cognitive (personal) coefficient
c2 = 1.5  # Social (global) coefficient

# Initialize particle positions and velocities
positions = np.random.uniform(-10, 10, num_particles)
velocities = np.zeros(num_particles)
personal_best_positions = positions.copy()
personal_best_scores = objective(positions)
global_best_idx = np.argmin(personal_best_scores)
global_best_position = personal_best_positions[global_best_idx]

# PSO loop
for iteration in range(num_iterations):
    # Evaluate current positions
    scores = objective(positions)
    # Update personal bests
    better_mask = scores < personal_best_scores
    personal_best_scores[better_mask] = scores[better_mask]
    personal_best_positions[better_mask] = positions[better_mask]
    # Update global best
    global_best_idx = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[global_best_idx]
    # Update velocities and positions
    r1 = np.random.rand(num_particles)
    r2 = np.random.rand(num_particles)
    velocities = (
        w * velocities
        + c1 * r1 * (personal_best_positions - positions)
        + c2 * r2 * (global_best_position - positions)
    )
    positions += velocities

print(f"Best position found: {global_best_position:.3f}")
print(f"Objective value: {objective(global_best_position):.3f}")

Passo a Passo: Atualizações de Posição e Velocidade no PSO

Avaliação de Cada Partícula: Para cada partícula, calcular a função objetivo em sua posição atual;
Atualização do Melhor Pessoal: Se a posição atual apresentar um resultado melhor do que qualquer posição anterior, armazená-la como o novo melhor pessoal;
Atualização do Melhor Global: Identificar o melhor resultado entre todos os melhores pessoais e atualizar a posição do melhor global conforme necessário;
Atualização da Velocidade: Para cada partícula, calcular a nova velocidade utilizando:
- O termo de inércia (w * velocity), que incentiva a partícula a continuar se movendo na direção atual;
- O termo cognitivo (c1 * r1 * (personal_best - position)), que direciona a partícula para sua melhor experiência individual;
- O termo social (c2 * r2 * (global_best - position)), que direciona a partícula para o melhor resultado encontrado pelo enxame;
Atualização da Posição: Somar a nova velocidade à posição atual para obter a nova localização da partícula no espaço de busca.

As partículas repetem esses passos por um número definido de iterações ou até que os critérios de convergência sejam atendidos.

Exemplo: Visualização das Trajetórias das Partículas


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
            
import numpy as np
import matplotlib.pyplot as plt

# Objective function: simple 1D quadratic (minimum at x=3)
def objective(x):
    return (x - 3) ** 2 + 2

# PSO parameters
num_particles = 20
num_iterations = 50
w = 0.5  # Inertia coefficient
c1 = 1.5  # Cognitive (personal) coefficient
c2 = 1.5  # Social (global) coefficient

# Re-run the PSO loop, recording particle trajectories
positions = np.random.uniform(-10, 10, num_particles)
velocities = np.zeros(num_particles)
personal_best_positions = positions.copy()
personal_best_scores = objective(positions)
global_best_idx = np.argmin(personal_best_scores)
global_best_position = personal_best_positions[global_best_idx]

trajectories = [positions.copy()]

for iteration in range(num_iterations):
    scores = objective(positions)
    better_mask = scores < personal_best_scores
    personal_best_scores[better_mask] = scores[better_mask]
    personal_best_positions[better_mask] = positions[better_mask]
    global_best_idx = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[global_best_idx]
    r1 = np.random.rand(num_particles)
    r2 = np.random.rand(num_particles)
    velocities = (
        w * velocities
        + c1 * r1 * (personal_best_positions - positions)
        + c2 * r2 * (global_best_position - positions)
    )
    positions += velocities
    trajectories.append(positions.copy())

trajectories = np.array(trajectories)

# Plot trajectories
plt.figure(figsize=(10, 6))
for i in range(num_particles):
    plt.plot(trajectories[:, i], label=f"Particle {i+1}", alpha=0.5)
plt.axhline(3, color='red', linestyle='--', label='Optimum (x=3)')
plt.title('Particle Trajectories in PSO')
plt.xlabel('Iteration')
plt.ylabel('Position')
plt.legend(bbox_to_anchor=(1.05, 1), loc='upper left', fontsize='small')
plt.tight_layout()
plt.show()

Análise de Parâmetros

A escolha dos parâmetros do PSO tem impacto significativo no comportamento e desempenho do algoritmo:

Coeficiente de Inércia (w): Controla quanto da velocidade anterior é mantida;
- Valores mais altos favorecem a exploração e ajudam as partículas a escapar de mínimos locais;
- Valores mais baixos favorecem a exploração e aceleram a convergência.
Coeficiente Cognitivo (c1): Determina a intensidade com que as partículas são atraídas para suas melhores posições individuais;
- Aumentar esse valor incentiva a exploração independente e ajuda a manter a diversidade do enxame.
Coeficiente Social (c2): Regula a atração para a posição do melhor global;
- O aumento desse valor acelera a convergência ao promover o aprendizado coletivo;
- Valores excessivamente altos podem causar estagnação prematura.

A calibração cuidadosa desses coeficientes é essencial para alcançar um desempenho robusto de otimização em diferentes domínios de problemas. Ajuste os parâmetros para equilibrar exploração e exploração, garantindo que as partículas busquem de forma eficaz sem ficarem presas ou convergirem rapidamente demais.

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 3. Capítulo 2

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Deslize para mostrar o menu