Research And Application Of Particle Swarm Optimization On TSP

Particle Swarm Optimization (PSO) is a new kind of evolutionary computation base on colony intelligent algorithm, which was was originally introduced by Eberhart and Kennedy in 1995. PSO is simple in concept, few in parameters, and easy in implementation.PSO has proven to be a powerful global optimization method. It has been widely applied infunction optimization, neural network training, and fuzzy system control, etc. However, as PSO is a newly emerging optimization method, there are many research work should be substantiated. So it is very significant to seek more powerful improved algorithms based on PSO to solve concrete engineering problems.Traveling Salesman Problem (TSP) is one of the classic problem combinatorial optimization in graphic theory. TSP is a typical NP-hard problem, many practical problems can be transformed into TSP. This paper analyse discrete PSO and designs corresponding operations in it for resolving TSP.Firstly, the paper analyses the elements of PSO. Based on the analysis on characteristics of PSO, the algorithm is summarized. The experienced settings of parameters are also given. In the paper, the present productions of PSO are summarized and compared.Secondly, according to the investigation of PSO, the paper proposes two kinds of new Particle Swarm Optimization: A Quantum Particle Swarm Optimization for Solving Traveling Salesman Problem (TSP-QPSO) and A Particle Swarm Optimization for Solving TSP base on Local Search Optimization (LSPSO). The experiment results illustrate that the new PSO has higher performance than some traditional PSO.Finally, the new Particle Swarm Optimization is used to solve the TSP in glass-block cutting problem. After solving the layout problem of glass-block typesetting, the shortest cutting route should be found, and this is just a TSP. This paper introduces the design and implement of PSO to solve the TSP in glass-block cutting problem.