Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax

Mühlenthaler M, Raß A, Schmitt M, Siegling A, Wanka R (2017)


Publication Language: English

Publication Type: Conference contribution

Publication year: 2017

Pages Range: 13-24

Conference Proceedings Title: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Event location: Copenhagen, Denmark DK

ISBN: 978-1-4503-4651-1

DOI: 10.1145/3040718.3040721

Abstract

We present the analysis of a discrete particle swarm optimization (PSO) algorithm that works on a significantly large class of discrete optimization problems. Assuming a black-box setting, we prove upper and lower bounds on the expected number of function evaluations required by the proposed algorithm to solve the sorting problem and the problem of maximizing the number of ones in a bitstring, i.e., the function OneMax. We show that depending on the probability of moving towards the attractor, the expected optimization time may be polynomial or exponential. The cornerstone of our analysis are Theta-bounds on the expected time it takes until the PSO returns to the attractor. We obtain these bounds by solving linear recurrence equations with constant and non-constant coefficients. We also introduce a useful indistinguishability property of states of a Markov chain in order to obtain lower bounds on the expected optimization time of our proposed PSO algorithm.

Authors with CRIS profile

Related research project(s)

Involved external institutions

How to cite

APA:

Mühlenthaler, M., Raß, A., Schmitt, M., Siegling, A., & Wanka, R. (2017). Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax. In ACM New York, NY, USA (Eds.), Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (pp. 13-24). Copenhagen, Denmark, DK.

MLA:

Mühlenthaler, Moritz, et al. "Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax." Proceedings of the Conference on Foundations of Genetic Algorithms (FOGA), Copenhagen, Denmark Ed. ACM New York, NY, USA, 2017. 13-24.

BibTeX: Download