基于大规模邻域搜索的模拟退火算法求解TSP  

Simulated Annealing Algorithm Based On LargeNeighborhood Search To Solve TSP

作　　者：孙鉴 刘凇佐 武晓晓 SUN Jian;LIU Song-zuo;WU Xiao-xiao(College of Computer Science and Engineering,North Minzu University,Yinchuan Ningxia 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021

出　　处：《计算机仿真》2023年第6期415-420,共6页Computer Simulation

基　　金：国家自然科学基金项目(62062002);北方民族大学中央高校基本科研业务费专项资金(FWNX09);北方民族大学校级一般项目(2021XYZJK01);宁夏自然科学基金项目(2022AAC03289)。

摘　　要：针对目前旅行商问题的求解精度较差、容易陷入局部最优和收敛效果慢等缺点,根据模拟退火算法和大邻域搜索算法的特点,提出了一种基于大规模邻域搜索的模拟退火算法解决旅行商问题(simulated annealing algorithm with large neighborhood search, SALNS)。上述算法在模拟退火的基础上修改算法的温度变化函数,构造旅行商问题的解空间,采用大邻域搜索技术和2-OPT算子增强局部搜索能力可以很好的解决旅行商问题。选取若干TSPLIB数据集进行实验,对降温函数和运行时间进行试验,并与一些新型智能算法对比。仿真结果表明,所提方法收敛效果好和鲁棒性强能够有效求解旅行商问题。For the current traveling salesman problem,the solution accuracy is poor,it is easy to fall into the local optimum and the convergence effect is slow.Based on the characteristics of the simulated annealing algorithm and the large neighborhood search algorithm,this paper proposes a hybrid algorithm to solve the traveling salesman problem.The algorithm modifies the temperature change function of the algorithm on the basis of simulated annealing to con-struct the solution space of the traveling salesman problem,and uses the Large neighborhood search technology and 2-OPT operator to enhance the local search ability,which can solve the traveling salesman problem very well.Several TSPLIB data sets are selected for experiments,the cooling function and running time are tested,and compared with some new intelligent algorithms.The simulation results show that the method has good convergence effect and strong robustness,which can effectively solve the traveling salesman problem.

关 键 词：模拟退火算法 大规模邻域算法 降温策略 旅行商问题 

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