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
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 |