What Is Particle Swarm Optimization?

Particle swarm optimization is a population-based algorithm in which a collection of individual particles move in steps throughout a region. A collection of individuals called particles move in steps throughout a region. At each step, the algorithm evaluates the objective function at each particle. After this evaluation, the algorithm determines the new velocity of each particle. The particles move, then the algorithm reevaluates their objective functions.

The inspiration for the algorithm is a flock of birds or a swarm of insects. Each particle is attracted to the best location it has found so far, and also to the best location any member of the swarm has found. After some steps, the population coalesces around one location, or coalesces around a few locations, or continues to move.

The algorithm is based on a population, not a single current point. In this way, particleswarm is similar to the genetic algorithm (see What Is the Genetic Algorithm?).

At iteration n of the algorithm, a particle has a velocity v(n) that depends on these values:

• The location of the best objective function value that it has encountered, s(n).

• The location of the best objective function value among its neighbors, g(n).

• The previous velocity v(n – 1).

The position of a particle x(n) updates according to its velocity:

$$x(n+1)=x(n)+v(n),$$

adjusted to stay within the bounds.

The velocity of a particle updates approximately according to this equation:

$$v(n+1)=W(n)v(n)+r(1)\left(s(n)-x(n)\right)+r(2)\left(g(n)-x(n)\right).$$

Here, r(1), and r(2) are random scalar values between 0 and 1, and W(n) is an inertia factor that adjusts during the iterations. The full algorithm uses randomly varying neighborhoods and includes modifications when it encounters an improving point. See Particle Swarm Optimization Algorithm.

As shown in this figure, the initial velocities of the particles seem random, but after a few iterations the swarm can converge to a local or even global solution.