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

Abstract: An improved Particle Swarm Optimization (PSO) algorithm based on Hamming distance was proposed to solve the discrete problems. The basic idea and process of traditional PSO was retained, and a new speed representation based on Hamming distance was defined. Meanwhile, in order to make the algorithm be more efficient and avoid the iterative process falling into the local optimum, new operators named 2-opt and 3-opt were designed, and the random greedy rule was also used to improve the quality of the solution and speed up the convergence. At the later period of the algorithm, in order to increase the global search ability of the particles in the whole solution space, a part of particles was regenerated to re-explore the solution space. Finally, a number of TSP standard examples were used to verify the effectiveness of the proposed algorithm. The experimental results show that the proposed algorithm can find the historical optimal solution for small scale TSP; for large-scale TSP, for example, the city number is more than 100, satisfactory solutions can also be found, and the deviations between the known and the optimal solutions are small, usually within 5%.

Key words: Particle Swarm Optimization (PSO) algorithm, Hamming distance, random greedy rule, 2-opt operator, 3-opt operator, Traveling Salesman Problem (TSP)