一种求解旅行商问题的改进混合粒子群算法

An Improved Hybrid Particle Swarm Optimization Algorithm for Solving Traveling Salesman Problem

为了使粒子群算法(PSO)在求解旅行商问题(TSP)时能在收敛速度和求解精度两方面都得到提升,提出一种改进的混合粒子群算法(IHPSO)。在现有的混合粒子群算法的基础上,采用贪婪交叉算子来提高收敛速度,同时利用混沌运动的特性,在种群中引入一个独立的混沌粒子。该粒子并不是用来在解空间里寻找最优解,而是用于与其它粒子进行贪婪交叉,使其它粒子的搜寻范围得以扩大,从而提高求解精度。利用Matlab在TSPLIB中的数据集上进行实验,结果显示该算法在收敛速度和求解精度两方面均有明显提高。

In order to improve the convergence speed and accuracy of the particle swarm optimization(PSO)algorithm in solving the traveling salesman problem(TSP),an improved hybrid particle swarm optimization(IHPSO)algorithm is proposed. Based on existing hybrid particle swarm optimization algorithm,the greedy crossover operator is used to improve the convergence speed,and a chaotic particle is introduced into the population by using the characteristics of chaotic motion. Instead of searching for the optimal solution in the solution space,the chaotic particle is used to implement greedy cross with other particles,and then expand the search scope of other particles,so the method can be utilized to enhance the precision of the solution. By using MATLAB,the experiments are carried out on the data set in TSPLIB,and the experimental results show that the improved algorithm can improve both convergence speed and accuracy.