求解TSP问题的贪婪随机模拟退火算法

ID:40960994

大小:100.50 KB

页数:6页

时间:2019-08-12

求解TSP问题的贪婪随机模拟退火算法_第1页
求解TSP问题的贪婪随机模拟退火算法_第2页
求解TSP问题的贪婪随机模拟退火算法_第3页
求解TSP问题的贪婪随机模拟退火算法_第4页
求解TSP问题的贪婪随机模拟退火算法_第5页
资源描述:

《求解TSP问题的贪婪随机模拟退火算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、求解TSP问题的贪婪随机模拟退火算法钟一文,蔡荣英福建农林大学计算机与信息学院,福建福州,350002摘要:模拟退火算法是一种典型的智能优化算法,它的一个主要缺点是收敛速度慢。针对这一问题,提出了一种基于贪婪随机策略的求解旅行商问题的模拟退火算法,在从当前解的邻域中选择候选解时,根据问题领域的启发式信息,采用贪婪策略从邻域中生成一个候选解列表,再从候选解列表中随机选择一个候选解。仿真结果表明,贪婪随机模拟退火算法明显优于传统的模拟退火算法。关键词:模拟退火算法;贪婪随机;旅行商问题中图分类号:TP301文献标识码:A文章编号:AGreedyRan

2、domSimulatedAnnealingAlgorithmforTravelingSalesmanProblemZHONGYi-wen,CAIRong-yingCollegeofComputerandInformationScience,FujianAgricultureandForestryUniversity,Fuzhou350002,ChinaAbstract:SimulatedAnnealingalgorithmisatypicalintelligentoptimizationalgorithm.Oneofitsmainshortage

3、sisslowconvergencespeed.Inordertotacklethisshortage,agreedyrandomSimulatedAnnealingalgorithmforTravelingSalesmanProblemispresented.Inthepresentedalgorithm,basedonheuristicinformationderivedfromtheproblemathand,acandidatelistisselectedgreedilyfromtheneighborhoodofcurrentsoluti

4、on.Thencandidatesolutionisselectedrandomlyfromthecandidatelist.SimulatedresultsshowthattheproposedalgorithmcangetbetterresultthanclassicalSimulatedAnnealingalgorithm.Keywords:SimulatedAnnealingalgorithm;Greedyrandom;TravelingSalesmanProblem1引言模拟退火(SimulatedAnnealing,SA)算法是一种典

5、型的智能优化方法,SA算法的思想最早是由Metropolis等[1]提出的,SA算法依据Metropolis准则接受新解,因此,除接受优质解外,还在一定范围内接受劣质解,SA算法在开始时温度t值较大,可以接受较差的劣质解,随着t值的减小,只能接受较好的劣质解,最后在t值趋于零时,就不再接受任何劣质解了,这就使SA算法可以从局部最优的“陷阱”中跳出,从而有可能求得优化问题的全局最优解。SA算法同时还具有简单和通用的特点,因此SA算法在许多领域都得到了很好的应用,比如在VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。但是,尽管从理论

6、上证明了SA算法能收敛到全局最优解,在使用SA算法的过程中也发现,其收敛速度很慢,与此相反,启发式算法通常基于某种贪婪策略,有较快的收敛速度,但易于陷入局部最优解,那么,能否在SA算法中嵌入一定的贪婪策略,在保持其全局寻优的前提下,加快SA算法的收敛速度呢?基于这个思想,针对旅行商问题(TravelingSalesmanProblem,TSP),本文研究了在产生下一个解时,根据领域的启发式信息,采用贪婪策略从邻域中生成一个候选解列表,再从候选解列表中随机选择一个候选解,以平衡算法的随机性和贪婪性,提高获取优质解的概率,从而提高SA算法的总体性能,

7、仿真表明,这种策略能明显提高SA算法的性能。2求解TSP问题的模拟退火算法TSP问题是一个典型的NP-困难的组合优化问题。假设有一个推销员必须遍历N个城市,每个城市必须且只能访问一次,最后返回到出发城市,TSP问题就是要找到访问这些城市的顺序,使旅行线路的总长度最短。对一个包含N个城市的TSP问题,可以用一个N×N的二维数组d来存储城市间的距离,其中每个元素d[i][j]表示城市i和j之间的距离,用一个包含N个元素的一维数组s来存储推销员访问城市的顺序,其中每个元素s[i]的值表示第i个访问的城市,求解TSP问题的目标就是要找到某个城市访问顺序s

8、,使其路径长度最小,即最小化路径长度:(1)图1是求解TSP问题的基本SA算法,其中函数generate(s)表示从当前解s产生一个候选

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

《求解TSP问题的贪婪随机模拟退火算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、求解TSP问题的贪婪随机模拟退火算法钟一文,蔡荣英福建农林大学计算机与信息学院,福建福州,350002摘要:模拟退火算法是一种典型的智能优化算法,它的一个主要缺点是收敛速度慢。针对这一问题,提出了一种基于贪婪随机策略的求解旅行商问题的模拟退火算法,在从当前解的邻域中选择候选解时,根据问题领域的启发式信息,采用贪婪策略从邻域中生成一个候选解列表,再从候选解列表中随机选择一个候选解。仿真结果表明,贪婪随机模拟退火算法明显优于传统的模拟退火算法。关键词:模拟退火算法;贪婪随机;旅行商问题中图分类号:TP301文献标识码:A文章编号:AGreedyRan

2、domSimulatedAnnealingAlgorithmforTravelingSalesmanProblemZHONGYi-wen,CAIRong-yingCollegeofComputerandInformationScience,FujianAgricultureandForestryUniversity,Fuzhou350002,ChinaAbstract:SimulatedAnnealingalgorithmisatypicalintelligentoptimizationalgorithm.Oneofitsmainshortage

3、sisslowconvergencespeed.Inordertotacklethisshortage,agreedyrandomSimulatedAnnealingalgorithmforTravelingSalesmanProblemispresented.Inthepresentedalgorithm,basedonheuristicinformationderivedfromtheproblemathand,acandidatelistisselectedgreedilyfromtheneighborhoodofcurrentsoluti

4、on.Thencandidatesolutionisselectedrandomlyfromthecandidatelist.SimulatedresultsshowthattheproposedalgorithmcangetbetterresultthanclassicalSimulatedAnnealingalgorithm.Keywords:SimulatedAnnealingalgorithm;Greedyrandom;TravelingSalesmanProblem1引言模拟退火(SimulatedAnnealing,SA)算法是一种典

5、型的智能优化方法,SA算法的思想最早是由Metropolis等[1]提出的,SA算法依据Metropolis准则接受新解,因此,除接受优质解外,还在一定范围内接受劣质解,SA算法在开始时温度t值较大,可以接受较差的劣质解,随着t值的减小,只能接受较好的劣质解,最后在t值趋于零时,就不再接受任何劣质解了,这就使SA算法可以从局部最优的“陷阱”中跳出,从而有可能求得优化问题的全局最优解。SA算法同时还具有简单和通用的特点,因此SA算法在许多领域都得到了很好的应用,比如在VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。但是,尽管从理论

6、上证明了SA算法能收敛到全局最优解,在使用SA算法的过程中也发现,其收敛速度很慢,与此相反,启发式算法通常基于某种贪婪策略,有较快的收敛速度,但易于陷入局部最优解,那么,能否在SA算法中嵌入一定的贪婪策略,在保持其全局寻优的前提下,加快SA算法的收敛速度呢?基于这个思想,针对旅行商问题(TravelingSalesmanProblem,TSP),本文研究了在产生下一个解时,根据领域的启发式信息,采用贪婪策略从邻域中生成一个候选解列表,再从候选解列表中随机选择一个候选解,以平衡算法的随机性和贪婪性,提高获取优质解的概率,从而提高SA算法的总体性能,

7、仿真表明,这种策略能明显提高SA算法的性能。2求解TSP问题的模拟退火算法TSP问题是一个典型的NP-困难的组合优化问题。假设有一个推销员必须遍历N个城市,每个城市必须且只能访问一次,最后返回到出发城市,TSP问题就是要找到访问这些城市的顺序,使旅行线路的总长度最短。对一个包含N个城市的TSP问题,可以用一个N×N的二维数组d来存储城市间的距离,其中每个元素d[i][j]表示城市i和j之间的距离,用一个包含N个元素的一维数组s来存储推销员访问城市的顺序,其中每个元素s[i]的值表示第i个访问的城市,求解TSP问题的目标就是要找到某个城市访问顺序s

8、,使其路径长度最小,即最小化路径长度:(1)图1是求解TSP问题的基本SA算法,其中函数generate(s)表示从当前解s产生一个候选

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭