Authors: Sudholt, Dirk
Witt, Carsten
Title: Runtime analysis of binary PSO
Language (ISO): en
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. The 1-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.
Issue Date: 2008-02
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
24108.pdfDNB235.53 kBAdobe PDFView/Open

This item is protected by original copyright

If no CC-License is given, pleas contact the the creator, if you want to use thre resource other than only read it.