Dirk Sudholt
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 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 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.
- D. Bratton and J. Kennedy. Defining a standard for particle swarm optimization. In Proc. of Swarm Intelligence Symposium (SIS 2007), pages 120--127. IEEE Press, 2007.Google Scholar
Digital Library
- M. Clerc. Particle Swarm Optimization. ISTE, 2006.Google ScholarCross Ref
- B. Doerr, F. Neumann, D. Sudholt, and C. Witt. On the runtime analysis of the 1-ANT ACO algorithm. In Proc. of GECCO '07, pages 33--40. ACM, 2007. Google ScholarDigital Library
- S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1Google Scholar
- 1) evolutionary algorithm. Theor. Comput. Sci., 276:51--81, 2002. Google ScholarDigital Library
- O. Giel and I. Wegener. Evolutionary algorithms and the maximum matching problem. In Proc. of STACS '03, volume 2607 of LNCS, pages 415--426, 2003. Google ScholarDigital Library
- W. J. Gutjahr. First steps to the runtime complexity analysis of Ant Colony Optimization. Computers and Operations Research, 2008. To appear. Google ScholarDigital Library
- W. Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, 58(301):13--30, 1963.Google ScholarCross Ref
- J. Kennedy and R. C. Eberhart. Particle swarm optimization. In Proc. of the IEEE International Conference on Neural Networks, pages 1942--1948. IEEE Press, 1995.Google ScholarCross Ref
- J. Kennedy and R. C. Eberhart. A discrete binary version of the particle swarm algorithm. In Proc. of the World Multiconference on Systemics, Cybernetics and Informatics (WMSCI), pages 4104--4109, 1997.Google ScholarCross Ref
- J. Kennedy, R. C. Eberhart, and Y. Shi. Swarm intelligence. Morgan Kaufmann, 2001. Google ScholarDigital Library
- F. Neumann, D. Sudholt, and C. Witt. Comparing variants of MMAS ACO algorithms on pseudo-boolean functions. In Proc. of SLS 2007, volume 4638 of LNCS, pages 61--75, 2007. Google ScholarDigital Library
- F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theor. Comput. Sci., 378(1):32--40, 2007. Google ScholarDigital Library
- F. Neumann and C. Witt. Runtime analysis of a simple Ant Colony Optimization algorithm. In Proc. of ISAAC '06, volume 4288 of LNCS, pages 618--627. Springer, 2006. Extended version to appear in Algorithmica. Google ScholarDigital Library
- J. Reichel and M. Skutella. Evolutionary algorithms and matroid optimization problems. In GECCO '07, pages 947--954, 2007. Google ScholarDigital Library
- Y. Shi and R. C. Eberhart. Parameter selection in particle swarm optimization. In Proc. of the Seventh Annual Conference on Evolutionary Programming, pages 591--600, 1998. Google ScholarDigital Library
- I. Wegener. Methods for the analysis of evolutionary algorithms on pseudo-boolean functions. In R. Sarker, X. Yao, and M. Mohammadian, editors, Evolutionary Optimization, pages 349--369. Kluwer, 2002.Google Scholar
- C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proc. of STACS '05, volume 3404 of LNCS, pages 44--56, 2005. Google ScholarDigital Library
Index Terms
- Runtime analysis of binary PSO
Recommendations
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,...
Theory of swarm intelligence
GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary ComputationSocial animals as found in fish schools, bird flocks, bee hives, and ant colonies are able to solve highly complex problems in nature. This includes foraging for food, constructing astonishingly complex nests, and evading or defending against predators. ...
Theory of Swarm Intelligence
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary ComputationSocial animals as found in fish schools, bird flocks, bee hives, and ant colonies are able to solve highly complex problems in nature. This includes foraging for food, constructing astonishingly complex nests, and evading or defending against predators. ...
Comments