求解TSP的贪心模拟退火算法

李金旭，黄悦悦

(1.郑州幼儿师范高等专科学校 信息网络部，河南 郑州 450001;

2.黄河科技学院 国际学院，河南 郑州 450001)



求解TSP的贪心模拟退火算法

李金旭1，黄悦悦2

(1.郑州幼儿师范高等专科学校 信息网络部，河南 郑州 450001;

2.黄河科技学院 国际学院，河南 郑州 450001)

摘要：通过分析传统模拟退火算法的不足和可行的改进方案，提出了一个用于求解TSP问题的贪心模拟退火算法.新算法在改进的模拟退火算法的基础上结合改进的贪心算法，增加了算法的解的质量.实验表明，新的算法比传统的模拟退火算法和贪心算法有更优的解.

关键词：模拟退火算法；贪心算法；TSP；组合优化

TSP(Traveling Salesman Problem，旅行商问题)是数学领域著名的问题之一，又被称为旅行销售员问题或货郎担问题.TSP问题是一个组合优化问题,任何能使该问题的求解得以简化的方法都会受到高度的关注和评价.目前,用来求解TSP问题的主要算法有遗传算法[1]、模拟退火算法[2]、蚁群算法[3]、神经网络算法[4]和混合策略算法[5].

模拟退火算法(Simulated Annealing, SA)[6]最早是由Metropolis于1953年提出的.1983 年,Kirkpatrick 成功地将退火思想引入组合优化领域.它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性.本研究分析了传统SA算法的原理和不足，提出了一个结合贪心算法和模拟退火算法的贪心模拟退火算法.实验证明，改进的算法是有效的.

1贪心模拟退火算法

1.1传统SA算法的缺点和改进策略

模拟退火的基本思想如下:

(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L，n=0.

(2) 对k=1，…，L,做第(3)至第(6)步.

(3) 产生新解S′.

(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数.

(5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.

(6) n=n+1，若n

(7) 如果满足终止条件则输出当前解作为最优解，结束程序,终止条件通常取连续若干个新解都没有被接受时终止算法.

(8) n=0, T逐渐减少且T→0，然后转第(2)步.

模拟退火算法包含内外两个循环，可以分解为解空间、目标函数和初始解3部分。

传统模拟退火算法的优点有以一定的概率接受恶化解,引进了算法控制参数T,可使用对象函数值进行搜索,隐含并行性并可搜索复杂区域.但是传统模拟退火算法的优点在某些情况下反而会成为算法的缺点,比如求解时间太长,温度T参数的初始值和衰减程度较难确定,接受概率是随机的或者是不确定的，使得有可能丢失全局最优解.

通过对模拟退火算法的过程、优点和缺点的研究分析，可行的改进方案组如下：

(1)赋予合适的初始状态值，增加最终解的质量；

(2)改进温度更新的方式，加快收敛速度，避免陷入局部最优解；

(3)改进状态产生函数，避免遗漏最优解；

(4)采用并行数据结构，加快运算速度；

(5)设计精确的算法终止规则，提高解的质量和收敛速度.

图1　贪心算法的计算过程Fig.1　The calculation process of greedy algorithm

1.2改进的贪心算法

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择,它对范围相当广泛的许多问题都能产生整体最优解或者整体最优解的近似解.贪心算法求解TSP问题的计算过程如图1所示.

算法访问节点的顺序就是TSP的最终解，但由于算法本身的缺点，最终解并不是最优解.因此，提出采用随机函数产生1~N的正整数M(N为城市的个数)来随机开始第一次访问的节点，改进后的算法思想如下：

(1)首先构造城市距离的对称矩阵A，任意节点到自身的距离为无穷大；

(2)随机函数产生1~N的正整数M(N为城市的个数，1≤M≤N)；

(3)先在第M行找到最小项a[M][j],跳到第j行；

(4)再找到最小值a[j][k],跳到第k行进行查找；

(5)遍历全部节点；

(6)算法结束.

1.3改进的模拟退火算法

基于传统模拟退火算法的不足，提出了改进的模拟退火算法.在改进的模拟退火算法中，采用双阈值iLK,oLK,lam，istd,ostd(iLK为内循环最大迭代次数，oLK为外循环最大迭代次数，lam为温度衰减系数，istd为内循环结束标准，ostd为外循环结束标准)来确保算法的精确性，采用双存储ilen,olen(ilen为内循环保存的目标函数值的个数，olen为外循环保存的目标函数值的个数)来保证算法在迭代过程中不会丢失最优解，采取新的退火方案T=T0exp(-lam(oLK-1)-1/2)，使算法更适应TSP问题的求解，其中T0为初始温度.

1.4贪心模拟退火算法

根据前文的分析，提出了结合贪心算法和模拟退火算法的贪心模拟退火算法，其思想是先采用改进的贪心算法产生初始状态解，然后运用改进的模拟退火算法求解.具体的算法步骤如下：

(1)令i=0,初始化参数T0,iLK,oLK,lam,istd,ostd,ilen,olen；

(2)调用改进的贪心算法产生初始访问序列x(0)；

(3)由x(1)随机扰动产生一个新的候选解x(i+1)；

(4)计算Δf=f(x(i+1))-f(x(i))；

(6)如果Δf≤0，接受新解；否则给出一个服从均匀分布0~1的随机数r，如果exp(-Δf)>r，则接受新解；

(7)i=i+1,如果i≤L，返回到第(3)步；

(8)令i=0，根据温度衰减方案使T变小，T=T0exp(-lam(oLK-1)-1/2)；

(9)如果不满足终止条件，返回到第(3)步，否则终止算法；

(10)当前解为最优解输出.

2仿真实验

采用普通办公用计算机，处理器为InterCorei5 2.67GHz,内存为2G，操作系统为32位Windows7，采用Matlab7.1编程实现.实验数据来自国际通用的TSP实例库TSPLIB，选取3组数据,分别为31cities,70cities和100cities.每组数据均迭代100次，记录每次的TSP实验结果.

表1　31/70/100 cities结果比较

表1中优化比的计算公式为

表示贪心模拟退火算法比传统模拟退火算法有效的比率.

如表1所示，在同样的城市规模中，贪心模拟退火算法比传统的模拟退火算法要好，并且随着组合优化规模的增大，贪心模拟退火算法比传统的模拟退火算法具有更大的优势.图2是100 cities在传统模拟退火算法和贪心模拟退火算法下最优路径的比较.通过比较可以直观地发现贪心模拟退火算法的优势.

图2　100 cities传统SA与贪心模拟退火算法最优路径Fig.2　100 cities the optimal path of traditional SA and greedy simulated annealing algorithm

图3　100 cities传统SA与贪心模拟退火算法收敛曲线Fig.3　100 cities convergence curve of traditionalSA and greedy simulated annealing algorithm

图3是实验数据100 cities在传统的模拟退火算法和改进后的贪心模拟退火算法中的收敛曲线图.通过比较可以看出，改进后的算法在大约40次退火实验后结果就趋于稳定，而传统的算法则需要大约80次的退火实验才会趋于稳定后.通过观察可以发现，改进后的贪心模拟退火算法比传统的模拟退火算法有较快的收敛速度.

3结语

改进的贪心算法和传统的模拟退火算法相结合后提出的贪心模拟退火算法比贪心算法和传统的模拟退火算法更有效.在TSP问题中，贪心模拟退火算法可以得出接近最优解的解.另外,通过3组实验可以推断出贪心模拟退火算法比较适合规模较大的TSP优化组合问题.

参考文献：

[1]兰兆青,白艳萍,李飞.遗传算法解TSP问题的程序设计[J].太原师范学院学报:自然科学版,2008(2):30-32.

[2]Ingber L,Rosen B.Genetic algorithms and very fast simulated annealing:a comparison[J].Mathematical Computer Modeling,1992,16(11):87-100.

[3]卢冰,王梦兰.一种改进蚂蚁算法在TSP问题中的应用[J].科技创业月刊,2010(6):128-129.

[4]王艳春,王新.基于神经网络求解TSP问题的研究[J].齐齐哈尔大学学报,2006(1):65-67.

[5]杜宗宗,刘国栋.基于混合遗传模拟退火算法求解TSP问题[J].计算机工程与应用,2010(29):40-42.

[6]Kirkpatrick S,Gelartt C D,Vecchi M P.Optimization by simulated annealing [J].Science,1983,220(11):650-671.

Solving TSP problem using greedy simulated annealing algorithm

LI Jinxu1，HUANG Yueyue2

(1.DepartmentofInformationandNetwork,ZhengzhouKindergartenTeachers′College,Zhengzhou450001,China;

2.InternationalSchool,YellowRiverInstituteofScienceandTechnology,Zhengzhou450001,China)

Abstract:By analyzing the shortage of the traditional simulated annealing algorithm and the feasible improvement scheme, we proposed a greedy simulated annealing algorithm for solving TSP problem. The new algorithm combines the improved simulated annealing algorithm and the improved greedy algorithm, and improved the quality of the solution of the algorithm. Experimental test results show that the new algorithm has better solution than that of traditional simulated annealing algorithm.

Key words:simulated annealing algorithm; greedy algorithm; TSP; combinatorial optimization

作者简介：李金旭(1986-)，男，河南郑州人，助教，硕士，主要从事人工智能与智能算法方面的研究.

收稿日期：2014-12-02

中图分类号：TP312

文献标志码：A

文章编号：1674-330X(2015)01-0066-04