% Encoding: UTF-8
@COMMENT{BibTeX export based on data in FAU CRIS: https://cris.fau.de/}
@COMMENT{For any questions please write to cris-support@fau.de}
@inproceedings{faucris.123478564,
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.},
author = {Mühlenthaler, Moritz and Raß, Alexander and Schmitt, Manuel and Siegling, Andreas and Wanka, Rolf},
booktitle = {Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms},
date = {2017-01-12/2017-01-15},
doi = {10.1145/3040718.3040721},
editor = {ACM New York, NY, USA},
faupublication = {yes},
isbn = {978-1-4503-4651-1},
keywords = {Particle Swarm Optimization; Discrete Optimization; Run-time Analysis; Markov Chains},
month = {Jan},
pages = {13-24},
peerreviewed = {unknown},
title = {{Runtime} {Analysis} of a {Discrete} {Particle} {Swarm} {Optimization} {Algorithm} on {Sorting} and {OneMax}},
venue = {Copenhagen, Denmark},
year = {2017}
}