欢迎来到天天文库
浏览记录
ID:52929916
大小:184.80 KB
页数:5页
时间:2020-04-01
《回火记忆功能的返回遍历退火算法求解TSP问题.pdf》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、回火记忆功能的返回遍历退火算法求解TSP问题问题描述旅行商问题,即TSP问题(TravellingSalesmanProblem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。左边的路程小于右边的图1TSP问题示意图算法流程图开始、参数初始化初始解、初始温度T、回火初值t0、记忆装置等参数设定否t0>0.01?是T=t0,返回搜索标志anneal=1:2否anneal<=2?是
2、否T<退火停温?是迭代计数iter_num,目标连续未改变计数m_num清零iter_num3、4、(anneal==1&&exp(-∆f/T)>rand(1))?是存储新路径,iter_num++,m_mun=0m_mun++新路径<记忆路径?否是记忆新路径T=αT如果当前路径小于记忆路径则当前等于记忆t0=β×t0结果显示,结束程序对全国34个城市的TSP问题进行计算,求解得到的最优路径图如下:起始城市用红五角标记本次算法运行结果是:最优路径路程长为2119.095、25。经多次运行,程序最终结果都收敛于最优解,当然算法的收敛性还需要进一步的验证仿真,由于时间关系这里未作收敛性分析,有此曲线可知,中间波峰是由于回火所致。
3、
4、(anneal==1&&exp(-∆f/T)>rand(1))?是存储新路径,iter_num++,m_mun=0m_mun++新路径<记忆路径?否是记忆新路径T=αT如果当前路径小于记忆路径则当前等于记忆t0=β×t0结果显示,结束程序对全国34个城市的TSP问题进行计算,求解得到的最优路径图如下:起始城市用红五角标记本次算法运行结果是:最优路径路程长为2119.09
5、25。经多次运行,程序最终结果都收敛于最优解,当然算法的收敛性还需要进一步的验证仿真,由于时间关系这里未作收敛性分析,有此曲线可知,中间波峰是由于回火所致。
此文档下载收益归作者所有