计算机应用 ›› 2017, Vol. 37 ›› Issue (3): 750-754.DOI: 10.11772/j.issn.1001-9081.2017.03.750

• 先进计算 • 上一篇    下一篇

求解TSP的自适应优秀系数粒子群优化算法

程毕芸, 鲁海燕, 黄洋, 许凯波   

  1. 江南大学 理学院, 江苏 无锡 214122
  • 收稿日期:2016-07-19 修回日期:2016-10-15 出版日期:2017-03-10 发布日期:2017-03-22
  • 通讯作者: 鲁海燕
  • 作者简介:程毕芸(1992-),女,安徽马鞍山人,硕士研究生,CCF会员,主要研究方向:最优化与控制;鲁海燕(1970-),女,山东淄博人,副教授,博士,主要研究方向:组合最优化、智能算法;黄洋(1991-),男,河南信阳人,硕士研究生,CCF会员,主要研究方向:最优化与控制;许凯波(1992-),男,山西阳城人,硕士研究生,CCF会员,主要研究方向:最优化与控制。
  • 基金资助:
    国家自然科学基金资助项目(11371174);中央高校基本科研业务费专项资金资助项目(1142050205135260,JUSRP51317B)。

Particle swarm optimization algorithm based on self-adaptive excellence coefficients for solving traveling salesman problem

CHENG Biyun, LU Haiyan, HUANG Yang, XU Kaibo   

  1. School of Science, Jiangnan University, Wuxi Jiangnan 214122, China
  • Received:2016-07-19 Revised:2016-10-15 Online:2017-03-10 Published:2017-03-22
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (11371174), the Fundamental Research Funds for the Central Universities (1142050205135260, JUSRP51317B).

摘要: 针对基本离散粒子群优化(PSO)算法求解旅行售货商问题(TSP)时容易陷入局部最优解和早熟收敛的问题,提出了一种基于自适应优秀系数的粒子群(SECPSO)算法。为了提高算法的全局搜索能力,在已有工作的基础上,进一步利用启发式信息对静态的路径优秀系数进行修改,使之可根据解的搜索过程进行自适应动态调整;另外,为了进一步提高解的精确性和算法的收敛速度,添加了3-opt搜索机制,提高算法的局部搜索能力。利用Matlab进行了实验仿真,用国际通用的TSP数据库(TSPLIB)中的若干经典实例对算法性能进行了测试。实验结果表明,与其他几种算法相比,SECPSO算法在全局寻优能力和更快的收敛速度方面表现更优,是求解TSP问题的一种有潜力的智能算法。

关键词: 自适应优秀系数, 3-opt, 粒子群优化算法, 旅行售货商问题

Abstract: To solve the problem that basic discrete Particle Swarm Optimization (PSO) algorithm often leads the computation process into local optimum and premature convergence when applied to Traveling Salesman Problem (TSP), a PSO based on Self-adaptive Excellence Coefficients (SECPSO) algorithm was proposed. To improve the global search ability, heuristic information was further utilized to modify the static excellence coefficients of paths based on previous work, so that these coefficients could be adjusted adaptively and dynamically according to the process of searching for the solutions. Furthermore, a 3-opt search mechanism was added to improve the accuracy of the solution and the convergence rate of the algorithm. Through simulation experiments with Matlab, the performance of the proposed algorithm was evaluated using several classical examples in the international general TSP database (TSPLIB). The experimental results indicate that the proposed SECPSO algorithm performs better in terms of global search ability and convergence rate compared with several other algorithms, and thus is a potential intelligent algorithm for solving TSP.

Key words: self-adaptive excellence coefficients, 3-opt, Particle Swarm Optimization (PSO) algorithm, Traveling Salesman Problem (TSP)

中图分类号: