Explanation of Stagnation at Points that are not Local Optima in Particle Swarm Optimization by Potential Analysis
Department of Computer Science
University of Erlangen-Nuremberg, Germany
Particle Swarm Optimization (PSO) is a nature-inspired meta-heuristic
for solving continuous optimization problems. In the literature, the
potential of the particles of swarm has been used to show that slightly
modified PSO guarantees convergence to local optima. Here we show that
under specific circumstances the unmodified PSO, even with swarm
parameters known (from the literature) to be good, almost surely does
not yield convergence to a local optimum is provided.
This undesirable phenomenon is called stagnation.
For this purpose, the particles' potential in each dimension is
analyzed mathematically. Additionally, some reasonable assumptions
on the behavior if the particles' potential are made.
Depending on the objective function and, interestingly, the number
of particles, the potential in some dimensions may decrease much faster than in other dimensions. Therefore, these dimensions lose relevance,
i.e., the contribution of their entries to the decisions about attractor updates becomes insignificant and, with positive probability,
they never regain relevance. If Brownian Motion is assumed to be an approximation of the time-dependent drop of potential, practical, i.e.,
large values for this probability are calculated.
Finally, on chosen multidimensional polynomials of degree two,
experiments are provided showing that the required circumstances
occur quite frequently. Furthermore, experiments are provided
showing that even when the very simple sphere function is
processed the described stagnation phenomenon occurs.
Consequently, unmodified PSO does not converge to any local
optimum of the chosen functions for tested parameter settings.
in: Companion of
Proc. 17th Genetic and Evolutionary Computation Conference (GECCO),
pp. 1463-1464, 2015.