欢迎来到天天文库
浏览记录
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。经多次运行，程序最终结果都收敛于最优解，当然算法的收敛性还需要进一步的验证仿真，由于时间关系这里未作收敛性分析，有此曲线可知，中间波峰是由于回火所致。
此文档下载收益归作者所有
