《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (6): 1837-1843.DOI: 10.11772/j.issn.1001-9081.2021040567

• 人工智能 • 上一篇    

求解旅行商问题的人工协同搜索算法

徐小平1, 唐阳丽1(), 王峰2   

  1. 1.西安理工大学 理学院,西安 710054
    2.西安交通大学 数学与统计学院,西安 710049
  • 收稿日期:2021-04-14 修回日期:2021-06-28 接受日期:2021-07-02 发布日期:2022-06-22 出版日期:2022-06-10
  • 通讯作者: 唐阳丽
  • 作者简介:徐小平(1973—),男,陕西蓝田人,教授,博士,主要研究方向:智能算法
    王峰(1972—),女,河南兰考人,教授,博士,主要研究方向:智能算法。
  • 基金资助:
    国家自然科学基金资助项目(61773016);陕西省创新能力支撑计划项目(2020PT-023);陕西省自然科学基础研究计划项目(2018JQ1089)

Artificial cooperative search algorithm for solving traveling salesman problems

Xiaoping XU1, Yangli TANG1(), Feng WANG2   

  1. 1.Faculty of Science,Xi’an University of Technology,Xi’an Shaanxi 710054,China
    2.School of Mathematics and Statistics,Xi’an Jiaotong University,Xi’an Shaanxi 710049,China
  • Received:2021-04-14 Revised:2021-06-28 Accepted:2021-07-02 Online:2022-06-22 Published:2022-06-10
  • Contact: Yangli TANG
  • About author:XU Xiaoping, born in 1973, Ph. D., professor. His research interests include intelligent algorithm.
    WANG Feng, born in 1972, Ph. D., professor. Her research interests include intelligent algorithm.
  • Supported by:
    National Natural Science Foundation of China(61773016);Shaanxi Provincial Innovation Capability Support Program(2020PT-023);Shaanxi Natural Science Basic Research Program(2018JQ1089)

摘要:

针对传统人工协同搜索(ACS)算法求解精度不高、收敛速度慢等问题,提出一种基于Sigmoid函数的反向人工协同搜索(SQACS)算法求解旅行商问题(TSP)。首先,利用Sigmoid函数构造比例因子,增强算法的全局搜索能力;其次,在变异阶段,加入差分进化(DE)算法的DE/rand/1变异策略,对当前种群进行二次变异,提高算法的计算精度和种群的多样性;最后,在算法后期的开发阶段,引入拟反向学习策略,进一步提高解的质量。对TSP测试库TSPLIB中的4个实例进行仿真实验,结果显示,SQACS算法在最短路径与花费时间上均优于麻雀搜索算法(SSA)、DE、阿基米德算法(AOA)等7种对比算法,并且具有良好的鲁棒性;与其他求解TSP的改进算法综合对比,SQACS算法也显示了良好的性能。实验结果表明,SQACS算法在求解小规模TSP时是有效的。

关键词: 人工协同搜索算法, 旅行商问题, Sigmoid函数, 差分进化, 拟反向学习

Abstract:

Concerning low solution accuracy and slow convergence of traditional Artificial Cooperative Search (ACS) algorithm, a Quasi opposition Artificial Cooperative Search algorithm based on Sigmoid function (SQACS) algorithm was proposed to solve Traveling Salesman Problem (TSP). Firstly, the Sigmoid function was used to construct the scale factor to enhance the global search ability of the algorithm. Then, in the mutation stage, the mutation strategy DE/rand/1 of Differential Evolution (DE) algorithm was introduced into the current population for secondary mutation, thereby improving the calculation accuracy of the algorithm and the diversity of the population. Finally, in the later development stage, the quasi opposition learning strategy was introduced to further improve the quality of the solution. Four instances in TSP test library TSPLIB were used to perform simulation experiments, and the results show that SQACS algorithm is superior to seven comparison algorithms such as Sparrow Search Algorithm (SSA), DE and Archimedes Optimization Algorithm (AOA) in the shortest path and time consumption, and has good robustness; and compared with other improved algorithms for solving TSP comprehensively, SQACS algorithm also shows good performance. Experimental results prove that the SQACS algorithm is effective in solving small-scale TSPs.

Key words: Artificial Cooperative Search (ACS) algorithm, Traveling Salesman Problem (TSP), Sigmoid function, Differential Evolution (DE), quasi opposition learning

中图分类号: