Discrete Particle Swarm Optimization for TSP: Theoretical Results and Experimental Evaluations
Department of Computer Science
University of Erlangen-Nuremberg, Germany
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.
Proc. International Conference on Adaptive and Intelligent Systems
(ICAIS); pp. 416-427, 2011.