A particle swarm searching for the global minimum of a function

In computational science, particle swarm optimization (PSO)^[1] is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. It solves a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formula over the particle's position and velocity. Each particle's movement is influenced by its local best known position, but is also guided toward the best known positions in the search-space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions.

PSO is originally attributed to Kennedy, Eberhart and Shi^[2][3] and was first intended for simulating social behaviour,^[4] as a stylized representation of the movement of organisms in a bird flock or fish school. The algorithm was simplified and it was observed to be performing optimization. The book by Kennedy and Eberhart^[5] describes many philosophical aspects of PSO and swarm intelligence. An extensive survey of PSO applications is made by Poli.^[6][7] Recently, a comprehensive review on theoretical and experimental works on PSO has been published by Bonyadi and Michalewicz.^[1]

PSO is a metaheuristic as it makes few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. Also, PSO does not use the gradient of the problem being optimized, which means PSO does not require that the optimization problem be differentiable as is required by classic optimization methods such as gradient descent and quasi-newton methods. However, metaheuristics such as PSO do not guarantee an optimal solution is ever found.

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.^[8] 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: ℝⁿ → ℝ be the cost function which must be minimized. The function takes a candidate solution as an 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.

Let S be the number of particles in the swarm, each having a position x_i ∈ ℝⁿ in the search-space and a velocity v_i ∈ ℝⁿ. 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 to minimize the cost function is then:^[9]

for each particle i = 1, ..., S do
    Initialize the particle's position with a uniformly distributed random vector: xi ~ U(blo, bup)
    Initialize the particle's best known position to its initial position: pi ← xi
    if f(pi) < f(g) then
        update the swarm's best known position: g ← pi
    Initialize the particle's velocity: vi ~ U(-|bup-blo|, |bup-blo|)
while a termination criterion is not met do:
    for each particle i = 1, ..., S do
        for each dimension d = 1, ..., n do
            Pick random numbers: rp, rg ~ U(0,1)
            Update the particle's velocity: vi,d ← w vi,d + φp rp (pi,d-xi,d) + φg rg (gd-xi,d)
        Update the particle's position: xi ← xi + vi
        if f(xi) < f(pi) then
            Update the particle's best known position: pi ← xi
            if f(pi) < f(g) then
                Update the swarm's best known position: g ← pi

The values b_lo and b_up represent the lower and upper boundaries of the search-space respectively. The w parameter is the inertia weight. The parameters φ_p and φ_g are often called cognitive coefficient and social coefficient.

The termination criterion can be the number of iterations performed, or a solution where the adequate objective function value is found.^[10] The parameters w, φ_p, and φ_g are selected by the practitioner and control the behaviour and efficacy of the PSO method (below).

Parameter selection

Performance landscape showing how a simple PSO variant performs in aggregate on several benchmark problems when varying two PSO parameters.

The choice of PSO parameters can have a large impact on optimization performance. Selecting PSO parameters that yield good performance has therefore been the subject of much research.^{[11][12][13][14][15][16][17][18][19]}

To prevent divergence ("explosion") the inertia weight must be smaller than 1. The two other parameters can be then derived thanks to the constriction approach,^[16] or freely selected, but the analyses suggest convergence domains to constrain them. Typical values are in ${\displaystyle [1,3]}$.

The PSO parameters can also be tuned by using another overlaying optimizer, a concept known as meta-optimization,^{[20][21][22][23]} or even fine-tuned during the optimization, e.g., by means of fuzzy logic.^[24][25]

Parameters have also been tuned for various optimization scenarios.^[26][27]

Neighbourhoods and topologies

The topology of the swarm defines the subset of particles with which each particle can exchange information.^[28] The basic version of the algorithm uses the global topology as the swarm communication structure.^[10] This topology allows all particles to communicate with all the other particles, thus the whole swarm share the same best position g from a single particle. However, this approach might lead the swarm to be trapped into a local minimum,^[29] thus different topologies have been used to control the flow of information among particles. For instance, in local topologies, particles only share information with a subset of particles.^[10] This subset can be a geometrical one^[30] – for example "the m nearest particles" – or, more often, a social one, i.e. a set of particles that is not depending on any distance. In such cases, the PSO variant is said to be local best (vs global best for the basic PSO).

A commonly used swarm topology is the ring, in which each particle has just two neighbours, but there are many others.^[10] The topology is not necessarily static. In fact, since the topology is related to the diversity of communication of the particles,^[31] some efforts have been done to create adaptive topologies (SPSO,^[32] APSO,^[33] stochastic star,^[34] TRIBES,^[35] Cyber Swarm,^[36] and C-PSO^[37])

Inner workings

There are several schools of thought as to why and how the PSO algorithm can perform optimization.

A common belief amongst researchers is that the swarm behaviour varies between exploratory behaviour, that is, searching a broader region of the search-space, and exploitative behaviour, that is, a locally oriented search so as to get closer to a (possibly local) optimum. This school of thought has been prevalent since the inception of PSO.^{[3][4][12][16]} This school of thought contends that the PSO algorithm and its parameters must be chosen so as to properly balance between exploration and exploitation to avoid premature convergence to a local optimum yet still ensure a good rate of convergence to the optimum. This belief is the precursor of many PSO variants, see below.

Another school of thought is that the behaviour of a PSO swarm is not well understood in terms of how it affects actual optimization performance, especially for higher-dimensional search-spaces and optimization problems that may be discontinuous, noisy, and time-varying. This school of thought merely tries to find PSO algorithms and parameters that cause good performance regardless of how the swarm behaviour can be interpreted in relation to e.g. exploration and exploitation. Such studies have led to the simplification of the PSO algorithm, see below.

Variants

Numerous variants of even a basic PSO algorithm are possible. For example, there are different ways to initialize the particles and velocities (e.g. start with zero velocities instead), how to dampen the velocity, only update p_i and g after the entire swarm has been updated, etc. Some of these choices and their possible performance impact have been discussed in the literature.^[14]

A series of standard implementations have been created by leading researchers, "intended for use both as a baseline for performance testing of improvements to the technique, as well as to represent PSO to the wider optimization community. Having a well-known, strictly-defined standard algorithm provides a valuable point of comparison which can be used throughout the field of research to better test new advances."^[10] The latest is Standard PSO 2011 (SPSO-2011).^[45]

See also

• Artificial bee colony algorithm
• Bees algorithm
• Derivative-free optimization
• Multi-swarm optimization
• Particle filter
• Swarm intelligence
• Fish School Search
• Dispersive flies optimisation

References

External links

Wikimedia Commons has media related to Particle swarm optimization.

• Particle Swarm Central is a repository for information on PSO. Several source codes are freely available.
• A brief video of particle swarms optimizing three benchmark functions.
• Simulation of PSO convergence in a two-dimensional space (Matlab).
• Applications of PSO.
• Liu, Yang (2009). "Automatic calibration of a rainfall–runoff model using a fast and elitist multi-objective particle swarm algorithm". Expert Systems with Applications. 36 (5): 9533–9538. doi:10.1016/j.eswa.2008.10.086.
• Links to PSO source code