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

Discrete Particle Swarm Optimization Algorithm for TSP

作　　者：邓伟林[1] 胡桂武[2] 

机构地区：[1]广东轻工职业技术学院计算机系,广东广州510300 [2]广东商学院数学与计算科学系,广东广州510320

出　　处：《计算机与现代化》2012年第3期1-4,共4页Computer and Modernization

基　　金：广东省自然科学基金资助项目(06301003);广东轻工职业技术学院科研启动基金资助项目(KY200817)

摘　　要：针对旅行商问题提出一种离散粒子群算法。算法重新定义了速度及其与粒子位置的相关算子,设计了"距离排序矩阵"(保存距离城市由近到远的其他城市的矩阵),并根据它生成可动态变化的优秀基因库来指导粒子高效地进行全局搜索。本文用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.

关 键 词：群体智能算法 离散粒子群算法 优化算法 旅行商问题 进化计算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]