 |
Particle Swarm Optimization
By Joey Harrison and Ankur Desai
|
Particle Swarm Optimization (PSO) is a population-oriented stochastic search technique similar to genetic algorithms, evolutionary strategies, and other evolutionary computation algorithms. The technique discovers solutions for N-dimensional parameterized problems: basically it discovers the point in N-dimensional space which maximizes some quality function.
PSO works approximately as follows: a "swarm" of candidate solutions ("particles") are placed randomly throughout the space and with a random initial velocity. Each particle measures the quality of its present location in space. This velocity vector affects how each particle moves in the space, and it is changed each timestep according to a weighted sum of the following values:
- A vector towards the personal best-quality location the particle has been.
- A vector towards the global best-quality location any member of the swarm has ever visited.
- A vector towards the "neighborhood best": all the particles are organized beforehand in a list. A particle's neighborhood are himself and the M individuals on either side of him. The neighborhood best is the best-quality location any neighbor ever visited.
- The particle's previous velocity vector.
This simulation applies a swarm of particles to simple two-dimensional problems sufficient for visualization. The model parameters are:
- NumParticles: how many particles are placed in the space.
- NeighborhoodSize: the size of the particle's "neighborhood", including himself.
- InitialVelocityRange: the range of possible initial velocities, which are randomly chosen.
- VelocityScalar: multiplies the final velocity vector by a constant (causing the particles to move more rapidly or more cautiously). A smaller value will cause particles to tend to get stuck in local optima more easily. A higher value will cause particles to move more rapidly towards good solutions, but they then cannot converge to precise locations as easily. Very large velocity values cause the swarm to become unstable.
- FitnessFunction: the quality function applied to the space. "Better" values are higher. There are several available functions, all common to the stochastic search literature:
- Rastrigin. 1000 - (20 + x2 - 10 cos(2 Pi x) + y2 - 10 cos(2 Pi y))
- Booth. 1000 - ((x + 2 y - 7)2 + (2 x + y - 5)2
- Griewangk. 1000 - (1+ (x2 / 4000) + y2/4000 - cos(x) cos(y / sqrt(2))
- Rosenbrock. 1000 - (100 (x2 - y) + (1 - x)2
- SuccessThreshold: A particle must reach this close to 1000 in order to be considered "optimal". The simulation terminates when all particles have moved to within this threshold.