Repulsive particle swarm optimization

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)
*$omega$ : 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 cite web | url = http://portal.acm.org/citation.cfm?id=998671.999056 | title = Urfalioglu, O., Robust estimation of camera rotation, translation and focal length at high outlier rates, CRV04] .

References

ee also

*Particle swarm optimization
*Ant colony optimization
*Genetic algorithm
*Swarm intelligence

External links

* [http://psotoolbox.sourceforge.net Particle Swarm Optimization toolbox] An open source PSO toolbox written in Matlab. * [http://www.particleswarm.info Particle Swarm Central ]
* [http://www1.webng.com/economics FORTRAN Codes for RPSO] FORTRAN 77 Codes for Repulsive Particle Swarm Optimization with a large number of test problems