A Discrete Particle Swarm Optimization Algorithm for Solving TSP under Dynamic Topology
A Discrete Particle Swarm Optimization Algorithm for Solving TSP under Dynamic Topology
复制标题
DOI：
10.1109/cis-ram47153.2019.9095780
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Shuo Wang;Jiandong Zhang;Zhen Zhang;Xiao Yu
中科院分区：
文献类型：
--
作者：
Shuo Wang;Jiandong Zhang;Zhen Zhang;Xiao Yu
研究了旅行商问题（TSP）的求解问题，建立了动态拓扑下求解该问题的离散粒子群优化算法（DPSO）模型。针对TSP问题解的离散性和有序性，设计了一种新的编码方法，包括城市间的时间序列连接，建立了粒子与实际问题的映射关系。针对算法的早熟收敛问题，设计了一种基于粒子质量聚类的动态拓扑策略来调整粒子的飞行空间。通过引入梯度学习系数，提高了算法的收敛速度和获得最优解的概率。仿真结果表明，该算法模型可以应用于离散空间TSP问题的优化。
This paper studied the solution of the traveling salesman problem (TSP), a discrete particle swarm optimization algorithm (DPSO) model for solving this problem under dynamic topology was established. As to the discreteness and order of the TSP solution, a new coding method was designed, which included the time series connection between cities, the mapping relationship between particles and actual problems was established. And aiming at the premature convergence of the algorithm, a dynamic topology strategy based on particle mass clustering was designed to adjust the flight space of the particles. By introducing the gradient learning coefficient, the convergence speed of the algorithm and the probability of obtaining the optimal solution were improved. The simulation results showed that the proposed algorithm model can be applied to the optimization of TSP in discrete space.