 |
3D 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.
For no particularly good reason, the PSO 3D version has a different notion of "neighborhood" than the 2D version. Rather than organize the particles in a ring, and letting a particle's "neighborhood" be the M individuals on either side of the particle, the 3D version simply groups the particles into P disjoint sets ("neighborhoods"). We realize this is a nonstandard approach in PSO but thought it would be interesting to try.
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": the best particle in the the particle's neighborhood as described earlier.
- 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:
- NumParticlesPerNeighborhood: how many particles are in each "neighborhood" set.
- NumNeighborhoods: how many neighborhoods there are.
- 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 - (30 + x2 - 10cos(2 Pi x) + y2 - 10cos(2 Pi y) + z2 - 10cos(2 Pi z))
- Griewangk. 1000 - (1 + (x2 + y2 + z2) / 4000 - (cos(x)*cos(y / 2.5)*cos(z / 3.5)))
- Rosenbrock. 1000 - (100 * ((x2 - y)*(x2 - y) + (1-x)2 + ((y2 - z)*(y2 - z) + (1-y)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.