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

利模拟退火算法解决旅行商问题 武 健 同组：任旭东，刘 洋，李 丹 （辽宁师范大学 物理与电子技术学院） 摘要： 旅行商问题（Traveling Salesman Problem，TSP），是数学领域中著名问题之一。组合优化领域里的一个典型的、易于描述却难以处理的NP完全难题。模拟退火（Simulatated Algorithm，SA）算法是通过控制退火参数，从而模拟退火过程进行的全局寻优的一种算法，用来在一个大的搜寻空间内找寻命题的最优解。通过MATLAB对优化过程进行仿真计算，证实了SA算法可以能够解决TSP问题。 关键词：旅行商 模拟退火 优化 MATLAB 前言 旅行商问题的简单描述是：一名商人想到n个城市推销商品，如何选择一条路径使得商人每个城市走且只走一遍后回到起点，而且所走路径最短。基于TSP问题的特性，目前解决该问题的方法主要有禁忌搜索算法、神经网络优化算法、蚁群算法、遗传算法和模拟退火算法等。本文介绍了利用SA算法求解TSP问题的方法。 基本原理 2.1旅行商问题中的相关定义 (1)问题定义： Dij代表从城市i到城市j的距离(i,j=1,2,3,……,20)，问题是要找出遍访每个城市恰好一次的一条回路，且其路径长度R为最小。 (2)解空间：解空间P是遍访每个城市恰好一次的所有回路，可表示为(1,2,3,……,20)的所有循环排列的集合。 (3)新解的产生：在第1~20个访问的城市中随机选取第i次和第j次访问的城市，在路径P中交换这两个城市的访问顺序其余不变，此时的路径为R1。(新解的产生方法不唯一) (4)目标函数：目标函数为访问所有城市的回路长度，需求其最小值。 2.2模拟退火算法 模拟退火算法是一种非导数优化方法。模拟退火来源于拉丝玻璃的物理特性，原理类似于以一定的速率冷却金属时所发生的现象。缓慢下降的温度使融化金属中的原子排成有规则的结构，结果将产生具有较高能量的非晶体结构。在该算法中，温度较高时允许对远处的点求函数值，并且有可能接受一个具有较高能量的新点。而温度低时，模拟退火算法只在局部处求目标函数值，它接受较高能量新点的可能性非常小。 模拟退火算法包含的基本步骤： 选取一个起始点z，并设一个较高的起始温度T令迭代次数N=1； 求目标函数E=f(x)的函数值； 按照由生成函数g(Δx , T)确定的概率选择Δx，令新点xn等于x+Δx； 计算新的目标函数值En=f(xn)； 按照由接受函数h(ΔE，T)确定的概率将x设为xn，E设为En，其中ΔE=En—E； 按照退火时间表降低温度T； 增加迭代次数k，如果k达到最大迭代次数，停止迭代，否则返回步骤(3)。 具体工作 程 序 初 始 化 程 序 初 始 化 产 生 初 始 解 达 到 稳 态 满足算法终止条件 最 终 解 产 生 新 解 满足Metropolis准则 图1-1 程 序 流 程 图 3.1选取起始点并初始化变量 在利用模拟退火进行优化之前，必须首先选取一个优化的起始点，该优化起始点随机选取。本实验中设城市数目为20，Z=[X,Y]为城市坐标： 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] 3.2固定温度的模拟退火子函数 首先，在温度为一个较高值时，利用生成函数确定新的搜索点，常用的生成函数有Boltzman机使用的高斯密度函数，Cauchy机使用的Cauchy分布函数等。为了确定新数据是否能够被接受，必须选择一个适当的接受函数。 3.3降低温度继续优化过程 按照退火时间表降低温度，s=0.98T，重新进行模拟退火推理，直到满足停止条件。 结 论 对程序进行多次MATLAB的优化仿真，最终能够找到最优解。可见利用模拟退火算法解决旅行商问题还是较为有效的，其初值鲁棒性也较好，可以将该模型应用于解决更多优化组合问题中。其实际模型在路径、网络、分配等优化问题中有着广泛的应用。模拟退火算法的试验性能具有质量高、初值鲁棒性强、通用易实现的优点，最大的缺点是优化过程较长。 参考文献： 1. 曲强、陈雪波 《基于MATLAB的模拟退火算法的实现》 鞍山科技大学学报 2003年6月 2. 陈磊、毛亚林 《基于MATLAB的非导数优化仿真》 计算机应用与IT技术 2005年1月 3. 高尚 《求解旅行商问题的模拟退火算法》 华东船舶工业学院学报 2003年6月 4. 潘昊、曲晓丽 《旅行商问题的一种模拟退火算法求解》 现 代 电 子 技 术 2007年第18期 附 录(程序代码