A novel discrete particle swarm optimization to solve traveling salesman problem

Particle swarm optimization (PSO), which simulates the unpredictable flight of a bird flock, is one of the intelligent computation algorithms. PSO is well-known to solve the continuous problems, yet by proper modification, it can also be applied to discrete problems, such as the classical test model: traveling salesman problem (TSP). In this paper, a novel discrete PSO call C3DPSO for TSP, with modified update formulas and a new parameter c₃ (called mutation factor, to help to keep the balance between exploitation and exploration), is proposed. In the new algorithm, the particle is not a permutation of numbers but a set of edges, which is different from most other algorithms for TSP. However, it still keeps the most important characteristics of PSO that the whole swarm is guided by pbest and gbest. According to some benchmarks in TSP lib, it is proved that the proposed PSO works well even with 200 cities.