Particle Swarm Optimization - Algorithm

Algorithm

A basic variant of the PSO algorithm works by having a population (called a swarm) of candidate solutions (called particles). These particles are moved around in the search-space according to a few simple formulae. The movements of the particles are guided by their own best known position in the search-space as well as the entire swarm's best known position. When improved positions are being discovered these will then come to guide the movements of the swarm. The process is repeated and by doing so it is hoped, but not guaranteed, that a satisfactory solution will eventually be discovered.

Formally, let f: ℝn → ℝ be the cost function which must be minimized. The function takes a candidate solution as argument in the form of a vector of real numbers and produces a real number as output which indicates the objective function value of the given candidate solution. The gradient of f is not known. The goal is to find a solution a for which f(a) ≤ f(b) for all b in the search-space, which would mean a is the global minimum. Maximization can be performed by considering the function h = -f instead.

Let S be the number of particles in the swarm, each having a position x_i ∈ ℝn in the search-space and a velocity v_i ∈ ℝn. Let p_i be the best known position of particle i and let g be the best known position of the entire swarm. A basic PSO algorithm is then:

• For each particle i = 1, ..., S do:
  • Initialize the particle's position with a uniformly distributed random vector: x_i ~ U(b_lo, b_up), where b_lo and b_up are the lower and upper boundaries of the search-space.
  • Initialize the particle's best known position to its initial position: p_i ← x_i
  • If (f(p_i) < f(g)) update the swarm's best known position: g ← p_i
  • Initialize the particle's velocity: v_i ~ U(-|b_up-b_lo|, |b_up-b_lo|)
• Until a termination criterion is met (e.g. number of iterations performed, or a solution with adequate objective function value is found), repeat:
  • For each particle i = 1, ..., S do:
    • For each dimension d = 1, ..., n do:
      • Pick random numbers: r_p, r_g ~ U(0,1)
      • Update the particle's velocity: v_i,d ← ω v_i,d + φ_p r_p (p_i,d-x_i,d) + φ_g r_g (g_d-x_i,d)
    • Update the particle's position: x_i ← x_i + v_i
    • If (f(x_i) < f(p_i)) do:
      • Update the particle's best known position: p_i ← x_i
      • If (f(p_i) < f(g)) update the swarm's best known position: g ← p_i
• Now g holds the best found solution.

The parameters ω, φ_p, and φ_g are selected by the practitioner and control the behaviour and efficacy of the PSO method, see below.