2026-07-23T15:54:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1480 2024-03-06T11:07:56Z ddc:004 open_access

Runtime Analysis of Binary PSO Sudholt, Dirk Witt, Carsten Particle swarm optimization runtime analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dirk Sudholt and Carsten Witt 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08051.6 urn:nbn:de:0030-drops-14800 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.6 eng https://creativecommons.org/licenses/by/4.0/legalcode