Discrete Particle Swarm Optimization for TSP: Theoretical Results and Experimental Evaluations

Beitrag bei einer Tagung
(Konferenzbeitrag)


Details zur Publikation

Autorinnen und Autoren: Hoffmann M, Mühlenthaler M, Helwig S, Wanka R
Herausgeber: Bouchachia A.
Verlag: Springer-Verlag
Verlagsort: Berlin, Heidelberg
Jahr der Veröffentlichung: 2011
Tagungsband: Proc. International Conference on Adaptive and Intelligent Systems (ICAIS)
Seitenbereich: 416-427


Abstract


Particle swarm optimization (PSO) is a nature-inspired technique originally designed for solving continuous optimization problems. There already exist several approaches that use PSO also as basis for solving discrete optimization problems, in particular the Traveling Salesperson Problem (TSP). In this paper, (i) we present the first theoretical analysis of a discrete PSO algorithm for TSP which also provides insight into the convergence behavior of the swarm. In particular, we prove that the popular choice of using ``sequences of transpositions'' as the difference between tours tends to decrease the convergence rate. (ii) In the light of this observation, we present a new notion of difference between tours based on ``edge exchanges'' and a new method to combine differences by computing their ``centroid.'' This leads to a more PSO-like behavior of the algorithm and avoids the observed slow down effect. (iii) Then, we investigate implementations of our methods and compare them with previous implementations showing the competitiveness of our new approaches.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Mühlenthaler, Moritz Dr.-Ing.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)
Wanka, Rolf Prof. Dr.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)


Zitierweisen

APA:
Hoffmann, M., Mühlenthaler, M., Helwig, S., & Wanka, R. (2011). Discrete Particle Swarm Optimization for TSP: Theoretical Results and Experimental Evaluations. In Bouchachia A. (Eds.), Proc. International Conference on Adaptive and Intelligent Systems (ICAIS) (pp. 416-427). Klagenfurt: Berlin, Heidelberg: Springer-Verlag.

MLA:
Hoffmann, Matthias, et al. "Discrete Particle Swarm Optimization for TSP: Theoretical Results and Experimental Evaluations." Proceedings of the International Conference on Adaptive and Intelligent Systems (ICAIS), Klagenfurt Ed. Bouchachia A., Berlin, Heidelberg: Springer-Verlag, 2011. 416-427.

BibTeX: 

Zuletzt aktualisiert 2018-08-08 um 22:39