Runtime analysis of a binary particle swarm optimizer

Dirk Sudholt, Carsten Witt

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    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.
    Original languageEnglish
    JournalTheoretical Computer Science
    Volume411
    Issue number21
    Pages (from-to)2084-2100
    ISSN0304-3975
    DOIs
    Publication statusPublished - 2010

    Fingerprint

    Dive into the research topics of 'Runtime analysis of a binary particle swarm optimizer'. Together they form a unique fingerprint.

    Cite this