关键词: 离散粒子群优化算法, 旅行商问题, 优秀系数, 局部搜索, 混沌序列

Abstract: In view of the drawbacks of the standard Discrete Particle Swarm Optimization (DPSO) algorithm such as slow convergence speed and easily trapping into local optima, an Improved Local-search-based Chaotic Discrete Particle Swarm Optimization (ILCDPSO) algorithm based on excellence coefficient was proposed and then applied to Traveling Salesman Problem (TSP). In this algorithm, each edge was assigned an appropriate excellence coefficient based on the principle of roulette selection. This helped to improve the selection probability of short edge, thus improving the optimization ability and convergence speed of the algorithm. In order to further improve the accuracy of solution, a local search strategy was employed such that the exploration ability of the algorithm could be improved by adjusting the routes of cities in the given neighborhood for each city. Moreover, a chaotic sequence was integrated into the iteration formula to enhance the randomness and diversity of particles and hence increasing the global searching ability of the proposed algorithm. Finally the algorithm was evaluated by some typical instances in the internationally commonly used library of TSP (TSPLIB) and compared with Particle Swarm Optimization (PSO) algorithm, Improved Particle Swarm Optimization (IPSO) algorithm, and Chaotic Particle Swarm Optimization (CPSO) algorithm, etc. The experiment data show that, under the same experimental conditions, ILCDPSO can achieve optimal solutions with less average iterations than other algorithms and has the highest ratio of number for obtaining optimal solutions. The research results indicate that ILCDPSO algorithm performs better than other algorithms in terms of convergence speed, global optimization ability and stability, and it is a comparatively potential intelligent algorithm for solving TSP.

Key words: Discrete Particle Swarm Optimization (DPSO) algorithm, Traveling Salesman Problem (TSP), excellence coefficient, local search, chaotic sequence