When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-14800
Go to the corresponding Portal

Sudholt, Dirk ; Witt, Carsten

Runtime Analysis of Binary PSO

08051.SudholtDirk.Paper.1480.pdf (0.2 MB)


We investigate the runtime of the Binary Particle Swarm Optimization (PSO) algorithm introduced by Kennedy and Eberhart (1997). The Binary PSO maintains a global best solution and a swarm of particles. Each particle consists of a current position, an own best position and a velocity vector used in a probabilistic process to update the particle's position. We present lower bounds for a broad class of implementations with swarms of polynomial size. To prove upper bounds, we transfer a fitness-level argument well-established for evolutionary algorithms (EAs) to PSO. This method is then applied to estimate the expected runtime on the class of unimodal functions. A simple variant of the Binary PSO is considered in more detail. The1-PSO only maintains one particle, hence own best and global best solutions coincide. Despite its simplicity, the 1-PSO is surprisingly efficient. A detailed analysis for the function Onemax shows that the 1-PSO is competitive to EAs.

BibTeX - Entry

  author =	{Dirk Sudholt and Carsten Witt},
  title =	{Runtime Analysis of Binary PSO},
  booktitle =	{Theory of Evolutionary Algorithms},
  year =	{2008},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  number =	{08051},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Particle swarm optimization, runtime analysis}

Keywords: Particle swarm optimization, runtime analysis
Seminar: 08051 - Theory of Evolutionary Algorithms
Issue Date: 2008
Date of publication: 06.05.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI