License
When quoting this document, please refer to the following
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:DSP:2008:1480,
  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 =		{http://drops.dagstuhl.de/opus/volltexte/2008/1480},
  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