下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 荷塘月色教育课件
- 课件网教学课件
- 人教版三年级下册音乐4-6单元教案
- 7500万米弹力革基布生产项目可行性研究报告模板-立项拿地
- 搅拌站防寒具体措施
- 综合实践课件教学课件
- 交通枢纽用地转让居间
- 产业园区道路改造居间合同
- 古建筑修复砂石运输协议
- 书店装修范本
- 精神科护士进修汇报
- 信息技术初探究(教学设计)三年级上册信息技术人教版
- 2024人教版道德与法治五年级上册第四单元:骄人祖先灿烂文化大单元整体教学设计
- 时代乐章第三课自然之美 课件 2024-2025学年人教版(2024)初中美术上册
- 康师傅智慧供应链管理:一体化体系与自动补货优化策略
- 《大学美育》 课件 7.模块三自然审美 第七章 感性表象之美
- 单品合同协议书
- 医学考博英语词汇
- 2024-2030年中国光谱分析仪行业市场发展趋势与前景展望战略分析报告
- 直播电商基础知识考核试题及答案
- 计算机各种进制转换练习题(附答案)
评论
0/150
提交评论