Particle Swarm Algorithm For Solving The Traveling Salesman Problem

Traveling salesman problem (TSP) is an old and typical NP-hard combinatorial optimization problem, its valid and effective solutions not only has important theoretical and academic values, but also has important guiding significance for many practical engineering applications. So TSP is a hot topic in optimization field. Particle swarm optimization (PSO) is a new method based on swarm intelligence, which are characterized mainly by simple model, convenient operation, self-organizing, self-adaptive, self-learning, etc. Particle swarm optimization has been proved to be an effective technique to solve large-scale complex problems. Therefore, it is also an efficient method to solve TSP. However, the existing PSO also suffers from some shortcomings, such as low efficiency, low accuracy, premature convergence, etc., especially for the large scale and complex discrete combinatorial optimization problems.The dissertation focuses on the model designing and performance improving of discrete particle swarm algorithm (DPSO) based on TSP, its main researches are listed as the following:1. Based on the optimization mechanisms of swarm intelligence, the dissertation makes an analysis of the primary design methods and the basic principles for discrete particle swarm optimization firstly. After that, the key techniques of DPSO also are analyzed in details, including the code methods for discrete optimization problems, the evolutionary operations in discrete solution space, etc., which provide a valid technical foundation for the following study.2. To improve the global convergence of DPSO, The dissertation develops an adaptive DPSO to solve TSP. Firstly, the improved DPSO adopts the integer code method and redesigns the particles'velocity, location, and their discrete evolution operations based on the PMX operator of genetic algorithm. Secondly, the improved DPSO introduces a local adjustment strategy for the parameters to avoid the local convergence of the swarm, which is controlled by the dynamic information of particles. The simulation results based on the typical TSP problems show that the proposed algorithm validly improves the global performance of PSO in discrete optimization problems.3. To develop the performance of DPSO for complex discrete optimization problems, the dissertation proposed another improved DPSO, which takes advantage of side-code technique and a multilevel reduction strategy. The improved DPSO redesigns the particles'velocity, location, and their discrete evolution operations based on the side-code technique. After that, a multilevel reduction strategy is introduced to improve the global convergence of the algorithm. Finally, the improved algorithm is applied to solve medium or large scale TSP problems, the simulation results show that the proposed algorithm is a valid technique for complex TSP problems.