Particle swarm optimization

Particle swarm optimization (PSO) is a 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:

$x\leftarrow x+v$
$v\leftarrow wv+c_{1}r_{1}({\hat {x}}-x)+c_{2}r_{2}({\hat {x}}_{g}-x)$ $v\leftarrow wv+c_{1}r_{1}({\hat {x}}-x)+c_{2}r_{2}({\hat {x}}_{g}-x)$
- $w$ is the inertial constant. Good values are usually slightly less than 1.
- $c_{1}$ and $c_{2}$ are constants that say how much the particle is directed towards good positions. Good values are usually right around 1.
- $r_{1}$ and $r_{2}$ are random values in the range $[0,1]$ .
- ${\hat {x}}$ is the best the particle has seen.
- ${\hat {x}}_{g}$ is the global best seen by the swarm. This can be replaced by ${\hat {x}}_{l}$ , the local best, if neighborhoods are being used.

Algorithm

Initialize $x$ and $v$ of each particle to a random value. The range of these values may be domain specific.
Initialize each ${\hat {x}}$ to the current position.
Initialize ${\hat {x}}_{g}$ to the position that has the best fitness in the swarm.

Loop while the fitness of ${\hat {x}}_{g}$ ${\hat {x}}_{g}$ is below a threshold and the number of iterations is less than some predetermined maximum.
- For each particle do the following:
  - Update $x$ according to the above equation.
  - Calculate fitness for new position.
  - If it is better than the fitness of ${\hat {x}}$ , replace ${\hat {x}}$ .
  - If it is better than the fitness of ${\hat {x}}_{g}$ , replace ${\hat {x}}_{g}$ .
  - Update $v$ according to the above equation.