论文研究-求解TSP问题的改进模拟退火算法.pdf

所需积分/C币:14 2019-09-06 19:04:57 646KB .PDF
7
收藏 收藏
举报

通过分析传统模拟退火算法的原理和存在的不足,提出了一个用于求解TSP问题的改进模拟退火算法。新算法增加了记忆当前最好状态的功能以避免遗失当前最优解,并设置双阈值使得在尽量保持最优性的前提下减少计算量。根据TSP和SA的特征设计了个体邻域搜索方法和高效的计算能量增量方法,加快了算法的运行速度。实验测试的结果表明,新算法比传统的模拟退火算法具有更快的收敛速度和更优的解质量。
362010,46(15) Computer Engineering and Applications计算机工程与应用 步骤8i(mum> DIMINISH TNUM), then ain=aim+1,mum=0。 表1改进SA算法的TSP实验结果 步骤9if(f(best)≤∫(x)), then best=x,转步骤2,f为个体 ISP实例城市规模目前最优解最好平均值偏差 适应度计算函数 20202020240.2% 步骤10以best为最终解输出,算法结束。 berlins 7542 754275540.2% 其中,T为k时刻的温度,它满足温度下降公式: 5400 Chn150 652 653265981.1% h (3) Rat195 234723862.7% Lin318 318 4202942230435273.6% 当迭代次数k达到温度下降总次数时,终止迭代。 Rat575 575 6773681270634.3% 由以上对改进SA算法的步骤描述,可得出算法具有如下 55000 的特点 改进模拟退火 45000 传统模拟退火 (1)增强了算法的搜索效率。在每个温度值时对个体进行 35000 多次 boltzmann更新,搜索更加充分。 25000 (2)通过设置双阈值使得在尽量保持最优性的前提下减少 15000 计算量。在各温度下当前状态连续 DIMINISHTNUN次保持不 5000 变则认为 Metropolis抽样稳定,若连续AM次退温过程中所得 04080120160200 的最优解均不变则认为算法收敛。 模拟退火次数 图4SA算法改进前后收敛曲线图 (3)增加了记忆功能。在算法搜索过程中记住中间最优解, 并即时更新,使之能记住搜索过程中遇到的最好解,避免了由4结束语 于执行概率接受环节而遗失当前遇到的最优解,增加了这种记 通过分析传统SA算法原理和存在的不足,提出了一个改 忆能力的模拟退火算法已成为一种智能化的算法。 进的模拟退火算法。根据TSP和SA的特征设计了个体邻域搜 索方法和高效的计算能量增量方法,极大加快了算法的运行速 3实验仿真 度。通过对标准的 TSPLib中不同国家城市的数据进行测试表 采用普通PC机,微处理器为 Pentium4(1.6G),内存1.00GB,明较传统的SA算法,该算法在时间性能上有较大的提高,能 用VC++2008编写程序进行实验验证算法的有效性,图3为求得到更优的解且容易收敛到问题的最优解,尤其在选取城市规 解TSP问题的程序操作界面。 模较小的情况下效率有明显的改观。该文算法并没有改变SA 品改进模-T回网 每次只是记录一个点,对解决大规模问题搜索效率低的问题, 文件〔)编辑)帮助 在以后的研究中应结合其他进化算法(如遗传算法)在此方面 的长处加以改进 参考文献: [1 Steinbrunn M, Moerkotte G, Kemper A Heuristic and randomized op- timization for the join ordering problem[J.The VLDB Journal, 1997,6 图3改进SA算法求解TSP程序界面 2]刘毅熊盛武TP问题的禁忌模拟退火求解J计算机工程与应用, 2009,45(31):43-45 该文所选测试实例来自国际通用的TSP实例库 TSPLIB,31 Kirkpatrick s, Gelartt c d, Vecchi me. Optimization by simulated 实验选取了7个对称的TSP,每个实例做20次测试,记录每次 annealing[J). Science, 1983, 220(11): 650-671 的实验结果,城市间距离以整数计算。表1为改进SA算法的41朱颢东,钟勇.一种改进的模拟退火算法计算机技术与发展, ISP实验结果,由结果数据可以看出,SA在城市规模较少时, 2009,19(6):32-35 如城市规模为52和76时,可以达到目前的最优结果,即使在「5吴大为,陆涛栋,刘晓冰求解作业车间调度问题的并行模拟退火算 城市规模达到575时,所求最优解可达到目前最优解的95.7% 法J计算机集成制造系统,2005,11(6):847-850 以上,而且算法收敛速度较快,在城市规模为200以下时,均可(高海昌,冯博琴朱利智能优化算法求解TP问题J控制与决策, 在60s内找到较优解。 2006,21(3):241-247 图4为测试实例Chm150分别使用传统SA算法和改进后71庞哈利郑秉霖,徐心和一种自适应的模拟退火算法机控制与决 策,1999,14(5):23-28. 的SA算法的收敛曲线,记录算法每一次降温的路径距离。图 [8]林慧君,彭宏模拟退火算法在全局查询优化中的应用J计算机技 中可以看出,改进后的SA在求解速度上较传统SA有相当大 术与发展,2006,16(4):155-157 的提高,经过40次左右降温基本能收敛到问题的解,求解精度9标准的TSP测试库[Db/olHttp:/www.iwr.uniheidelherg.de/groups/ 也有一定程度的提高 comopt/software/TSPLIB95/tsp/

...展开详情
试读 3P 论文研究-求解TSP问题的改进模拟退火算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744375 你的留言是对我莫大的支持
2019-09-06
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信
上传资源赚积分or赚钱
最新推荐
论文研究-求解TSP问题的改进模拟退火算法.pdf 14积分/C币 立即下载
1/3
论文研究-求解TSP问题的改进模拟退火算法.pdf第1页

试读结束, 可继续阅读

14积分/C币 立即下载 >