Particle swarm optimization

thumb|A particle swarm searching for the [[global minimum of a function]]

In computational science, particle swarm optimization (PSO) Each particle has some neighbors it is connected to, where the neighborhood may be a few or all other population members. The next position of a particle is stochastically determined by its own best-so-far position in the search space as well as the particle's best neighbor's best-so-far position. When an improved position is discovered - one that produces a better result in the objective function - the best-so-far position of the particle is updated. The process is repeated and by doing so it is expected, 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 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 xi ∈ ℝn in the search-space and a velocity vi ∈ ℝn. Let pi be the best known position of particle i and let g be the best known position of the particle's neighborhood. A basic PSO algorithm to minimize the cost function is then: 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. – 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. APSO, stochastic star, TRIBES, Cyber Swarm, and C-PSO

Inner workings

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

As the system iterates and individuals learn from their neighbors, the distances in the search space between a particle and its neighbor tend to become smaller. Thus the “p” and “g” terms in the formula become closer to one another, and the particle takes shorter steps through the search space as the swarm converges on optimal regions that have been discovered. If a new optimal region is found late in the search, the algorithm is able to return to its exploratory behavior, taking large steps again as particles adapt to the new discovery, and gradually converging or clustering around optimal regions.

While the behavior of a single particle is easily conceptualized, a particle by itself has no optimization ability at all; the behavior of the swarm is more difficult to comprehend. 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. that these simplifications do not affect the boundaries found by these studies for parameter where the swarm is convergent. Considerable effort has been made in recent years to weaken the modeling assumption utilized during the stability analysis of PSO, and.

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 pi 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. and the incorporation of an effective learning method. (multi-swarm optimization). The multi-swarm approach can also be used to implement multi-objective optimization. has been proposed in 2003 by James Kennedy, and does not need to use velocity at all.

In this variant of PSO one dispenses with the velocity of the particles and instead updates the positions of the particles using the following simple rule,

:<math>

\vec x_i = G\left(\frac{\vec p_i+\vec g}{2},||\vec p_i-\vec g||\right) \,,

</math>

where <math>\vec x_i</math>, <math>\vec p_i</math> are the position and the best position of the particle <math>i</math>; <math>\vec g</math> is the global best position; <math>G(\vec x,\sigma)</math> is the normal distribution with the mean <math>\vec x</math> and standard deviation <math>\sigma</math>; and where <math>||\dots||</math> signifies the norm of a vector.

Accelerated Particle Swarm Optimization

Another simpler variant is the accelerated particle swarm optimization (APSO), which also does not need to use velocity and can speed up the convergence in many applications. A simple demo code of APSO is available.

In this variant of PSO one dispenses with both the particle's velocity and the particle's best position. The particle position is updated according to the following rule,

:<math>

\vec x_i \leftarrow (1-\beta)\vec x_i + \beta \vec g + \alpha L \vec u \,,

</math>

where <math>\vec u</math> is a random uniformly distributed vector, <math>L</math> is the typical length of the problem at hand, and <math>\beta\sim 0.1-0.7</math> and <math>\alpha\sim 0.1-0.5</math> are the parameters of the method. As a refinement of the method one can decrease <math>\alpha</math> with each iteration, <math>\alpha_n=\alpha_0\gamma^n</math>, where <math>n</math> is the number of the iteration and <math>0 < \gamma < 1</math> is the decrease control parameter.

Multi-objective optimization

PSO has also been applied to multi-objective problems,

However, it can be noted that the equations of movement make use of operators that perform four actions:

computing the difference of two positions. The result is a velocity (more precisely a displacement)
multiplying a velocity by a numerical coefficient
adding two velocities
applying a velocity to a position

Usually a position and a velocity are represented by n real numbers, and these operators are simply -, *, +, and again +. But all these mathematical objects can be defined in a completely different way, in order to cope with binary problems (or more generally discrete ones), or even combinatorial ones. One approach is to redefine the operators based on sets.

<!-- not used

-->

<!-- not used

-->f

External links

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.
Links to PSO source code