基于大规模邻域搜索的模拟退火算法求解TSP.pdf
《基于大规模邻域搜索的模拟退火算法求解TSP.pdf》由会员分享,可在线阅读,更多相关《基于大规模邻域搜索的模拟退火算法求解TSP.pdf(6页珍藏版)》请在咨信网上搜索。
1、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、度变化函数,构造旅行商问题的解空间,采用大邻域搜索技术和2-OPT算子增强局部搜索能力可以很好的解决旅行商问题。选取若干TSPLIB数据集进行实验,对降温函数和运行时间进行试验,并与一些新型智能算法对比。仿真结果表明,所提方法收敛效果好和鲁棒性强能够有效求解旅行商问题关键词:模拟退火算法;大规模邻域算法;降温策略;旅行商问题中图分类号:TP301.6文献标识码:BSimulated Annealing Algorithm Based On LargeNeighborhood Search To Solve TSPSUN Jian,LIU Song-zuo,WU Xiao-xiao(Colleg
3、e 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 annea
4、ling 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 sales
5、man 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 ne
6、w 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引言旅行商
7、问题(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
8、市序列。在车辆路径规划2 、物流配送问题3 等领域有重要的现实意义。考虑到该问题在各个领域的应用价值,研究人员从计算机、数学、运筹学等多个学科交叉人手,集中研究解决旅行商问题。该问题的解决方法大致划分为精确算法和近似算法两大类。常用的精确算法主要有枚举法、动态规划法以及分支限界法。但是大量的实验证明,精确算法只适用于求解城市规模较小的旅行商问题,随着城市规模的增大,精确算法求解开销较大,短时间内难以求得可行解,在实际生活中应用价值不高4近似算法是在近乎合理的时间内找到问题的近似解,近似算法可以分为常规的启发式算法和元启发式算法两类。416常规的启发式算法根据问题的特点,按照规则经验、规则和知识
9、设计而成,虽然算法设计简单,但是不具有迁移性5当问题结构发生变化,就需要设计新的模型求解。元启发式算法更具有通用性,也因其特点成为求解TSP问题的主要方法,包括人工蜂群算法6 (ABC)、粒子群算法7 (PSO)、模拟退火算法8,9(SA)。朱继生10 提出一种人工蜜蜂融合量子编码的方法,在算法运行过程中量子位代表城市的访问序列,同时利用量子影响最佳蜜蜂的方向移动,影响整个蜜蜂种群找到最优解。李文、伍铁斌等人11 分析了基本粒子群算法的优点和缺点,利用混沌运动的随机性,自适应调整惯性权重,平衡了粒子群算法的局部搜索能力和全局搜索能力。本文利用模拟退火算法,修改降温函数结合大邻域搜索和2-opt
10、算子,求解旅行商问题收敛速度快,寻优能力强。2基本知识2.1基本的模拟退火算法模拟退火算法受固体退火原理的启发,金属固体退温为加温、等温、冷却三个过程。在退火最初,固体的温度较高,内部分子没有稳定顺序,分子之间热运动较为剧烈,温度缓慢降低,分子逐渐有序稳定,这一过程称为退火;温度快速下降,能量无法降到最低,这一过程称为淬火。如图1是固体退火和淬火的过程示意图。金属(固体)加热高温状态缓慢退火火快速下降下降低温态均匀稳定状态非均匀亚稳定状态低温态图1物理退火和火过程图示退火的过程与组合优化的问题具有一定的相似性,故而将模拟退火算法应用到一系列组合优化问题中,如表1是组合优化问题和模拟退火算法的对
11、应关系。表1过程对应关系表组合优化问题模拟退火物理过程解能量函数目标函数最低能量的状态设定初始温度加温过程基于Metropolis准则的搜索等温过程温度参数t的下降冷却过程模拟退火算法首先设定当前解为初始值,通过降温产生新解,通过比较新解和初始解的适应度函数,按照Metropolis准则12 对新解进行一定概率的接受,达到终止温度则停止选代。3解决旅行商问题的模拟退火算法3.1改进的模拟退火算法模拟退火算法的主要组成要素分别是状态产生函数、状态接受函数、降温函数、热平衡稳定准则、退火结束准则、初始温度的选取。本文针对旅行商问题的特性,对算法的降温函数进行改进,降温函数是控制温度下降的方式,温度
12、的大小是算法的搜索能力的体现,当温度较高时,算法进行广域搜索;当温度较低时,算法进行局域搜索。温度下降较快导致算法从广域搜索直接进入局域搜索,这将使得当前状态的解无法得到验证,进而无法找到全局最优解。当温度下降过慢时,算法局域搜索能力较弱,将会漏掉很多可行解。常用的降温方式有以下两种:第一种:T=T*a,其中a是退火率,a的大小决定温度下降的速度,在算法迭代的过程中,都是按照线性递减的规律进行变化的。第二种T=T-T,A T 是每次温度下降的幅度,可以事先控制温度下降的总次数,之后依次递减。基于第一种温度的下降方式修改温度下降函数为如下形式TO=TO*(1)T=TO*(1+cos(t*pi/g
13、aplter)(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
14、重新插人破坏解空间初始解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:Origi
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 大规模 邻域 搜索 模拟 退火 算法 求解 TSP
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。