Runtime Analysis of Discrete Particle Swarm Optimization Applied to Shortest Paths Computation

Raß A, Schreiner J, Wanka R (2019)

Publication Language: English

Publication Type: Conference contribution, Original article

Publication year: 2019

City/Town: Cham

Pages Range: 115-130

Conference Proceedings Title: Evolutionary Computation in Combinatorial Optimization

Event location: Leipzig DE

ISBN: 978-3-030-16711-0

DOI: 10.1007/978-3-030-16711-0_8

Abstract

We mathematically analyze a discrete particle swarm optimization (PSO) algorithm solving the single-source shortest path (SSSP) problem. Key features are an improved and extended study on Markov chains expanding the adaptability of this technique and its application on the ubiquitous SSSP problem. The results are upper and lower bounds on the expected optimization time. For upper bounds, we combine return times within a Markov model with the well known fitness level method which is appropriate even for the non-elitist PSO algorithm. For lower bounds we prove that the recently introduced property of indistinguishability applies in this setting and we also combine it with a further Markov chain analysis.

Authors with CRIS profile

Alexander Raß Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung) Rolf Wanka Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)

Related research project(s)

Partikelschwarm-Optimierung (PSO) July 24, 2008 - Aug. 28, 2020

How to cite

APA:

Raß, A., Schreiner, J., & Wanka, R. (2019). Runtime Analysis of Discrete Particle Swarm Optimization Applied to Shortest Paths Computation. In Springer International Publishing (Eds.), Evolutionary Computation in Combinatorial Optimization (pp. 115-130). Leipzig, DE: Cham.

MLA:

Raß, Alexander, Jonas Schreiner, and Rolf Wanka. "Runtime Analysis of Discrete Particle Swarm Optimization Applied to Shortest Paths Computation." Proceedings of the 19th European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCOP), Leipzig Ed. Springer International Publishing, Cham, 2019. 115-130.

BibTeX: Download