求解TSP问题的贪婪随机模拟退火算法.doc

求解TSP问题的贪婪随机模拟退火算法
钟一文，蔡荣英
福建农林大学计算机与信息学院，福建福州，350002
摘要：模拟退火算法是一种典型的智能优化算法，它的一个主要缺点是收敛速度慢。针对这一问题，提出了一种基于贪婪随机策略的求解旅行商问题的模拟退火算法，在从当前解的邻域中选择候选解时，根据问题领域的启发式信息，采用贪婪策略从邻域中生成一个候选解列表，再从候选解列表中随机选择一个候选解。仿真结果表明，贪婪随机模拟退火算法明显优于传统的模拟退火算法。
关键词：模拟退火算法；贪婪随机；旅行商问题
中图分类号：TP301 文献标识码：A 文章编号：
A Greedy Random Simulated Annealing Algorithm for Traveling Salesman Problem
ZHONG Yi-wen, CAI Rong-ying
College of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China
Abstract: Simulated Annealing algorithm is a typical intelligent optimization algorithm. One of its main shortages is slow convergence speed. In order to tackle this shortage, a greedy random Simulated Annealing algorithm for Traveling Salesman Problem is presented. In the presented algorithm, based on heuristic information derived from the problem at hand, a candidate list is selected greedily from the neighborhood of current solution. Then candidate solution is selected randomly from the candidate list. Simulated results show that the proposed algorithm can get better result than classical Simulated Annealing algorithm.
Key words: Simulated Annealing algorithm; Greedy random; Traveling Salesman Problem
1 引言
模拟退火（Simulated Annealing, SA）算法是一种典型的智能优化方法，SA算法的思想最早是由Metropolis等[1]提出的，SA算法依据Metropolis准则接受新解，因此，除接受优质解外，还在一定范围内接受劣质解，SA算法在开始时温度t值较大，可以接受较差的劣质解，随着t值的减小，只能接受较好的劣质解，最后在t值趋于零时，就不再接受任何劣质解了，这就使SA算法可以从局部最优的“陷阱”中跳出，从而有可能求得优化问题的全局最优解。SA算法同时还具有简单和通用的特点，因此SA算法在许多领域都得到了很好的应用，比如在VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。但是，尽管从理论上证明了SA算法能收敛到全局最优解，在使用SA算法的过程中也发现，其收敛速度很慢，与此相反，启发式算法通常基于某种贪婪策略，有较快的收敛速度，但易于陷入局部最优解，那么，能否在SA算法中嵌入一定的贪婪策略，在保持其全局寻优的前提下，加快SA算法的收敛速度呢？基于这个思想，针对旅行商问题（Traveling Salesman Problem，TSP），本文研究了在产生下一个解时，根据领域的启发式信息，采用贪婪策略从邻域中生成一个候选解列表，再从候选解列表中随机选择一个候选解，以平衡算法的随机性和贪婪性，提高获取优质解的概率，从而提高SA算法的总体性能，仿真表明，这种策略能明显提高SA算法的性能。
2 求解TSP问题的模拟退火算法
TSP问题是一个典型的NP-困难的组合优化问题。假设有一个推销员必须遍历N个城市，每个城市必须且只能访问一次，最后返回到出发城市，TSP问题就是要找到访问这些城市的顺序，使旅行线路的总长度最短。对一个包含N个城市的TSP问题，可以用一个N×N的二维数组d来存储城市间的距离，其中每个元素d[i][j]表示城市i和j之间的距离，用一个包含N个元素的一维数组s来存储推销员访问城市的顺序，其中每个元素s[i]的值表示第i个访问的城市，求解TSP问题的目标就是要找到某个城市访问顺序s，使其路径长度最小，即最小化路径长度：
（1）
图1是求解TSP问题的基本SA算法，其中函数generate(s)表示从当前解s产生一个候选解，函数tourLenght(s)表示由解s所对应的路径长度。
1 给定初温tk = t0，产生初始解s = s0，令k = 0；
2 当温度tk大于终温tmin时，重复下述操作；
2.1 内循环计数器c = 0;
2.2 当c小于内循环最大迭代次数时，重复下述操作：
2.2.1 产生新的候选解sj = generate(s)；
2.2.2 如果tourLength(sj) < tourLengths)
s = sj；
2.2.3 否则，如果exp[-(tourLength(sj) - tourLengthe(s)) / tk] ≥ random[0,1]
s = sj；
2.2.4 c = c + 1;
2.3 退温tk+1 = decrease(tk); //decrease是退温函数
2.4 k = k + 1;
3 输出算法搜索结果。
图1 基本模拟退火算法的伪代码
Fig.1 The pseudo code of basic Simulated Annealing Algorithm
文献中对求解TSP问题的SA算法的研究多集中在相关参数的设置上，比如对初始温度、终止温度、退温方式、目标函数、邻域结构及其大小的研究等。文献[2]提出的空间锐化SA算法通过对原搜索空间进行某种非线性拉伸操作，强化各局部极值点的差异，使“好的更好，差的更差”，这样，在锐化后的空间中，模拟退火跳出较好局部最小的概率相对减小，因而更易于得到好解；文献[3-5]研究了不同邻域结构的大小对SA算法性能的影响，文献[6-7]研究了不同的邻域结构（不同形式的逆转邻域、插入邻域和交换邻域及它们的混合）对SA算法性能的影响。当确定了邻域结构后，上述文献基本上都是采用等概率的方式从邻域中随机产生下一个候选解，文献[6]提出了一个基于领域知识的启发式方式，其基本思想是在插入邻域中选择插入位置和插入城市时，根据TSP问题中边的信息，使用比例选择策略，优先破坏长的边，优先插入短的边：
在选择插入位置时，使路径中相邻城市之间的距离大的两个城市以较大的概率被选取，在它们之间插入其他城市，即选择位置i为插入点的概率为：
（2）
假设已经选定在位置i插入，选择插入的城市时，使距离城市s[i]近的城市以较大的概率选为下一个访问点，即选择位置j上的城市s[j]的概率为：
（3）
式中dmax是其他城市到城市s[i]的最大距离。
仿真结果表明，上述比例选择策略的使用能有效地提高SA算法的性能[6]，但上述方式存在以下不足：
（1）在选择插入位置时，优先破坏距离大的城市的策略在有些情况下是不合适的，因为各个城市到其他城市的平均距离可能有很大的差别。
（2）这种概率选择方式比较费时，特别是选择插入位置时，每次都得重新生成概率分布表。
（3）在选择插入城市时，公式（3）考虑了从某一城市出发所能到达的所有城市，而实际上，在最佳路径上的边几乎都是较短的边[8]，所以，如果只考虑离这个城市较近的一些城市，则算法可能具有较快的收敛速度，更好的局部求精能力。
3 贪婪随机模拟退火算法
针对比例选择策略的上述不足，本文提出一种基于贪婪随机思想的候选解生成策略。先根据城市之间的距离生成一个二维的排名表rank，其中rank[i][j]表示城市j到城市i的距离在所有到城市i的城市的排名，排名越小，距离越短，即排名为1表示距离最短，排名为2表示距离第二短，依此类推；建立一个二维的近邻城市排序表order，里面的每一个元素order[i][j]的值表示对城市i而言，第j近的城市是order[i][j]，即最近的城市是order[i][1]，次近的城市是order[i][2]，依此类推。在选择插入位置时i，使用锦标赛选择策略，先随机选择2个位置x和y，如果rank[s[(x-1+N)%N]][s[x]]大于rank[s[(y-1+N)%N]][s[y]]，则取i为x，否则，取i为y，即优先破坏排名靠后的边作为插入的位置。假设已经选定在位置i插入，选择插入的城市时，采用贪婪随机策略，假设位置i前一个位置上的城市为c，假设取贪婪列表的长度为M，则取城市order[c][1]、order[c][2]、…、order[c][M]构成候选解列表，再从中随机选择一个城市为要插入的城市。图2是根据上述思想从当前解s产生候选解的generate(s)函数的伪代码。
generate( s )
BEGIN
x = random(N);
y = random(N);
IF rank[s[(x-1+N)%N]][s[x]] > rank[s[(y-1+N)%N]][s[y]] THEN
i x;
ELSE
i = y;
ENDIF
c = s[ ( i-1+N ) % N ]; //c为位置i前一个位置上的城市
j = index(s, order[ c ][ random(M) ];
RETURN insert( s, i, j );
END
图2 generate函数的伪代码
Fig.2 The pseudo code of generate function
图2所示generate(s)函数的伪代码中的random(N)函数用于产生一个1到N之间的随机数，表达式order[ c ][ random(M)]的作用是在离城市c最近的M个城市中随机选择一个城市，函数index(s, order[ c ][ random(M) ]用于查找第二个参数指定的城市在解s中的位置，函数insert( s, i, j )利用插入法从当前解s产生一个新的解，即把位置j上的城市插入到位置i。
文献[6]只是在插入邻域中应用了比例选择策略，而对TSP问题的逆转邻域、插入邻域和交换邻域的研究表明[6]，采用逆转邻域性能最好。可以把比例选择和贪婪随机策略应用到逆转邻域结构中，对逆转邻域，在按上述方式选择好i和j之后，把位置i和j之间的子路径以反方向插入来产生新解，其余不变。
4 算法仿真结果
在Java环境下实现了基本SA算法（Basic Simulated Annealing, BSA）、基于比例选择策略的SA算法（Proportional Simulated Annealing, PSA）和基于贪婪随机策略的SA算法（Greedy Random Simulated Annealing, GRSA），分别在逆转邻域和插入邻域比较它们的性能。参数设置为，初始温度t0=105，终止温度tmin=0.1，退温方式选用指数退温，即tk+1=atk，其中a=0.99，贪婪列表的长度M取为5，为了比较不同的退火过程中算法的性能，内循环迭代次数依次取1、20、40、60、80、100、200、300、…、1000。从通用TSPLIB[9]中选用最佳解是426的eil51问题进行仿真实验，每个算法重复运行100次，结果取平均值，表1是仿真结果。
表1 在eil51问题上BSA、PSA和GRSA的性能比较
Table 1 Performance comparisons of BSA, PSA, and GRSA for eil51 Problem
内循环迭代数
逆转邻域
插入邻域
BSA
PSA
GRSA
BSA
PSA
GRSA
1
709.95
586.37
452.63
792.24
672.75
513.43
20
448.61
445.3
433.52
477.62
460.63
447.36
40
444.66
440.87
431.84
462.0
451.34
442.05
60
443.28
438.96
430.52
455.66
449.65
439.33
80
440.75
438.34
429.51
454.34
447.65
439.61
100
440.39
436.87
429.44
450.86
446.51
437.87
200
437.29
435.31
428.37
444.99
441.08
435.89
300
436.34
433.01
427.65
442.67
439.51
434.33
400
433.87
432.71
427.39
441.91
439.92
432.81
500
434.53
431.95
427.33
439.66
437.1
432.78
600
433.53
431.5
427.09
438.9
436.7
432.05
700
433.17
431.06
426.93
440.07
436.91
431.11
800
433.38
430.49
426.89
437.76
435.82
430.81
900
432.32
429.75
426.85
436.47
435.52
430.91
1000
431.72
429.47
426.86
437.2
435.72
430.84
从表1可以看出，PSA和GRSA算法在各种邻域结构下、在不同的内循环次数下，其结果均优于BSA，特别是在内循环次数越小的情况下，效果越明显，说明PSA和GRSA算法由于使用了启发式信息来指导候选解的产生，能有效地加快SA算法找到优质解的速度。从表中还可以看到，在各种情况下GRSA都优于PSA。而且，GRSA的运行时间尽管比BSA长，但比PSA算法明显短，比如，在内循环迭代次数为100时，BSA、PSA和GRSA的单次运行时间分别是0.139、0.472和0.243秒。

图3 BSA, PSA, and GRSA在逆转邻域中不同内循环次数下的性能比较
Fig.3 Performance comparisons of BSA, PSA, and GRSA in inversion neighborhood with different inner loop times
图3是在逆转邻域结构中，不同内循环迭代次数下平均解的变化曲线，其中横坐标表示内循环的迭代次数（取20到1000），而纵坐标表示解的平均值，从图中可以很明显地看到，在各种不同的内循环迭代情况下，PSA和GRSA算法都优于BSA而GRSA又明显优于PSA算法。
5 结束语
SA算法是一种典型的智能优化算法，尽管在理论上能收敛到全局最优解，但实际收敛速度很慢，所以，提高其收敛速度是应用SA算法时的一个关键。传统的SA算法在从邻域结构中选择候选解时，采用的是随机的等概率方式，本文研究了利用领域的启发式信息、采用贪婪随机策略来指导候选解的产生，从而提高产生优质候选解的概率，以期提高SA算法的总体性能，仿真结果表明，这种贪婪随机策略能有效地提高SA算法的性能。
参考文献（References）：
[1] Metropolis N, Rosenbluth A W, and Rosenbluth M N, et al Equations of state calculations by fast computing machines[J]. Journal of Chemical Physics, 1953,21(6):1087-1092.
[2] 高国华,沈林成,常文森. 求解TSP的空间锐化模拟退火算法[J].自动化学报,1999,25(3):425-428.
GAO Guohua, SHEN Linching, and CHANG Wensen. Using Simulated Annealing Algorithm with Search Space Sharpening to Solve Traveling Salesman Problem[J]. ACTA AUTOMATICA SINICA, 1999, 25(3):425-428.
[3] Cheh, K.M., J.B. Goidberg, and R.G. Askin. A note on the effect of neighbourhood structure in simulated annealing[J]. Computers and Operations Research, 1991,18(6): 537-548.
[4] Goldstein, L. and M. Waterman. Neighborhood size in the simulated annealing algorithm[J]. American Journal of Mathematical and Management Sciences, 1988, 8(3):409-423.
[5] Yao, X. Comparison of different neighbourhood sizes in simulated annealing[A]. Proceedings of the Fourth Australian Conference on Neural Networks[C], 1993, 216-219.
[6] 高尚.求解旅行商问题的模拟退火算法[J].华东船舶工业学院学报.2003,17(3):13-16.
GAO Shan. Solving TSP with Simulated Annealing Algorithm[J]. Journal of East China Ship Building Institute. 2003, 17(3):13-16.
[7] 孙燮华.用模拟退火算法解旅行商问题[J].中国计量学院学报,2005,16(1):66-71.
SUN Xiehua. Solving Traveling Salesman Problem by simulated annealing algorithm[J]. Journal of China JiLian University. 2005, 16(1):66-71.
[8] 钟一文,杨建刚,宁正元.求解TSP问题的离散粒子群优化算法[J].系统工程理论与实践, 2006, 26(6):88-94.
ZHONG Yiwen, YANG Jiangang, and NING Zhengyuan. Discrete Particle Swarm Optimization Algorithm For TSP Problem[J]. System Engineering Theory and Practice. 2006,26(6):88-94.
[9] http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95.