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

Beitrag bei einer Tagung
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Raß A, Schreiner J, Wanka R
Herausgeber: Springer International Publishing
Verlagsort: Cham
Jahr der Veröffentlichung: 2019
Tagungsband: Evolutionary Computation in Combinatorial Optimization
Seitenbereich: 115-130
ISBN: 978-3-030-16711-0
Sprache: Englisch


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-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

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


Zitierweisen

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: 

Zuletzt aktualisiert 2019-17-04 um 08:42