Repulsive particle swarm optimization

From Wikipedia, the free encyclopedia

In mathematics, specifically in optimization, repulsive particle swarm optimization (RPSO) is a global optimization algorithm. It belongs to the class of stochastic evolutionary global optimizers, and is a variant of particle swarm optimization (PSO).

There are several different realizations of RPSO. Common to all realizations is the repulsion between particles. This can prevent the swarm being trapped in local maxima, which would cause a premature convergence and would lead the optimization algorithm to fail to find the global optimum.

In one type of this RPSO-class algorithm, the future velocity \mathbf{v}_{\mathrm{next}} of a particle at position \mathbf{x} with a recent velocity \mathbf{v} is calculated by

\mathbf{v}_{\mathrm{next}} = \omega \mathbf{v} + a \ \chi_1 \ (-\mathbf{x}+\hat{\mathbf{x}}) + b \ \chi_2 \ \omega (-\mathbf{x}+\hat{\mathbf{y}}) + c \ \chi_3 \ \omega \ \mathbf{z}

where

  • \chi_1,\ \chi_2,\ \chi_3 : random numbers \in [0,\ 1](different at each iteration)
  • ω : inertia weight \in [0.01,\ 0.7]
  • \hat{\mathbf{x}} : best position of a particle
  • \hat{\mathbf{y}} : best position of a randomly chosen other particle from within the swarm
  • \mathbf{z} : a random velocity vector
  • a,b,c : constants

The repulsion property is realized for a negative b. The main difference between PSO and RPSO is the propagation mechanism to determine new positions for a particle in the search space. RPSO is capable of finding global optima in more complex search spaces. On the other hand, compared to PSO it may be slower on certain types of optimization problems. This type of RPSO was first introduced as an application to a robust estimation problem [1].

[edit] References

  1. ^ Urfalioglu, O., Robust estimation of camera rotation, translation and focal length at high outlier rates, CRV04.

[edit] See also

[edit] External links