基于MATLAB的模拟退火算法解决旅行推销员问题的研究

03MATLAB仿真实验与算法改进01旅行推销员问题介绍02模拟退火算法介绍03MATLAB仿真实验与算法改进01旅行推销员问题介绍02模拟退火算法介绍给定N个城市和每个城市之间的距离，推销员要访问每一个城市，并且只去一次，最终返回原城市，寻找最短路径。旅行推销员问题简介旅行推销员问题（TravellingSalesmanProblem，又称为旅行商问题、货郎担问题、TSP问题）是一个多局部最优的优化问题：给定N个城市和每个城市之间的距离，推销员要访问每一个城市，并且只去一次，最终返回原城市，寻找最短路径。旅行推销员问题由爱尔兰数学家SirWilliamRowanHamilton和英国数学家ThomasPenyngtonKirkman在19世纪提出的数学问题WilliamRowanHamilton旅行推销员问题研究意义现实生活中经常要同时考虑多个目标，目标之间往往存在冲突性，我们要在多个目标中寻找一个公平、合理的最优解。如路程最短、时间最短、费用最省、风险最小等多方面的因素。该问题的实际模型在VLSI芯片设计、连锁店的货物配送、网络路由设计、物流、生产调度等领域有着广泛的应用价值，故研究TSP问题，对科学管理与经济决策的许多应用领域中都有重大意义。03MATLAB仿真实验与算法改进01旅行推销员问题介绍02模拟退火算法介绍模拟退火算法(SimulatedAnnealingAlgorithm,SAA)是一种通用概率算法，用来在固定时间内寻求在一个大的搜寻空间内找到的最优解。适合解决大规模组合优化问题，特别是NP完全类问题的通用有效近似算法。模拟退火算法最早的思想是由Metropolis在1953年提出的，由S.Kirkpatrick,C.D.Gelatt和M.P.Vecch于1983年成功地将其应用在组合最优化问题中，目前已经应用到各门学科中以解决非线性系统中的优化问题。物理退火在冶金学或材料工程中，退火（Annealing）是一种能够改变材料微结构，进而改变硬度和强度的机械性质的热处理。过程为将金属加温到某个高于再结晶温度的一点并维持此温度一段时间，再将其缓慢冷却。加温维持温度缓慢冷却加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。物理退火模拟退火算法物理退火优化问题物质状态解能量最低的物质状态最优解退火过程求解过程温度T控制参数t能量E目标函数F等温过程Metropolis抽样过程模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解，计算目标函数的差，接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。Metropolis准则是SA算法收敛于全局最优解的关键，是Metropolis等人在1953年提出的重要性采样法，其基本采样思想是着重选择那些具有重要贡献的状态，则可以较快地达到较好的结果。温度越小，则降温概率p就越小，温度越高，与出现一次能量差为dE的降温概率p就越大。p越大则j状态是重要状态的概率就越大。若j是重要状态，则取代i成为当前状态，否则舍弃新状态再重复以上新状态产生过程。这种接受新状态转移的准则即为Metropolis准则。Metropolis准则

解空间：解空间X是访遍每一个城市且只有一次的所有路经，解可以表示为{x1,x2,……,xn}，x1,……,xn是1,2,……,n的一个排列，表明x1城市出发，依次经过x2,……,xn城市，再返回x1城市。初始解可选为(1,……,n);目标函数：访问所有城市的路径总长度；其中最优路径为目标函数等于最小值时所对应的路径。新路径的产生：随机产生1和n之间的两相异数k和m，假设k<m，则将原路径：(x1,x2,…,xk,xk+1,…,xm,xm+1,…,xn)变为新路径：(x1,x2,…,xm,xk+1,…,xk,xm+1,…,xn)模拟退火算法解决TSP问题模型求解旅行推销员问题（TSP）的模拟退火算法模型可描述如下:YYYYNNNN选择初始路径X0确定初始温度T0当前路径Xi=X0当前温度Ti=T0Exp(-△f/Ti)>random(0,1)跳出外循环结束

当前温度Ti下降从Xi的邻域中随机选择Xj，计算Xi与Xj的路程差△f=f(Xj)-f(Xi)△f<=0

当前路径Xi=Xj跳出内循环选一初始状态X0,作为当前解：并且确定初始温度T0，令当前的Xi=X0和Ti=T0。然后从Xi的邻域中随即选择Xj，计算Xi与Xj的路径差，比较差值。按一定方式将T降温，即令T(t+1)＝k×T(t)，i=i+1，然后检查退火过程是否结束，如果不是继续交换，如果是的话输出Xi作为最优输出。模拟退火算法的流程图模拟退火算法在搜索策略上与传统的随机搜索方法不同，它是一种启发式随机搜索算法。不仅引人了物理系统退火过程的自然机理，而且还引入了适当的随机因素。它在迭代过程中，不但能接受使目标函数值变“好”的点，又能够以一定的概率接受使目标函数值变“差”的点。接受概率随着温度的下降逐渐减小，因为在整个解的邻域范围内取值的随机性，可使算法避免陷入局部最优解，有利于提高求得全局最优解的可靠性。模拟退火算法的效果示范局限性123在目标函数复杂、变量多时，执行时间长。为了得到一个好的近似解,控制参数T需要从一个较大的值开始,并需要在每一个温度值T下执行多次Metropolis算法，导致减慢迭代运算的速度。温度T的初始数据和减小步长较敏感。如果温度T的初值选择较大，减小步长太小，虽然最终能得到较优的解,但算法收敛速度太慢；如果温度T的初值选择较小，减小步长过大，可能得不到全局最优解。容易遗失当前遇到的最优解。搜索过程通过执行概率接受来判断。模拟退火算法的局限性1)模拟退火算法自身要素改进增加升温或重升温过程增加补充搜索过程增加记忆功能……模拟退火算法的改进策略2)和其他算法结合遗传算法混沌搜索禁忌算法……03MATLAB仿真实验与算法改进01旅行推销员问题介绍02模拟退火算法介绍TSP问题假设有40个城市，坐标矩阵如下（单位：km），第一行是各城市的横坐标，第二行是各城市的纵坐标：zuobiao=[2.373.751.453.765.714.071.426.595.323.64.35.675.622.671.204.350.270.940.821.371.612.420.67.390.532.40.632.51.983.680.553.763.885.651.785.252.102.400.622.555.51.22.80.994.06.92.662.44.71.3;6.913.870.852.750.726.742.710.693.645.643.590.593.550.550.51.451.433.420.382.272.260.256.230.192.191.132.082.045.020.852.320.153.301.552.901.741.760.350.291.282.30.993.52.91.23.80.451.24.70.5];待寻优城市位置分布利用基本的模拟退火算法：（1）初始解的产生：随机产生城市序列。（2）新解的产生：随机选择两个城市，交换在路径上的位置。选择不同的初温、温度变化率和在每个温度下的搜索次数得到的仿真实验结果。终止温度为0.001。取不同参数时模拟退火算法对40城市寻优的仿真结果实验次数初始温度每个温度下的搜索次数温度变化率最优距离（km）运行时间（秒）11005000.9545.496862.052786210015046.832523.27674231005055.601710.629814450010047.827919.39315855005052.506514.5146916100030048.815448.4334757100010050.469022.460067810005051.092812.6625459200015045.393641.710554210200010047.289020.096185111005000.7550.854115.9211521210030056.64548.10133113500100043.931124.2264951450080045.973619.3682961550050050.381114.5637071650030047.52729.4693691750010054.05964.18842718100030050.53598.94543919100020051.75597.19137220100010052.26457.12147921200030051.75439.25097822200020053.51677.42748723200010057.12305.3151532450010000.65

45.235017.5530902550050049.411410.94340326100020054.20425.23688327200010051.26487.130828当初始温度较大，结束温度较低，温度下降较慢，每个温度的搜索次数较多时，优化结果比较好，但是需要的计算时间很长。如果采取适当高的初温和搜索次数，可以缩短计算时间。如果加快温度下降速度，可以明显缩短计算时间，但是要通过实验选择合适的初温和每个温度下的搜索次数，否则计算结果不佳。如果每个温度下的搜索次数不够，即使取到较高的初温，寻优结果也不令人满意。如果温度选择不合适，容易陷入局部极值。MATLAB仿真结果分析采取不同的参数做了多组仿真实验，将典型结果列在上表中。从表中数据可知以下结论：改进再搜索记忆新解初始解每次搜索时保存当前寻到的历史最优值，以保证最优值不被丢掉。产生一个初始解群，从中挑选一个最优解，作为初始解。以争取在开始时尽量遍历整个解空间，找到一个相对好的解，为搜索做一个较好的开始。在整体搜索结束后，在寻到的最优解附近，利用贪婪搜索的思路，进行小范围的搜索，只接受比当前解更好的新解。为减少冗余计算，将禁忌搜索的思路引入进来，每次记录互换的城市序号，如果下一次迭代他们又被选中互换，则重新选择互换的城市，以避免重复的计算。模拟退火算法的