Particle Swarm Optimization
๐ฅ Vibe Prompt
"Minimize Rastrigin function in 5D: f(x)=10n+sum(x_i^2 - 10cos(2ฯx_i)). Compare PSO vs Gradient Descent."
import random, math
def rastrigin(x): return 10*len(x) + sum(xi**2 - 10*math.cos(2*math.pi*xi) for xi in x)
class PSO:
def __init__(self, dim, n_particles=50):
self.particles = [[random.uniform(-5.12, 5.12) for _ in range(dim)] for _ in range(n_particles)]
self.velocities = [[random.uniform(-1, 1) for _ in range(dim)] for _ in range(n_particles)]
self.p_best = [p[:] for p in self.particles]
self.g_best = min(self.particles, key=rastrigin)[:]
self.w, self.c1, self.c2 = 0.7, 1.5, 1.5
def step(self):
for i, p in enumerate(self.particles):
for d in range(len(p)):
r1, r2 = random.random(), random.random()
self.velocities[i][d] = (self.w * self.velocities[i][d] +
self.c1*r1*(self.p_best[i][d] - p[d]) +
self.c2*r2*(self.g_best[d] - p[d]))
p[d] += self.velocities[i][d]
if rastrigin(p) < rastrigin(self.p_best[i]):
self.p_best[i] = p[:]
if rastrigin(p) < rastrigin(self.g_best):
self.g_best = p[:]
pso = PSO(dim=5)
for gen in range(100):
pso.step()
if gen % 20 == 0:
print(f"Gen {gen}: best = {rastrigin(pso.g_best):.4f}")
print(f"\nPSO final: {rastrigin(pso.g_best):.4f}")
print(f"Global minimum is 0 at x=(0,...,0)")
Metaheuristic Course Complete! ๐
- โ Hill Climbing
- โ Tabu Search
- โ Simulated Annealing
- โ Genetic Algorithm
- โ Particle Swarm
Key Points
- Understand the core concepts thoroughly
- Practice with hands-on code examples
- Apply knowledge to real-world problems
- Review and reinforce through exercises
Further Learning
- Official documentation
- Open source projects on GitHub
- Community forums and discussions
- Related courses and tutorials
What Is Particle Swarm Optimization?
Particle Swarm Optimization (PSO) is inspired by the social behavior of birds flocking or fish schooling. Each "particle" represents a candidate solution and moves through the search space influenced by its own best position and the swarm's best position.
How PSO Works
Each particle has:
- Position: current candidate solution ($x_i$)
- Velocity: direction and speed of movement ($v_i$)
- pbest: personal best position found so far
- gbest: global best position found by any particle
Velocity Update Formula
$$v_i(t+1) = w \cdot v_i(t) + c_1 \cdot r_1 \cdot (pbest_i - x_i) + c_2 \cdot r_2 \cdot (gbest - x_i)$$
$$x_i(t+1) = x_i(t) + v_i(t+1)$$
Where:
- $w$ = inertia weight (balances exploration vs exploitation)
- $c_1$ = cognitive coefficient (trust in self)
- $c_2$ = social coefficient (trust in swarm)
- $r_1, r_2$ = random values in [0, 1]
Parameter Guide
| Parameter | Typical Range | Effect | |-----------|---------------|--------| | Inertia (w) | 0.4 - 0.9 | Higher = more exploration | | Cognitive (cโ) | 1.0 - 2.0 | Trust in personal best | | Social (cโ) | 1.0 - 2.0 | Trust in swarm best | | Swarm size | 10 - 100 | More particles = better coverage |
Python Implementation
import random
import math
class Particle:
def __init__(self, dim, bounds):
self.position = [random.uniform(b[0], b[1]) for b in bounds]
self.velocity = [random.uniform(-1, 1) for _ in range(dim)]
self.pbest = self.position.copy()
self.pbest_value = float('inf')
def particle_swarm_optimization(
cost_func,
dim=2,
bounds=[(-10, 10), (-10, 10)],
swarm_size=30,
w=0.7,
c1=1.5,
c2=1.5,
max_iter=100
):
# Initialize swarm
swarm = [Particle(dim, bounds) for _ in range(swarm_size)]
gbest = swarm[0].position.copy()
gbest_value = float('inf')
for iteration in range(max_iter):
for particle in swarm:
# Evaluate cost
value = cost_func(particle.position)
# Update personal best
if value < particle.pbest_value:
particle.pbest = particle.position.copy()
particle.pbest_value = value
# Update global best
if value < gbest_value:
gbest = particle.position.copy()
gbest_value = value
# Update velocities and positions
for particle in swarm:
for i in range(dim):
r1, r2 = random.random(), random.random()
# Velocity update
cognitive = c1 * r1 * (particle.pbest[i] - particle.position[i])
social = c2 * r2 * (gbest[i] - particle.position[i])
particle.velocity[i] = w * particle.velocity[i] + cognitive + social
# Position update
particle.position[i] += particle.velocity[i]
# Clamp to bounds
particle.position[i] = max(bounds[i][0], min(bounds[i][1], particle.position[i]))
if iteration % 20 == 0:
print(f"Iter {iteration}: best = {gbest_value:.6f}")
return gbest, gbest_value
# Example: Minimize Rastrigin function (many local minima)
def rastrigin(x):
A = 10
return A * len(x) + sum((xi**2 - A * math.cos(2 * math.pi * xi)) for xi in x)
best_pos, best_val = particle_swarm_optimization(
cost_func=rastrigin,
dim=2,
bounds=[(-5.12, 5.12), (-5.12, 5.12)],
swarm_size=30,
max_iter=200
)
print(f"\nBest position: {best_pos}")
print(f"Best value: {best_val:.6f}")
print(f"Expected minimum: 0.0 at (0, 0)")
PSO vs Simulated Annealing
| Aspect | PSO | Simulated Annealing | |--------|-----|-------------------| | Population | Multiple particles | Single candidate | | Memory | Remembers pbest and gbest | No memory | | Parallelizable | โ Yes (evaluate particles in parallel) | โ Sequential | | Parameters | 3 (w, c1, c2) | 3 (Tโ, ฮฑ, max_iter) | | Best for | Continuous optimization | Combinatorial optimization |
Summary
PSO mimics bird flocking to find optimal solutions. Particles share information through pbest (personal) and gbest (global), balancing exploration and exploitation.
Key takeaways: | PSO: inspired by bird flocking โ particles share info via pbest and gbest | | Velocity = inertia ร old velocity + cognitive + social components | | Inertia (w): high = explore, low = exploit | | Cognitive (cโ): trust in own best position | | Social (cโ): trust in swarm's best position | | Swarm size: 30 particles is a good default | | Rastrigin function: many local minima at integer coordinates, global min at (0,0) | | PSO is parallelizable โ evaluate all particles simultaneously |
Next Chapter: Genetic Algorithm
The next chapter covers Genetic Algorithms.