Runtime analysis of a binary particle swarm optimizer

We investigate the runtime of a binary Particle Swarm Optimizer (PSO) for optimizing pseudo-Boolean functions f:{0,1}n→R. The binary PSO maintains a swarm of particles searching for good solutions. Each particle consists of a current position from {0,1}n, its own best position and a velocity vector used in a probabilistic process to update its current position.

The velocities for a particle are then updated in the direction of its own best position and the position of the best particle in the swarm.We present a lower bound for the time needed to optimize any pseudo-Boolean function with a unique optimum. To prove upper bounds we transfer a fitness-level argument that is well-established for evolutionary algorithms (EAs) to PSO.

This method is applied to estimate the expected runtime for the class of unimodal functions. A simple variant of the binary PSO is considered in more detail for the test function OneMax, showing that there the binary PSO is competitive to EAs. An additional experimental comparison reveals further insights.