Particle swarm optimization
|
|
Particle swarm optimization (PSO) is form of swarm intelligence. Imagine a swarm of insects or a school of fish. If one sees a desirable 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 and remember the best position that they have seen. Members of a swarm communicate good positions to each other and adjust their own position and velocity based on these good positions. 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:
- <math> x \leftarrow x + v <math>
- <math> v \leftarrow wv + c_1 r_1 (\hat{x}-x) + c_2 r_2 (\hat{x}_g-x) <math>
- <math>w<math> is the inertial constant. Good values are usually slightly less than 1.
- <math>c_1<math> and <math>c_2<math> are constants that say how much the particle is directed towards good positions. Good values are usually right around 1.
- <math>r_1<math> and <math>r_2<math> are random values in the range <math>[0, 1]<math>.
- <math>\hat{x}<math> is the best the particle has seen.
- <math>\hat{x}_g<math> is the global best seen by the swarm. This can be replaced by <math>\hat{x}_l<math>, the local best, if neighborhoods are being used.
Algorithm
- Initialize <math>x<math> and <math>v<math> of each particle to a random value. The range of these values may be domain specific.
- Initialize each <math>\hat{x}<math> to the current position.
- Initialize <math>\hat{x}_g<math> to the position that has the best fitness in the swarm.
- Loop while the fitness of <math>\hat{x}_g<math> is below a threshold and the number of iterations is less than some predetermined maximum.
- For each particle do the following:
- Update <math>x<math> according to the above equation.
- Calculate fitness for new position.
- If it is better than the fitness of <math>\hat{x}<math> replace it.
- It it is better than the fitness of <math>\hat{x}_g<math> replace it.
- Update <math>v<math> according to the above equation.
- For each particle do the following: