| Runtime Analysis of Binary PSO (2008) | |||||||||||||
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.. @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} } | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||