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

415第40 卷第6 期2023年6 月机真仿算文章编号：10 0 6-9348(2 0 2 3)0 6-0 415-0 6基于大规模邻域搜索的模拟退火算法求解TSP孙鉴，刘淞佐，武晓晓（北方民族大学计算机科学与工程学院，宁夏银川7 50 0 2 1）摘要：针对目前旅行商问题的求解精度较差、容易陷入局部最优和收敛效果慢等缺点，根据模拟退火算法和大邻域搜索算法的特点，提出了一种基于大规模邻域搜索的模拟退火算法解决旅行商问题（simulated annealing algorithmwith large neighbor-hood search,SALNS）。上述算法在模拟退火的基础上修改算法的温度变化函数，构造旅行商问题的解空间，采用大邻域搜索技术和2-OPT算子增强局部搜索能力可以很好的解决旅行商问题。选取若干TSPLIB数据集进行实验，对降温函数和运行时间进行试验，并与一些新型智能算法对比。仿真结果表明，所提方法收敛效果好和鲁棒性强能够有效求解旅行商问题关键词：模拟退火算法；大规模邻域算法；降温策略；旅行商问题中图分类号：TP301.6文献标识码：BSimulated Annealing Algorithm Based On LargeNeighborhood Search To Solve TSPSUN Jian,LIU Song-zuo,WU Xiao-xiao(College of Computer Science and Engineering,North Minzu University,Yinchuan Ningxia 750021,China)ABSTRACT:For the current traveling salesman problem,the solution accuracy is poor,it is easy to fall into the localoptimum and the convergence effect is slow.Based on the characteristics of the simulated annealing algorithm and thelarge 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.SeveralTSPLIB data sets are selected for experiments,the cooling function and running time are tested,and compared withsome new intelligent algorithms.The simulation results show that the method has good convergence effect and strongrobustness,which can effectively solve the traveling salesman problem.KEYWORDS:Simulated annealing algorithm;Large neighborhood search algorithm;Cooling strategy;Travelingsalesman problem1引言旅行商问题（Traveling Salesman Problem,TSP）是较早提出的组合优化问题，其目标是求得在给定城市坐标集合，每个城市遍历且仅遍历一遍构成的城市序列，该城市序列代表旅行商将随机选择一个城市作为起点，每个城市遍历一次，回到出发城市。旅行商问题的最优解是总路程最短的城基金项目：国家自然科学基金项目（6 2 0 6 2 0 0 2）；北方民族大学中央高校基本科研业务费专项资金（FWNX09）；北方民族大学校级一般项目（2 0 2 1XYZJK01）；宁夏自然科学基金项目（2 0 2 2 AAC03289）收稿日期：2 0 2 1-0 8-2 4修回日期：2 0 2 1-0 9-0 4市序列。在车辆路径规划2 、物流配送问题3 等领域有重要的现实意义。考虑到该问题在各个领域的应用价值，研究人员从计算机、数学、运筹学等多个学科交叉人手，集中研究解决旅行商问题。该问题的解决方法大致划分为精确算法和近似算法两大类。常用的精确算法主要有枚举法、动态规划法以及分支限界法。但是大量的实验证明，精确算法只适用于求解城市规模较小的旅行商问题，随着城市规模的增大，精确算法求解开销较大，短时间内难以求得可行解，在实际生活中应用价值不高4近似算法是在近乎合理的时间内找到问题的近似解，近似算法可以分为常规的启发式算法和元启发式算法两类。416常规的启发式算法根据问题的特点，按照规则经验、规则和知识设计而成，虽然算法设计简单，但是不具有迁移性5当问题结构发生变化，就需要设计新的模型求解。元启发式算法更具有通用性，也因其特点成为求解TSP问题的主要方法，包括人工蜂群算法6 （ABC）、粒子群算法7 （PSO）、模拟退火算法8,9（SA）。朱继生10 提出一种人工蜜蜂融合量子编码的方法，在算法运行过程中量子位代表城市的访问序列，同时利用量子影响最佳蜜蜂的方向移动，影响整个蜜蜂种群找到最优解。李文、伍铁斌等人11 分析了基本粒子群算法的优点和缺点，利用混沌运动的随机性，自适应调整惯性权重，平衡了粒子群算法的局部搜索能力和全局搜索能力。本文利用模拟退火算法，修改降温函数结合大邻域搜索和2-opt算子，求解旅行商问题收敛速度快，寻优能力强。2基本知识2.1基本的模拟退火算法模拟退火算法受固体退火原理的启发，金属固体退温为加温、等温、冷却三个过程。在退火最初，固体的温度较高，内部分子没有稳定顺序，分子之间热运动较为剧烈，温度缓慢降低，分子逐渐有序稳定，这一过程称为退火；温度快速下降，能量无法降到最低，这一过程称为淬火。如图1是固体退火和淬火的过程示意图。金属（固体）加热高温状态缓慢退火火快速下降下降低温态均匀稳定状态非均匀亚稳定状态低温态图1物理退火和火过程图示退火的过程与组合优化的问题具有一定的相似性，故而将模拟退火算法应用到一系列组合优化问题中，如表1是组合优化问题和模拟退火算法的对应关系。表1过程对应关系表组合优化问题模拟退火物理过程解能量函数目标函数最低能量的状态设定初始温度加温过程基于Metropolis准则的搜索等温过程温度参数t的下降冷却过程模拟退火算法首先设定当前解为初始值，通过降温产生新解，通过比较新解和初始解的适应度函数，按照Metropolis准则12 对新解进行一定概率的接受，达到终止温度则停止选代。3解决旅行商问题的模拟退火算法3.1改进的模拟退火算法模拟退火算法的主要组成要素分别是状态产生函数、状态接受函数、降温函数、热平衡稳定准则、退火结束准则、初始温度的选取。本文针对旅行商问题的特性，对算法的降温函数进行改进，降温函数是控制温度下降的方式，温度的大小是算法的搜索能力的体现，当温度较高时，算法进行广域搜索；当温度较低时，算法进行局域搜索。温度下降较快导致算法从广域搜索直接进入局域搜索，这将使得当前状态的解无法得到验证，进而无法找到全局最优解。当温度下降过慢时，算法局域搜索能力较弱，将会漏掉很多可行解。常用的降温方式有以下两种：第一种：T=T*a,其中a是退火率,a的大小决定温度下降的速度，在算法迭代的过程中，都是按照线性递减的规律进行变化的。第二种T=T-T,A T 是每次温度下降的幅度,可以事先控制温度下降的总次数，之后依次递减。基于第一种温度的下降方式修改温度下降函数为如下形式TO=TO*(1)T=TO*(1+cos(t*pi/gaplter)(2)其中TO表示初始温度，T表示变化后的温度，为降温系数，t迭代次数，gapIter表示浮动的间隔数。3.2大规模邻域搜索模拟退火算法产生新解的步骤中引人大规模邻域搜索算法13（Large Neighborhood Search,LNS）。如图2 所示,初始解空间为3-5-1-8-7-2-6-4,首先对初始解空间进行破坏移除城市，移除的城市数是随机的，本文设置为1 N/3（N为城市总数）。在图2 中破坏选择移除的是城市1和城市6，把选中的城市从初始解空间中拿掉，剩下的按照初始解依次排序为破坏解空间：3-5-8-7-2-4。最后进行修复,对破坏解空间进行处理，例如图2 选择城市1重新插人破坏解空间初始解358 7264破坏35872466find best f(path)修复厂-1358724L最终解3一568724图2大规模邻域搜索算法的流程图417中,第一次插入后的结果为Sr,插入后的路径为1-3-5-8-7-2-4,计算Sr的适度值f(Sr)并且记录，因插人首尾效果相同，可以插人的位置为破坏解空间中的城市数量，分别计算插人不同位置的适度值，选择适度值效果最好的进行输出，之后把城市6 插人新的破坏解空间中，直到所有移除的城市修复完成得到最终解空间，算法伪代码如算法1所示。Algorithml:Large Neighborhood SearchInput:Original route Snow,destroy_numOutput:New optimal path sequence_repairsequence_random=random.permutation(Snow)Sequence_destroy sequence_random O:destroy_numsequence_remain+remove the Sequence_destroy in Snowremain_num len(Sd)for j in range(0,destroy_num):for i in range(0,remain_num+1):if i=1:sequence_remain_temp Sequence_destroyj+se-quence_remainelse:sequence_remain_one sequence_remain 0:i-1sequence_remain_two sequence_remain i-1:sequence_remain_temp sequence_remain_one+sequence_destroyj +sequence_remain_twolen_remain=fitness(sequence_remain_temp)ifi=1:len_remain_best len_remainSbest sequence_remain_tempelse:if len_remain len_remain_best:len_remain_best len_remainSbest sequence_remain_tempremain_num+=1sequence_remain sequence_remain_temp3.3局部搜索算子2-opt2-opt是一种随机性算法，基本思想就是随机选择两个元素进行优化，在求解TSP问题中得到了广泛的应用。如图3所示,路径为Ci,C2，,Cn,其中d(C,C)表示城市C和城市C,之间的距离，图3为2-opt思想实例。如果条件d(C,C,)+d(Ci+1,Cj+1)2:New_route2opt(Current_route,i,j)New_distancefitness(New_route)if New_distance Best_distance:Current_routeNew_routeBest_distanceNew_distanceReturn Current_route3.4交换和插入本文使用交换和插入两种操作来增加邻域结构，作用是防止进入局部最优，并且轮盘赌算法的方式来选择使用交换，插人和LNS。交换和插入概率设置高可以减少时间复杂度和提高局部搜索能力，交换和插人两种操作介绍如下：例如当前城市路径为：13-462-78-51)交换操作随机选择两个城市进行交换修改路径，如果选择的城市是3和7,那么变换后的城市序列为：17 46 2 3852)插人操作随机选取两个城市，选中进行插人操作的为i=3和j=7,进行判断如果ij（1:i-1i+1:j i j+l:e n d ）,否则（1:j-1ij+1:ii+l：e n d ），插人操作后的序列为：1-4-62-73853.5算法流程综上所述，本文算法步骤如下：1)初始化迭代次数，交换概率P,初始化温度等参数；2)贪婪策略初始化；3)计算适应度值，记录最优路径Pe和最优距离Lbes；4)对当前路径根据轮盘赌策略以一定的概率选择执行交换，插人和LNS操作产生新的路径Pnew；5）比较两次路径的适应度值之差f（Pn e w）302010102030405060 xlabel图7Eil51最优路径图Total Distance=61107006005004003002001000100200300400500600700 xlabel图8Ch130最优路径图Total Distance=293682000175015001250100075050025005001000150020002500300035004000 xlabel图9KroA200最优路径图TotalDistance=3896350300250200150200300400500600 xlabel图10Tsp225最优路径图420上接第343页）5总结本文针对旅行商问题的特性，在模拟退火算法的基础上，修改降温函数，降温函数是控制温度下降的方式，温度的大小关乎算法的搜索能力，改进后的降温函数可以很好的跳出局部最优解。同时采用在产生新解的过程中采用随机选择产生方式，使用交换和插人来增加邻域结构，作用是防止进人局部最优，并且轮盘赌算法的方式来选择使用交换，插人和LNS，之后通过2-opt优化解空间。通过实验仿真证明，SALNS修改的降温函数效果得到了很大的提高，求解质量相较于三种经典的启发式算法较好，同时和当前较新改进的算法比较，收敛速度快，求解质量高。参考文献：1 A G M Zaman,Sajib Hasan,Mohammad Samawat Ulah.Evaluationof TSP for Emergency Routing J.International Journal of Infor-mation Technology and Computer Science(IJITCS),2021,13(1).2Nogareda AnaMaria,Del Ser Javier,Osaba Eneko,Camacho David.On the design of hybrid bio-inspired meta-heuristics for com-plex multiattribute vehicle routing problems J.Expert Systems,2020,37(6).3Novellani,Stefano.Models and algorithms for the optimization ofreal-world routing and logistics problems J.A Quarterly Journalof Operations Research,2016,14(3):1-2.4熊文瑞，陶继平.自适应对抗学习求解旅行商问题J/OL.计算机工程与应用，2 0 2 1-0 8-12：1-7.5蔡永乐.求解有色旅行商问题的自然启发式算法研究D.武汉大学，2 0 17.6Kiran Mustafa Servet.A binary artificial bee colony algorithm andits performance assessment J.Expert Systems With Applications,2021,175.9吉敬华，孙玉坤，朱纪洪，等.模块化永磁电机的设计分析与实验J.电工技术学报，2 0 10,2 5(2)：2 2-2 9.10张炳义，贾宇琪，陈其雨，等。模块组合式交流电机定子分块规则与不等跨距绕组研究J.电工电能新技术，2 0 15，34(5):24-29.11 Q Chen,G Liu,W Zhao,et al.Design and comparison of two fault-tolerant interior-permanent-magnet motorsJ.IEEE Transac-tions on Industrial Electronics,2014,61(12):6615-6623.12许小伟，肖祎然，严运兵，等.车用永磁同步电机匝间短路故障瞬态特性分析J.计算机仿真,2 0 2 0,37（12)：111-116.13 Y Qi,E Bostanci,V Gurusamy,et al.A comprehensive analysis ofshort-circuit current behavior in PMSM interturn short-circuitfaultsJ.IEEE Transactions on Power Electronics,2018,33(12):10784-10793.7Miao Yu.A solution of TSP based on the ant colony algorithm im-proved by particle swarm optimization J.Discrete&ContinuousDynamical Systems-S,2018,12:8袁汪凰，游晓明，刘升，朱艳.求解TSP问题的自适应模拟退火蚁群算法J.计算机应用与软件，2 0 18,35（2）：2 6 1-2 6 6.9林之博，刘媛华.一种分片混沌贪婪振荡退火TSP优化算法J/0L.计算机应用研究,2 0 2 1-0 8-0 4:1-7.10 朱继生，混合人工蜂群算法求解旅行商问题D.广西大学,2 0 2 0.11李文，伍铁斌，赵全友，李玲香.改进的混沌粒子群算法在TSP中的应用J.计算机应用研究,2 0 15,32（7）：2 0 6 5-2 0 6 7.12 宋悦阳.基于改进遗传模拟退火优化BP算法的接地故障选线方法D.广西大学，2 0 2 0.13南丽君，陈彦如，张宗成.改进的自适应大规模邻域搜索算法求解动态需求的混合车辆路径问题J/OL.计算机应用研究,2 0 2 1-0 8-0 6:1-10.14王纪程，陈祖斌，江海宇，吕昊.基于极快速模拟退火与网格逐次剖分的微地震定位算法J.科学技术与工程，2 0 17，17(33):248-252.15汪冲，李俊，李波，张粤.改进的蚁群与粒子群混合算法求解旅行商问题J.计算机仿真，2 0 16,33（11）：2 7 4-2 7 9.16王震,刘瑞敏，朱阳光，王枭.一种求解TSP问题的改进遗传算法J.电子测量技术，2 0 19,42（2 3）：91-96.作者简介孙鉴（198 2-），男（汉族），山东烟台人，讲师，硕士研究生导师，主要研究领域为大数据存储与管理。刘淞佐（1994-），男（回族），黑龙江省双鸭山人，硕士研究生，主要研究领域为大数据分析与知识工程。武晓晓（1996-），女（汉族），山西省汾阳人，硕士研究生，主要研究领域为闪存索引。14P Arumugam,T Hamiti,C Gerada.Modeling of different windingconfigurations for fault-tolerant permanent magnet machines to re-strain interturn short-circuit current J.IEEE Transactions onEnergy Conversion,2012,27(2):351-361.15戴文进，张景明.电机设计M.北京：清华大学出版社，2 0 10.作者简介刘旭（198 4-），男（汉族），山西省运城市人，教授，博士研究生导师，主要研究领域为新型永磁电机及其控制、电机驱动及集成技术。张引引（1995-），女（汉族），安徽省亳州市人，硕士研究生，主要研究领域为新型永磁电机设计。