Title: Hybrid particle swarm optimisation with k-centres method and dynamic velocity range setting for travelling salesman problems

Authors: Xumei Zhang, Hanguang Qiu

Addresses: College of Economics and Business Administration, Chongqing University, Chongqing, China. ' College of Economics and Business Administration, Chongqing University, Chongqing, China

Abstract: The particle swarm optimisation (PSO) does well in the continuous optimisation problems. To solve travelling salesman problem (TSP) with the PSO, priority coding method is presented to code the solution of the TSP. Then a method based on dynamic setting of velocity range is proposed for the PSO to remove the side effect which results from inconsistency of the search space and the solution space under the priority coding method. The experiment shows: the descending velocity range could achieve this goal and the descending rate of velocity range should match up with that of the priority range in position vector. In addition, a new approach based on cluster analysis on the swarm with the k-centres method is proposed for preventing the PSO from local optimum during solving the TSP. Through this mechanism, the diversity of the swarm could be reserved as the computation goes on, which could improve the performance of the PSO.

Keywords: travelling salesman problem; TSP; particle swarm optimisation; hybrid PSO; cluster analysis; k-centres method; velocity range; bio-inspired computation.

DOI: 10.1504/IJBIC.2010.030042

International Journal of Bio-Inspired Computation, 2010 Vol.2 No.1, pp.34 - 41

Published online: 03 Dec 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article