利模拟退火算法解决旅行商问题

1、利模拟退火算法解决旅行商问题武 健 同组：任旭东，刘 洋，李 丹（辽宁师范大学 物理与电子技术学院）摘要：旅行商问题（Traveling Salesman Problem，TSP），是数学领域中著名问题之一。组合优化领域里的一个典型的、易于描述却难以处理的NP完全难题。模拟退火（Simulatated Algorithm，SA）算法是通过控制退火参数，从而模拟退火过程进行的全局寻优的一种算法，用来在一个大的搜寻空间内找寻命题的最优解。通过MATLAB对优化过程进行仿真计算，证实了SA算法可以能够解决TSP问题。关键词：旅行商 模拟退火 优化 MATLAB1. 前言旅行商问题的简单描述是：一名商

2、人想到n个城市推销商品，如何选择一条路径使得商人每个城市走且只走一遍后回到起点，而且所走路径最短。基于TSP问题的特性，目前解决该问题的方法主要有禁忌搜索算法、神经网络优化算法、蚁群算法、遗传算法和模拟退火算法等。本文介绍了利用SA算法求解TSP问题的方法。2. 基本原理2.1旅行商问题中的相关定义(1)问题定义：Dij代表从城市i到城市j的距离(i,j=1,2,3,20)，问题是要找出遍访每个城市恰好一次的一条回路，且其路径长度R为最小。(2)解空间：解空间P是遍访每个城市恰好一次的所有回路，可表示为(1,2,3,20)的所有循环排列的集合。(3)新解的产生：在第120个访问的城市中随机选取

3、第i次和第j次访问的城市，在路径P中交换这两个城市的访问顺序其余不变，此时的路径为R1。(新解的产生方法不唯一) (4)目标函数：目标函数为访问所有城市的回路长度，需求其最小值。2.2模拟退火算法 模拟退火算法是一种非导数优化方法。模拟退火来源于拉丝玻璃的物理特性，原理类似于以一定的速率冷却金属时所发生的现象。缓慢下降的温度使融化金属中的原子排成有规则的结构，结果将产生具有较高能量的非晶体结构。在该算法中，温度较高时允许对远处的点求函数值，并且有可能接受一个具有较高能量的新点。而温度低时，模拟退火算法只在局部处求目标函数值，它接受较高能量新点的可能性非常小。 模拟退火算法包含的基本步骤：(1)

4、 选取一个起始点z，并设一个较高的起始温度T令迭代次数N=1；(2) 求目标函数E=f(x)的函数值；(3) 按照由生成函数g(x , T)确定的概率选择x，令新点xn等于x+x；(4) 计算新的目标函数值En=f(xn)；(5) 按照由接受函数h(E，T)确定的概率将x设为xn，E设为En，其中E=EnE；(6) 按照退火时间表降低温度T；(7) 增加迭代次数k，如果k达到最大迭代次数，停止迭代，否则返回步骤(3)。3. 具体工作程 序 初 始 化产 生 初 始 解达 到 稳 态满足算法终止条件最 终 解产 生 新 解满足Metropolis准则图1-1 程 序 流 程 图3.1选取起始点并

5、初始化变量 在利用模拟退火进行优化之前，必须首先选取一个优化的起始点，该优化起始点随机选取。本实验中设城市数目为20，Z=X,Y为城市坐标：X = 17 7 16 9 18 12 1 14 2 15 3 10 11 4 6 5 8 19 13 20Y = 1 18 4 7 15 13 11 20 6 19 5 3 8 17 12 9 2 16 14 103.2固定温度的模拟退火子函数 首先，在温度为一个较高值时，利用生成函数确定新的搜索点，常用的生成函数有Boltzman机使用的高斯密度函数，Cauchy机使用的Cauchy分布函数等。为了确定新数据是否能够被接受，必须选择一个适当的接受函数。

6、3.3降低温度继续优化过程 按照退火时间表降低温度，s=0.98T，重新进行模拟退火推理，直到满足停止条件。4. 结 论对程序进行多次MATLAB的优化仿真，最终能够找到最优解。可见利用模拟退火算法解决旅行商问题还是较为有效的，其初值鲁棒性也较好，可以将该模型应用于解决更多优化组合问题中。其实际模型在路径、网络、分配等优化问题中有着广泛的应用。模拟退火算法的试验性能具有质量高、初值鲁棒性强、通用易实现的优点，最大的缺点是优化过程较长。参考文献：1. 曲强、陈雪波 基于MATLAB的模拟退火算法的实现 鞍山科技大学学报 2003年6月2. 陈磊、毛亚林 基于MATLAB的非导数优化仿真 计算机应

7、用与IT技术 2005年1月3. 高尚 求解旅行商问题的模拟退火算法 华东船舶工业学院学报 2003年6月4. 潘昊、曲晓丽 旅行商问题的一种模拟退火算法求解 现 代 电 子 技 术 2007年第18期附 录(程序代码)：clc;N=1;Num=20;T=1000;T0=1e-3;k=150;s=0.98;x=17 7 16 9 18 12 1 14 2 15 3 10 11 4 6 5 8 19 13 20;y=1 18 4 7 15 13 11 20 6 19 5 3 8 17 12 9 2 16 14 10;z=x;y;z(1,21)=z(1,1);z(2,21)=z(2,1);p1=1

8、,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21;while T>T0 for t=1:k R1=0; for i=1:Num R1=R1+sqrt(z(1,p1(i)-z(1,p1(i+1).2+(z(2,p1(i)-z(2,p1(i+1).2); end R1 p2=p1; a=round(rand(1,2)*19+1); W=p2(a(1); p2(a(1)=p2(a(2); p2(a(2)=W; R2=0; for i=1:Num R2=R2+sqrt(z(1,p2(i)-z(1,p2(i+1).2+(z(2,p2(i)-z(2,p2(i+1).2); end if (R2-R1)<0 p1=p2; elseif exp(R1-R2)/T)>rand p1=p2; end temp(t,1:length(p1)=p1; R1=0; for i=1:Num R1=R1+sqrt(z(1,p1(i)-z(1,p1(i)+1).2+(z(2,p1(i)-z(2,p1(i)+1).2); end temp(t,length(p1)+1)=R1; end fmin i=min(temp(:,length(p