Friedrich-Alexander-Universität DruckenUnivisEnglish FAU-Logo
Techn. Fakultät Willkommen am Department Informatik FAU-Logo
Lehrstuhl für Informatik 12
Department Informatik  >  Informatik 12  >  Personal  >  Rolf Wanka  >  Veröffentlichungen  >  SW13b

Particle Swarm Optimization Almost Surely Finds Local Optima

Manuel Schmitt and Rolf Wanka

Department of Computer Science
University of Erlangen-Nuremberg, Germany

Abstract. Particle swarm optimization (PSO) is a popular nature-inspired meta-heuristic for solving continuous optimization problems. Although this technique is widely used, up to now only some partial aspects of the method like trajectories, runtime aspects, the initial behavior in a bounded search space, and parameter selection have been formally investigated. In particular, while it is well-studied how to let the swarm converge to a single point in the search space, no theoretical statements about this point or on the best position any particle has found have been known. For a very general class of objective functions, we provide for the first time results about the quality of the solution found. We show that a slightly adapted PSO almost surely finds a local optimum by investigating the newly defined potential of the swarm. The potential drops when the swarm approaches the point of convergence, but increases if the swarm remains close to a point that is not a local optimum, meaning that the swarm charges potential and continues its movement.

in: Proc. 15th Genetic and Evolutionary Computation Conference (GECCO), pp. 1629-1636, 2013. [Best Paper Award]


BibTex entry

  Impressum Stand: 17 July 2013.   R.W.