APP下载

改进模拟退火算法在TSP中的应用

2018-01-24张驰汪海涛姜瑛陈星

软件 2017年7期
关键词:张驰定界模拟退火

张驰 汪海涛 姜瑛 陈星

摘要:为了有效优化旅行商问题(TSP)的旅行路径,通过分析传统模拟退火算法的优缺性,提出了一种改进扰动机制并结合分支定界的模拟退火算法。为了弥补模拟退火(SA)算法对初始解的依赖性,该算法首先通过分支定界产生一个较优的初始解,通过对SA温度参数和扰动机制的的有效控制,进行全局优化。采用TSPLIB中的标准库文件验证,测试的数据显示改进的SA算法和传统算法相比较,在針对此类问题的求解上有着良好的性能。

关键词:旅行商问题;扰动机制;分支定界算法;模拟退火算法endprint

猜你喜欢

张驰定界模拟退火
Structural origin for composition-dependent nearest atomic distance in Cu–Zr metallic glass
Fast and perfect state transfer in superconducting circuit with tunable coupler
结合模拟退火和多分配策略的密度峰值聚类算法
RTK技术在土地勘测定界中的应用研究
一类DC规划问题的分支定界算法
模拟退火遗传算法在机械臂路径规划中的应用
基于外定界椭球集员估计的纯方位目标跟踪
张驰
基于模糊自适应模拟退火遗传算法的配电网故障定位
SOA结合模拟退火算法优化电容器配置研究