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 |
|
Seminar: |
|
08051 - Theory of Evolutionary Algorithms
|
|
Issue date: |
|
2008 |
|
Date of publication: |
|
06.05.2008 |
