Overview
Particle Swarm Optimization (PSO) is form of swarm intelligence. Imagine a swarm of insects or a school of fish. If one sees a desireable path to go (ie for food, protection, etc.) the rest of the swarm will be able to follow quickly even if they are on the opposite side of the swarm.
This is modeled by particles in multidimensional space that have a position and a velocity. These particles are flying through hyperspace but remember the best position that they have seen. Members of a particle swarm can communicate good solutions to each other and adjust their own position and velocity based on that. There are two main ways this communication is done:
- a swarm best that is known to all
- local bests are known in neighborhoods of particles
Updating the position and velocity is done through the following formulas at each iteration:
- p = p + v
- v = w*v + c1*(pparticle best-p) + c2*(pglobal best-p)
Choosing good values for w, c1, and c2 requires much tweaking. Good values are in the range 0-2.
Once a fairly good solution is found the optizimation is finished.
Algorithm
- Initialize the "current position" of each particle to a random value.
- Initialize the "current velocity" of each particle to a random value.
- Initialize each "particle best" to the current position and calculate fitness.
- Initialize the "global best" to the best fitness in the swarm.
- Loop while the "global best" is below a threshold and the number of iterations is less than a max number of iterations.
- for each particle do the following:
- Update position: p = p + v.
- Re-calculate fitness for new position.
- if it is better than the "particle best" replace it.
- it it is better than the "global best" replace it.
- Update velocity: v = w*v + c1*(pparticle best-p) + c2*(pglobal best-p) (The first term is an inertia value. The second term moves the velocity toward the best the particle has seen. The last term moves the velocity towards the best the swarm has seen.)
- for each particle do the following: