基于改进禁忌搜索算法求解TSP问题  

Solving TSP problem based on improved tabu search algorithm

作　　者：冉令龙 李琳 郑学东 RAN Linglong;LI Lin;ZHENG Xuedong(College of Science,Shenyang Aerospace University,Shenyang 110136,China;College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学理学院,沈阳110136 [2]沈阳航空航天大学计算机学院,沈阳110136

出　　处：《沈阳航空航天大学学报》2023年第4期80-87,共8页Journal of Shenyang Aerospace University

基　　金：国家自然科学基金(项目编号:61972266,61403260);辽宁省自然科学基金(项目编号:2020-MS-233);辽宁省兴辽英才计划项目(项目编号:XLYC2002017)。

摘　　要：针对禁忌搜索算法(tabu search algorithm,TS)对初始解依赖性较强的问题,提出一种改进的禁忌搜索算法求解TSP问题。在分析TSP问题特点后,分别采用随机生成初始解算法、改良圈算法、CW节约算法和贪婪算法生成初始解并比较4种算法的计算效果,从中选出最优解作为TS算法的初始解。在禁忌搜索过程中比较Insert邻域、Swap邻域和2-opt邻域的改进效果,选择最优的邻域变换模式得到改进解。在仿真实验中,设置合适的参数,通过与相关文献实验结果的对比,验证了该算法的有效性。For the problem that tabu search algorithm(TS)has strong dependence on the initial solution,an improved tabu search algorithm(TS algorithm)was proposed to solve traveling sales-man problem(TSP).The initial solution was generated by random generation algorithm,improved circle algorithm,CW saving algorithm and greedy algorithm,and the results of the four algorithms were compared.The optimal solution was selected as the initial solution of TS algorithm.During TS,the improvement effects of insert neighborhood,swap neighborhood and 2-opt neighborhood were compared,and the optimal neighborhood transformation mode was selected to get the improved solution.In the simulation experiment,appropriate parameters were set,and the effectiveness of the proposed algorithm was verified by comparing with the experimental results of relevant literatures.

关 键 词：TSP问题 禁忌搜索算法 贪婪算法 邻域变换 组合优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]