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

Conference contribution
(Original article)


Publication Details

Author(s): Raß A, Schreiner J, Wanka R
Editor(s): Springer International Publishing
Publishing place: Cham
Publication year: 2019
Conference Proceedings Title: Evolutionary Computation in Combinatorial Optimization
Pages range: 115-130
ISBN: 978-3-030-16711-0
Language: English


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.


FAU Authors / FAU Editors

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


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: 

Last updated on 2019-17-04 at 08:42