版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、模拟退火算法求解TSP问题作者:ymhui下载源代码一、问题描述旅行商问题,即TSP问题(TravellingSalesmanProblem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。图1TSP问题的示意图二、遍历算法一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来,并逐一比较,选出最小的路径。虽然该方法在理论上是可行的,但路径的个数与城市的个数成指数增长,当城市个数较大时,该方法的求解时间是难以忍受的,甚至是不可能完成
2、的。以每秒1亿次的计算速度来估算,如果TSP问题包含20个城市时,求解时间长达350年;如果要处理30个城市,则求解时间更长达1+10e16年。如此长的时间,在实际中完成是难以想象的。三、模拟退火算法模拟退火算法是解决TSP问题的有效方法之一,其最初的思想由Metropolis在1953年提出,Kirkpatrick在1983年成功地将其应用在组合最优化问题中。模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。用固体退火模拟组合优化问题,将内能
3、E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解一计算目标函数差一接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。求解TSP的模拟退火算法模型可描述如下:解空间:解空间S是遍访每个城市恰好一次的所有路经,解可以表示为wl,w2,wn,w1,wn是1,2,n的一个排列,表明w1城市出发,依次经过w2,wn城市,再返回w1城市。初始解可选为(1,n);目标函数:目标函数为访问所有城市的路径总长度;我们要求的最优路径为目标函数为最小值时
4、对应的路径。新路径的产生:随机产生1和n之间的两相异数k和m,不妨假设km,则将原路径(w1,w2,,wk,wk+1,,wm,wm+1,,wn)变为新路径:(w1,w2,wm,wk+1,wk,wm+1,wn)上述变换方法就是将k和m对应的两个城市在路径序列中交换位置,称为2-opt映射。根据上述描述,模拟退火算法求解TSP问题的流程框图如下图2模拟退火算法的流程框图四、主要代码对应于流程框图,实现流程的主体函数是SAComputionO,代码如下:UINTSACompution(LPVOIDpParam)while(l)doubledeltatotaldis=0.0;while(l)SYRou
5、terSelRouter(ResultRouter.m_CityRouter,NowTemperature,NowExternalIterNumber,NowInnerIterNumber);/从某路径的邻域中随机选择一个新的路径,邻域映射为2-optdeltatotaldis=SelRouter.m_fTotalDistanceResultRouter.m_fTotalDistance;-/计算新路径与当前路径的路程长度差值if(deltatotaldisrandom)ResultRouter=SelRouter;/如果新路径长于当前路径,但exp(Af/1)random(0,1),则仍然替
6、换当前路径if(JudgeOverInnerLoop(0)break;/判断内循环是否结束,结束则跳出当前温度的内循环elseNowInnerIterNumber+;/判断内循环是否结束,不结束则继续内循环if(JudgeOverExternalLoop(O)break;/判断外循环是否结束,结束则结束模拟退火计算elseNowTemperature=CountDownTemperature(NowTemperature,0);NowExternalIterNumber+;NowInnerIterNumber=0;/判断外循环是否结束,不结束则计算出下降后的温度,并继续循环五、算例测试程序对48个城市的TSP问题(城市坐标文件对应于48.txt,已放在发布的源码中)进行计算,求解得到的最优路径图如下。图3模拟退火算法获得的最优路径图48个城市的计算结果,大的红*表示路径开始城市,途经城市依次用蓝色方块和红色*标示。六、调试环境WindowsXPProfessionalVisualC+6.0STLport4.6.2比较简明易懂的文章,补充一点,关于温度
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二四年度废液处理与资源化利用合同
- 店面装饰装修施工合同(2篇)
- 担保合同范本
- 商铺租赁协议书(2篇)
- 化妆品包销协议书(2篇)
- 租赁转购买设备协议
- 品牌许可合同模板
- 摇一摇服务合同的违约金支付方式
- 纸张买卖招标文件
- 付费翻译服务合同
- DB31-T 1439-2023 养老服务机构信用评价规范
- 井陉秀林110kV变电站电缆沟施工方案
- 实验室消防安全安全管理PPT
- 竖井工程地质勘察报告
- 儿科运用PDCA循环提高儿科患者家属对护理服务的满意度PDCA 案例
- 高中音乐人音版音乐《音乐鉴赏》新音乐初放单元教学设计
- 燃气公司技术档案管理制度
- 企业全域会员运营整合解决方案
- 生产车间员工绩效考核评分标准说明表
- 《现代汉语》(增订6版)笔记和课后习题(含考研真题)详解
- 新药的非临床药效学研究和评价
评论
0/150
提交评论