Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax
Moritz Mühlenthaler, Alexander Raß, Manuel Schmitt, Andreas Siegling, Rolf Wanka · 2017
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.