License
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08051.6
URN: urn:nbn:de:0030-drops-14800
URL: https://drops.dagstuhl.de/opus/volltexte/2008/1480/
Go to the corresponding Portal

Sudholt, Dirk ; Witt, Carsten

Runtime Analysis of Binary PSO

pdf-format:
08051.SudholtDirk.Paper.1480.pdf (0.2 MB)

Abstract

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

@InProceedings{sudholt_et_al:DagSemProc.08051.6,
  author =	{Sudholt, Dirk and Witt, Carsten},
  title =	{{Runtime Analysis of Binary PSO}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2008/1480},
  URN =		{urn:nbn:de:0030-drops-14800},
  doi =		{10.4230/DagSemProc.08051.6},
  annote =	{Keywords: Particle swarm optimization, runtime analysis}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI