Conference contribution


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


Publication Details
Author(s): Mühlenthaler M, Raß A, Schmitt M, Siegling A, Wanka R
Editor(s): ACM New York, NY, USA
Publication year: 2017
Conference Proceedings Title: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
Pages range: 13-24
ISBN: 978-1-4503-4651-1

Event details
Event: Conference on Foundations of Genetic Algorithms (FOGA)
Event location: Copenhagen, Denmark
Start date of the event: 12/01/2017
End date of the event: 15/01/2017
Language: English

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.



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).

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


External Organisations
Share link
Last updated on 2017-09-23 at 03:52
PDF downloaded successfully