一种混合局部搜索算法的嵌套分区算法

宗德才1,王康康2摘要:提出了一种混合多种局部搜索算法的嵌套分区算法用于求解中小规模旅行商问题。该算法使用加权抽样法产生初始最可能域,用带约束的3-opt局部搜索算法搜索每个子域的最优解,然后对Lin-Kernighan算法进行了改进,并且用改进的Lin-Kernighan算法搜索每个裙域的最优解,最后通过实验分析法确定了子域和裙域最优的抽样个数及初始最可能域的长度。对TSPLIB中15个问题实例的仿真结果表明,所提出的混合局部搜索算法的改进嵌套分区算法在求解旅行商问题时可以获得高质量的解。关键词:嵌套分区算法;局部搜索算法;Lin-Kernighan算法;带约束的3-opt算法;旅行商问题:TP301.6文献标志码:A:1001-3695(2015)03-0752-07doi:10.3969/j.issn.1001-3695.2015.03.026CombinednestedpartitionsmethodbasedonlocalsearchalgorithmZONGDe-cai1,WANGKang-kang2(1.CollegeofComputerScience&Engineering,ChangshuInstituteofTechnology,Changshu激angsu215500,China;2.SchoolofAbstract:Thispaperputforwardanimprovednestedpartitionsmethodusingmultiplelocalsearchalgorithmstosolvethesmallandmediumscaletravelingsalesmanproblem.Thealgorithmadoptedweightedsamplingmethodtogeneratetheinitialmostpromisingregionandusedtherestricted3-optlocalsearchalgorithmtosearchtheoptimalsolutionofeachsubregion.ThenthisalgorithmusedanimprovedLin-Kernighanalgorithmtosearchtheoptimalsolutionofeachsurroundingregion.Final-ly,itanalyzedanddeterminedtheoptimalsamplingnumberofeachsubregionandeachsurroundingregionandtheoptimallengthoftheinitialmostpromisingregionthroughexperiments.Thesimulationresultsforthe15problemsinTSPLIBshowthattheproposedimprovednestedpartitionsmethodusingmultiplelocalsearchalgorithmscanfindsolutionsofhighqualitywhenappliedtothetravelingsalesmanproblem.题规模的扩大,将产生组合爆炸;b)随机优化算法或局部搜索算法,能够在多项式时间内求得问题的近似解。近年来,为解决TSP出现了许多随机优化算法或局部搜索算法,比较著名的有遗传算法、粒子群算法、模拟退火算法禁忌搜索算法、2-opt算法、3-opt算法、Lin-Kernighan(LK)算法等。这些算法能够在较短时间内获得近似解。嵌套分区算法(nestedpartitionsmethod,NPM)[2]是由Shi等人提出的一种能够高效求解大规模问题的优化方法,该算法提供了一个框架,能够将全局搜索与局部搜索相融合,具有易实现、并行性、全局性等优点。文献[3]将嵌套分区算法应用于银行分支机构选址问题,文献[4]将嵌套分区算法应用于大规模车间作业调度问题,文献[5]将嵌套分区算法应用于产品装配子序列合并问题,都取得了较好的效果。目前国内对于嵌套分区算法的研究还比较少。文献[6]将嵌套分区算法应用于求解旅行商问题,通过在抽样算子中引入2-opt局部搜索算法,对抽样得到的初始回路进行2-opt优化,能够显著提高解的质量和算法的收敛速度,但是能够搜索到最优解的概率不高,而且文献[6]中没有列出对具体的TSP实例的仿真结果。文献[7]将嵌套分区0引言旅行商问题(TSP)是一个典型的NP难的组合优化问题。该问题可描述为[1]:给定n个城市和两两城市之间的距离,要求确定一条经过各城市当且仅当一次的最短巡回路径。假设有n个城市,用1~n对城市进行编号,1表示城市1、2表示城市2,…,n表示城市n。Θ是所有1,2,…,n排列的集合,di,j是城市i到城市j的距离,s=(a1,a2,…,an)是1,2,…,n的一个排列,(a1,a2,…,an)表示访问的第一个城市是城市a1,第二个城市是城市a2,…,访问的最后一个城市是an,最后再回到第一个城市a1的一条回路。当di,j=dj,i时,称为对称min(ds∈Θ+d+…+d)(1)a1a2a2a3ana1求解TSP的算法有两类:a)精确算法,能够求出TSP的精确解,但是计算时间是问题规模(城市个数)的指数级,随着问收稿日期:2014-01-21;修回日期:基金项目:江苏省高校自然科学基础研究项目(13KJB110006);常熟理工学院青年教师2014-03-26基金资助项目(CST-201209)作者简介...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供参考,付费前请自行鉴别。
3、如文档内容存在侵犯商业秘密、侵犯著作权等,请点击“举报”。

常见问题具体如下:

1、问:已经付过费的文档可以多次下载吗?

      答:可以。登陆您已经付过费的账号,付过费的文档可以免费进行多次下载。

2、问:已经付过费的文档不知下载到什么地方去了?

     答:电脑端-浏览器下载列表里可以找到;手机端-文件管理或下载里可以找到。

            如以上两种方式都没有找到,请提供您的交易单号或截图及接收文档的邮箱等有效信息,发送到客服邮箱,客服经核实后,会将您已经付过费的文档即时发到您邮箱。

注:微信交易号是以“420000”开头的28位数字;

       支付宝交易号是以“2024XXXX”交易日期开头的28位数字。

客服邮箱:

biganzikefu@outlook.com

所有的文档都被视为“模板”,用于写作参考,下载前须认真查看,确认无误后再购买;

文档大部份都是可以预览的,笔杆子文库无法对文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;

文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为依据;

如果您还有什么不清楚的或需要我们协助,可以联系客服邮箱:

biganzikefu@outlook.com

常见问题具体如下:

1、问:已经付过费的文档可以多次下载吗?

      答:可以。登陆您已经付过费的账号,付过费的文档可以免费进行多次下载。

2、问:已经付过费的文档不知下载到什么地方去了?

     答:电脑端-浏览器下载列表里可以找到;手机端-文件管理或下载里可以找到。

            如以上两种方式都没有找到,请提供您的交易单号或截图及接收文档的邮箱等有效信息,发送到客服邮箱,客服经核实后,会将您已经付过费的文档即时发到您邮箱。

注:微信交易号是以“420000”开头的28位数字;

       支付宝交易号是以“2024XXXX”交易日期开头的28位数字。

文秘专家
机构认证
内容提供者

1

确认删除?