关键词: 粒子群算法, 汉明距离, 随机贪婪规则, 2-opt算子, 3-opt算子, 旅行商问题

Abstract: In this paper, an improved particle swarm optimization algorithm based on Hamming distance is proposed to solve the discrete problem. The algorithm retains the basic idea and process of particle swarm optimization algorithm, and defines a new velocity representation for particle. At the same time, in order to make the algorithm more efficient and avoid the iterative process falling into the local optimum, the 2-opt and 3-opt operators are designed, and the random greedy rule is used to improve the quality of the solution. In order to increase the global search ability of the particles in the whole solution space, a part of particle re-generation is used to explore the solution space. In order to verify the effectiveness of the algorithm, this paper uses a number of TSP standard examples for testing. The results show that the algorithm can find the optimal solution for the small scale TSP problem. For large-scale TSP problem, we can find a satisfactory solution.

Key words: particle swarm optimization, Hamming distance, random greedy rule, 2-opt operator, 3-opt operator, traveling salesman problem