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

doi:10.3778/j.issn.1002-8331.1712-0281

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

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

陈雷，张红梅，张向利

桂林电子科技大学广西高校云计算与复杂系统重点实验室，广西桂林 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

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

摘要/Abstract

摘要： 针对离散布谷鸟算法求解旅行商问题时邻域搜索效率低和易陷入局部最优解等问题，提出了一种自适应动态邻域布谷鸟混合算法（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

陈雷，张红梅，张向利. 自适应动态邻域布谷鸟混合算法求解TSP问题[J]. 计算机工程与应用, 2018, 54(23): 42-50.

CHEN Lei, ZHANG Hongmei, ZHANG Xiangli. Adaptive dynamic neighborhood hybrid cuckoo search algorithm for solving traveling salesman problems[J]. Computer Engineering and Applications, 2018, 54(23): 42-50.

[1]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[2]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[3]	陈瑶，陈思. 基于自适应多普勒及动态邻域的改进BA算法[J]. 计算机工程与应用, 2021, 57(22): 166-176.
[4]	陈展，公建宁，刘媛媛，徐京邦. 基于禁忌搜索的多AGV系统路径优化算法[J]. 计算机工程与应用, 2021, 57(10): 273-278.
[5]	宋钰，石立宝. 参数动态调整的自适应布谷鸟算法[J]. 计算机工程与应用, 2020, 56(23): 61-67.
[6]	罗函明，罗天洪，吴晓东，陈科百. 求解混合流水车间调度问题的离散布谷鸟算法[J]. 计算机工程与应用, 2020, 56(22): 264-271.
[7]	陈思远，林丕源，黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
[8]	马艳芳，应斌，康凯，栾新凤. 模糊需求下绿色同时取送货问题与算法研究[J]. 计算机工程与应用, 2020, 56(16): 248-257.
[9]	周克良，龚达欣，张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[10]	王晓华，聂腾腾. 改进的布谷鸟算法优化粒子滤波研究[J]. 计算机工程与应用, 2020, 56(12): 60-65.
[11]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[12]	胡士娟，鲁海燕，黄洋，许凯波. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
[13]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.
[14]	李娟，游晓明，刘升，陈佳. 自适应模糊蚁群系统[J]. 计算机工程与应用, 2019, 55(15): 75-81.
[15]	赵亚文，熊瑞平，乔治，梁齐齐，罗勇. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics