一种求旅行商问题的离散粒子群算法

Discrete Particle Swarm Optimization Algorithm for TSP

针对旅行商问题提出一种离散粒子群算法。算法重新定义了速度及其与粒子位置的相关算子,设计了"距离排序矩阵"(保存距离城市由近到远的其他城市的矩阵),并根据它生成可动态变化的优秀基因库来指导粒子高效地进行全局搜索。本文用TSPLIB中的部分案例进行实验,实验结果表明,该算法在求解旅行商问题上有很好的性能,并且具有很好的鲁棒性。

A discrete particle swarm optimization algorithm is proposed for solving traveling salesman problem （TSP）. It defines a newly velocity. It also defines some new operators between particle and velocity. A matrix, which keeps the sorted ascending ed- ges by distance for each city is created, and a variable size of gene pool is implemented to direct the particle to search around the space. In this paper, some eases from TSPLIB are tested; the experiments results show that the algorithm has good performance and good rudeness for solving TSP.