Improved discrete particle swarm optimization based on edge coding and multilevel reduction strategy for larger scale TSP

In order to improve particle swarm optimization (PSO) to solve complex and large scale discrete optimization problems, the paper introduces an improved discrete particle swarm optimization (IDPSO) based on edge coding and multilevel reduction strategy. First, redefine the velocity and position of the particle based on edge-coding, and adopted converted insertion of the edge to update the information of the particle. Next, introduce multilevel reduction strategy to improve the global convergence ability of the algorithm. The improved algorithm is applied to solve representative cases of traveling salesman problem (TSP), The results show that the improved DPSO is efficient and valid on the complex TSP, and the multilevel reduction strategy can contribute to develop the ability of PSO when facing up to the complex and large scale problems greatly.

I. Introduction

Traveling Salesman Problem (TSP) is a typical NP-hard combinatorial optimization problem[1]. which can be simply stated as follows: given a collection of cities, find the shortest tour which visits all of them and returns to the starting point. Typically the cities are given coordinates in the 2D plane and then the tour length is measured by the sum of Euclidean distances between each pair on the tour. For such discrete prblems, there are two baffles generally hard to overcome: one is that the problem is hard to be solved in multinomial time, the other is that the run time for solving such kind of problems will increase exponentially with the scale increasing. As far as the large scale TSP is concerned, only the acceptable solution can be got in multinomial time generally. Resently, Many heuristic and intelligent algorithms, including LKM[2], Simulated Annealing(SA), Genetic Algorithm(GA)[3], Ant Colony Algorithm (ACA)[4], etc., have been used to solve the NP-hard problem, and obtain great achievements.