基于模拟退火算法的TSP算法.doc
《基于模拟退火算法的TSP算法.doc》由会员分享,可在线阅读,更多相关《基于模拟退火算法的TSP算法.doc(12页珍藏版)》请在咨信网上搜索。
1、专业综合设计报告课程名称:电子专业综合设计 设计名称: 基于模拟退火算法的TSP算法姓名:学号: 班级:电子0903指导教师:朱正为 起止日期:2012。11。12012.12。30专业综合设计任务书学生班级:电子0903 学生姓名:学号: 20095830 设计名称:基于模拟退火算法的TSP算法 起止日期:2012。11.12012.12。30指导教师设计要求:旅行商问题,即TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,
2、而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 此设计是用模拟退火算法来实现TSP问题的寻求最优解。专业综合设计学生日志时间设计内容2012.11.9初步了解模拟退火算法的TSP算法2012。11.12设计算法流程、确定解题思路2012。11.20讨论算法流程及解题思路的可行性,为仿真做准备2012。12。2运用MATLAB软件进行实验仿真,分析仿真结果2012。12。8整理实验报告2012.12.17答辩专业综合设计考勤表周星期一星期二星期三星期四星期五专业综合设计评语表指导教师评语:成绩:指导教师:年月日一 设计目的和意义5二设计原理52。1 模拟退
3、火算法的基本原理.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.52。2 TSP问题介绍.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。6三详细设计步骤。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。73.1.算法流程83.2模拟退火算法实现步骤8四设计结果及分析94。1 MATLAB程序实现及主函数.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.
4、。.。.。.。.。94.1.1 计算距离矩阵.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。9 4。1.2 初始解。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。10 4。1.3 生成新解.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。10 4。1。4 Metropolis 准则函数。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。. .。.10 4。1。5 画路线轨迹图.。.。.。.。.。.。.。.。
5、.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。11 4。1。6 输出路径函数。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。12 4。1。7 可行解路线长度函数。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.12 4.1.8 模拟退火算法的主函数.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.134。2。仿真结果15五体会18六参考文献19基于模拟退火算法的TSP算法一 、设计目的和意义 旅行商问题是组合优化领域里的一个典
6、型的、易于描述却难以处理的NP难题,其可能的路径数目与城市数目是呈指数型增长的,求解非常困难.首先介绍了旅行商问题,给出了其数学描述以及实际应用,进而给出解决TSP的一种比较精确的算法-模拟退火算法.然后阐述了模拟退火算法的基本原理,重点说明了其基本思想及关键技术.最后运用MATLAB语言实现了该算法,并将其运用到解决旅行商问题的优化之中。数值仿真的结果表明了该方法能够对数据进行全局寻优,有效克服了基于导数的优化算法容易陷入局部最优的问题。 了解模拟退火算法的TSP算法的基本思路及原理,并应用MATLAB实现仿真,熟练掌握MATLAB的操作方式及应用,能正确书写报告。二 、设计原理2。1 模拟
7、退火算法的基本原理 模拟退火算法足2O世纪8O年代初提出的一种基于蒙特卡罗(Mente Carlo)迭代求解策略的启发式随机优化算法。它通过Metropolis接受准则概率接受劣化解并以此跳出局部最优,通过温度更新函数的退温过程进行趋化式搜索并最终进入全局最优解集。其出发点是基于物理中固体物质的退火过程与一搬的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法,其物理退火过程由以下三部分组成。(1) 加温过程。 其目的是增强粒子的热运动,使其偏离平衡位置.当温度足够高时,固体将熔为液体,从而消除系统原先存在的非均匀状态。(2) 等温过程. 对于与周围环境交换热量而温度不变的密封系统,系统
8、状态的自发变化总是朝自由能减少的方向进行的,当自由能达到最小时,系统达到平衡状态。(3) 冷却过程。 使粒子热运动减弱,系统能量下降,得到晶体结构。 其中,加热过程对应算法的设定初温,等温过程对应算法的 Metropolis 抽样过程,冷却过程对应控制参数的下降.这里能量的变化就是目标函数,要得到的最优解就是能量最低态。Metropolis 准则是SA算法收敛于全局最优解的关键所在,Metropolis 准则以一定的概率接受恶化解,这样就使算法跳离局部最优的陷阱。 模拟退火算法为求解传统方法难处理的TSP问题提供了一个有效的途径和通用框架,并逐渐发展成一种迭代自适应启发式概率性搜索算法。模拟退
9、火算法可以用以求解不同的非线性问题,对不可微甚至不连续的函数优化,能以较大的概率求的全局有化解,该算法还具有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性,并且能处理不同类型的优化设计变量(离散的、连续的和混合型的),不需要任何的辅助信息,对目标函数和约束函数没有任何要求。利用 Metropolis 算法并适当的控制温度下降过程,在优化问题中具有很强的竞争力,此设计即为基于模拟退火算法的TSP算法。 SA算法实现过程如下(以最小化问题为例): (1)初始化:取初始温度T0足够大,令T=T0,任取初始解S1,确定每个T时的迭代次数,即 Metropolis 链长L.(2)对当前温度T和k=1
10、,2,l,重复步骤(3)(6)。 (3)对当前S1随机扰动产生一个新解S2. (4)计算S2的增量df=f(S2)f(S1) 其中f为S1的代价函数。(5)若df1。其每一边(i,j)E有一非负整数耗费 Ci,j(即上的权记为Ci,j,i,jV)。G的一条巡回路线是经过V中的每个顶点恰好一次的回路.一条巡回路线的耗费是这条路线上所有边的权值之和.TSP问题就是要找出G的最小耗费回路.人们在考虑解决这个问题时,一般首先想到的最原始的一种方法就是:列出每一条可供选择的路线(即对给定的城市进行排列组合),计算出每条路线的总里程,最后从中选出一条最短的路线。假设现在给定的4个城市分别为A、B、C和D,
11、各城市之间的耗费为己知数,如图1所示.我们可以通过一个组合的状态空间图来表示所有的组合,如图图 1 顶点带权图 图 2 TSP问题的解空间树从图中不难看出,可供选择的路线共有6条,从中很快可以选出一条总耗费最短的路线:顶点序列为(A,C,B,D,A).由此推算,若设城市数目为n时,那么组合路径数则为(n1)!.很显然,当城市数目不多时要找到最短距离的路线并不难,但随着城市数目的不断增大,组合路线数将呈指数级数规律急剧增长,以至达到无法计算的地步,这就是所谓的“组合爆炸问题.假设现在城市的数目增为20个,组合路径数则为(20-1)!1.2161017,如此庞大的组合数目,若计算机以每秒检索100
12、0万条路线的速度计算,也需要花上386年的时间6.三 、详细设计步骤3。1算法流程模拟退火算法求解流程框图如图1所示.图3 模拟退火算法求解流程框图3。2模拟退火算法实现步骤如下: (1)控制参数的设置 需要设置的主要控制参数有降温速率q、初始温度T0、结束温度Tend以及链长L。 (2)初始解 对于n个城市TSP问题,得到的解就是对1n的一个排序,其中每个数字为对应城市的编号,如对10个城市的TSP问题1,2,3,4,5,6,7,8,9,10,则 |11024|568793就是一个合法的解,采用产生随机排列的方法产生一个初始解S. (3)解变换生成新解 通过对当前解S1进行变换,产生新的路径
13、数组即新解,这里采用的变换是产生随机数的方法来产生将要交换的两个城市,用二邻域变换法产生新的路径,即新的可行解S2。 例如n=10时,产生两个1,10范围内的随机整数r1和r2,确定两个位置,将其对换位置,如r1=4,r2=7 9 5 1 6 3 8 7 10 4 2 得到的新解为 9 5 1 7 3 8 6 10 4 2 (4)Metropolis准则 若路径长度函数为(S),新解的路径为(S2),路径差为d=(S2)(S1),则Metropolis准则为如果df0,则以概率1接受新路线,否则以概率exp(df/T)接受新路线. (5)降温 利用降温速率q进行降温,即T=qT,若T小于结束温
14、度,则停止迭代输出当前状态,否则继续迭代.四 、设计结果及分析4。1 MATLAB程序实现及主函数4.1。1 计算距离矩阵利用给出的N个城市的坐标,算出N个城市的两两之间的距离,得到距离矩阵(NN).计算函数为Distance,得到初始群种。程序如下function D=Distanse(a)% 计算两两城市之间的距离%输入 a 各城市的位置坐标%输出 D 两两城市之间的距离row=size(a,1);D=zeros(row,row);for i=1:row for j=i+1:row D(i,j)=(a(i,1)-a(j,1)2+(a(i,2)-a(j,2)2)0.5; D(j,i)=D(i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 模拟 退火 算法 TSP
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。