计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (10): 48-54.DOI: 10.3778/j.issn.1002-8331.1512-0115

• 理论与研发 • 上一篇    下一篇

求解TSP问题的自适应离散型布谷鸟算法

张子成,韩  伟   

  1. 南京财经大学 信息工程学院,南京 210046
  • 出版日期:2017-05-15 发布日期:2017-05-31

Adaptive discrete cuckoo algorithm for solving TSP problem

ZHANG Zicheng,  HAN Wei   

  1. College of Information & Engineering, Nanjing University of Finance and Economics, Nanjing 210046, China
  • Online:2017-05-15 Published:2017-05-31

摘要: 对于求解的TSP问题,提出了一种自适应离散型布谷鸟算法(Adaptive Discrete Cuckoo Search,ADCS)。在基于布谷鸟搜索算法(Cuckoo Search,CS)的搜索原理下构造TSP问题的路径求解策略。针对离散型算法整体调整容易破坏已形成的较优路径和随着算法迭代数目增加导致种群多样性下降这两个缺陷,设计了一种针对路径的自适应型局部调整算子和全局随机扰动策略,采用了简单的2-opt优化算子作为局部优化算子以加快算法的收敛速度。最后采用多组不同规模的标准TSPLIB数据与其他的优化算法进行对比实验,结果表明ADCS算法在求解精度和稳定性方面具有优势。

关键词: TSP问题, 布谷鸟搜索算法, 2-opt优化, 局部调整, 全局随机扰动

Abstract: For solving the TSP problem, this paper proposes an adaptive discrete cuckoo algorithm. Constructing path solution strategy of TSP problem based on the principle of cuckoo search algorithm. For the two defects of the discrete algorithm, one is overall adjustment can easily destroy the optimum path which is already formed, the other is the decline of diversity of population with the increase of the iteration number of the algorithm, this paper designs an adaptive partial adjustment operator and a global random perturbation strategy for path. In order to speed up the convergence rate of the algorithm, a simple 2-opt optimization operator is used as a local optimization operator. In the end, multiple sets of different sizes of standard TSPLIB data are compared with other optimization algorithms, the experimental result shows that the ADCS algorithm has advantages in solving precision and stability.

Key words: TSP problem, cuckoo search algorithm, 2-opt optimization, partial adjustment, global random disturbance