Swarm Intelligence�Particle Swarm Optimization

CSCI4830/7000�Nikolaus Correll

Algorithm optimization

​

​

​

Describe an algorithm from your practice that requires parameter tuning.

An Optimization Problem

Standard Numerical Approach

More Challenging Problems

A swarming approach to optimization

Left: A herd of wildebeest crossing a river © Eric Inafuku CC BY-SA 2.0.

Right: Slime mold collectively moving in search of food. Middle: a school of fish (big eyed scad) forming a “bait ball” © SteveD. CC BY-SA 2.0. Bottom: a flock of birds migrating.

Two-fold bioinspiration

• Optimization by division of labor in search of a solution
• Local communication to maintain cohesiveness (Reynolds, 1987)
• move toward the center of the flock,
• move at around the same speed than the flock,
• repel from each other when becoming too close.

Implementation: Particle Swarm Optimization

Assign random values to x_i

Do

For i = 1 to N

if f(x_i) < f(p_i) then p_i=x_i // update particle’s previous best

g = min_i(p_i) // update global best

v_i=wv_i+r₁(p_i-x_i)+r₂(g-x_i) // calculate speed

x_i=x_i+v_i // move all particles

end

until termination criterion is met

​

Good parameters:

w=0.7298 with r₁ and r₂ random values in the interval from [0;1.49618]

MATLAB DEMO

Issues

• Difficult to prove convergence, even to local optima
• Difficult to chose parameters
• Inertia weight, “constriction parameters”, magnitude of random search
• Neighborhood for “global best”: star, ring, solution space
• Difficult to determine convergence criterion

Applications

• Unlike gradient-descent, PSO can work with non-continuous fitness functions
• Optimize the input parameters of almost any algorithm with a simple objective function
• Computer vision / object recognition
• Weights of a neural network
• PSO itself
• ...