计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (23): 42-50.DOI: 10.3778/j.issn.1002-8331.1712-0281

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

自适应动态邻域布谷鸟混合算法求解TSP问题

陈  雷,张红梅,张向利   

  1. 桂林电子科技大学 广西高校云计算与复杂系统重点实验室,广西 桂林 541004
  • 出版日期:2018-12-01 发布日期:2018-11-30

Adaptive dynamic neighborhood hybrid cuckoo search algorithm for solving traveling salesman problems

CHEN Lei, ZHANG Hongmei, ZHANG Xiangli   

  1. Guangxi Colleges and Universities Key Laboratory of Cloud Computing and Complex Systems, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
  • Online:2018-12-01 Published:2018-11-30

摘要: 针对离散布谷鸟算法求解旅行商问题时邻域搜索效率低和易陷入局部最优解等问题,提出了一种自适应动态邻域布谷鸟混合算法(Adaptive Dynamic Neighborhood Hybrid Cuckoo Search algorithm,ADNHCS)。为了提升邻域搜索效率,设计了一种圆限定突变的动态邻域结构来降低经典算法的随机性;此外,提出了可根据迭代过程进行自适应参数调整的策略,并结合禁忌搜索算法来提升全局寻优的能力。使用MATLAB和标准TSPLIB数据库中的若干经典算例对算法性能进行了实验仿真,结果表明与其他基于布谷鸟算法、经典和新型群智能优化算法相比,ADNHCS算法在全局寻优能力以及稳定性方面表现更优。

关键词: 布谷鸟算法, 旅行商问题, 禁忌搜索算法, 动态邻域

Abstract: In view of the deficiencies of discrete cuckoo search algorithm for solving Traveling Salesman Problem(TSP) like easy to fall into the local optimal solution and low efficiency of local search. An adaptive dynamic neighborhood hybrid cuckoo search algorithm is proposed. To improve the local search efficiency, a circle-restricted dynamic neighborhood structure is designed to reduce the randomness. In addition, the strategy of adaptive parameter adjustment based on the iterative process is proposed, and the tabu search algorithm is used to improve the ability of searching global optimum solution. Finally, using MATLAB and some instances in TSPLIB database to test the performance of the algorithm, the results show that compared with other cuckoo search algorithms, new intelligence algorithms and classical intelligent optimization algorithms, ADNHCS algorithm has better performance in global optimization and stability.

Key words: cuckoo search algorithm, traveling salesman problem, tabu search algorithm, dynamic neighborhood