改进模拟退火算法求解TSP问题

摘要：对模拟退火算法进行了改进，从不同的初始状态开始搜索来解决TSP问题，并将计算的结果与遗传算法的计算结果进行比较，优于文献[1]中遗传算法的结果。

关键词：TSP；模拟退火；Metropolis准则；二邻域法

中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)15-20ppp-0c

Modified Simulated Annealing Algorithm for TSP

SHENG Guo-hua,CHEN Yu-jin

(People's Liberation Army University of Science & Technology,Nanjing 210007,China)

Abstract: Modify the simulated annealing algorithm .Begin to search for solving TSP from different initial states ,and compares the result with the result of genetic algorithm. We find that the result excels the result of genetic algorithm in the literature[one].

Key words: TSP; Simulated Annealing; Metropolis rule; two neighbourhood method

1 TSP问题描述

TSP问题可描述为：有n个城市，且已知城市i到城市j的距离矩阵D=[dij]n×n，其中，dij≥0，dij=dji，dii=0且对于任意的k，有dik+dkj≥dij(i,j,k=1,2,…n)。一旅行商从其中一个城市出发, 每个城市均经过一次后回到出发地, 要求找出一条最短的路线。这是一个典型的组合优化问题，对n个城市而言, 可能的路径总数为(n-1)!/2。随着城市数n的增大, 可能的路径数将呈指数急剧增长。以n=30为例，如果用每秒计算一亿次的计算机按穷举搜索的方法来求解，需要1.4×1015年，可见用穷举法来求解是不切实际的。

2 模拟退火算法简介

模拟退火算法来源于固体物质降温原理，在高温条件下，粒子将自由运动，在达到稳定状态后，再缓慢的降低其温度，则固体物质最终会形成最低能量的状态。可以将这种思想应用于求解组合优化问题，将组合优化问题解空间中的一个解对应于固体降温过程中的一个状态，将目标函数对应于该状态下的能量。以控制参数T来模拟固体的温度。对于每一个T，进行迭代过程：“解变换产生新解――判别准则――新解的取舍”，采用Metropolis准则4来决定解的取舍，随着温度的降低，该算法有可能从局部极值区域跳出，从而达到全局最优解。

3 模拟退火算法在求解TSP中的应用

3.1 解空间分析及初始解

可以将TSP问题的一个解表示为一个循环排列π=(π1, π2,…πn)，πi表示第i次经过的城市，只有满足πi≠πj(i≠j)的解才是可行解，它表示TSP问题的一条可行路线。所有可行解构成了TSP问题的解空间Ω。

考虑到问题的解决方便，不妨设城市1为起点，增加一个虚拟的城市（序号为n+1）与城市1重合。可得到解空间Ω={(π1, π2,…, πn, πn+1)| ( π2, π3,…, πn)为{2,3,…n}的循环排列，π1=πn+1=1}，初始解可采用产生随机排列得方法来得到。

3.2 解变换产生新解

采用二邻域变换法5来改变相邻的状态来产生新的可行解。任选序号u，v（u

3.3 Metropolis准则4

由Metropolis准则确定的随机接受概率为：

其中T为控制参数，在初始阶段，T取一初值，在每一个T值下，进行足够多次计算，直到达到稳定状态，再缓慢减小T的值（模拟固体物质的降温过程），直到满足停止准则时停止计算。

3.4 目标函数：

3.5 算法步骤：

Step1：随机产生一个初始解；

Step2：采用产生随机数的方法来产生将要交换的两个城市，用二邻域变换法5产生新的路径，即新的可行解。计算两条路径的长度差Δf；

Step3：若满足Metropolis准则4，则将得到的新解作为新的出发点，否则，以原先的解作为出发点，重复Step2―Step3 L次；

Step4：降温，取Tk=Tk-1(k=1,2,…)，转到Step2，直到满足停止准则为止；

Step5：重复Step1――Step4 K次，记录这K个解的最小值及其对应的状态。

4 实例分析

对Oliver的30个城市的TSP问题进行研究。30个城市的位置坐标如下：{(87,7),(91,38),(83,46),(71,44),(64 ,60),(68,69),(83,69),(87,76),(74,78),(71,71),(58,69),(54,62),(51,67),(37,84),(41,94),(2,99),(7,64),(22,60),(25,62),(18,54),(4,50),(13,40),(18,40),(24,42),(25,38),(41,26),(45,21),(44,35),(58,35),(62 ,32)}。散点图如图1所示：

sgh04.tif

由两点间距离公式得到两两距离矩阵。

（1）采用产生随机排列的方法产生一个初始解

（2）解变换产生新解

任选（随机产生）序号u，v（u

如果Δf

（5）控制参数的设置：

降温速率α=0.999999；初始温度：T0=1；结束温度：e=10-50；L=1000n=30000；K=1000；

（6）降温

利用降温速率α进行降温即：T

（7）结束条件

用结束温度e=10-50，判断退火过程是否结束。若T

（8）重复执行（1）――（6）K次，将这K次结果的最小值及最短路径作为该问题的最好解。

计算结果如图2所示：

得到的最优路径为

1-2-3-4-7-8-9-10-6-5-11-12-13-14-15-16-17-19-18-20-21-22-23-24-25-28-26-27-29-30-1

最短路径长为：423.9045。

文献[1]中遗传算法的计算结果为424.86929。本文算法的计算结果优于文献[1]的结果。

5 结束语

本文用改进的模拟退火算法对TSP问题进行了研究，并对Oliver30城市的TSP进行了求解，求得的结果比遗传算法的结果要好，模拟退火算法能够跳出局部极值区域，寻得最优解。

参考文献：

[1] 敖友云,迟洪钦.基于遗传算法求解TSP问题的一种算法[J].计算机数字与工程,2006.

[2] 张波,叶家玮,胡郁葱.模拟退火算法在路径优化问题中的应用[J].中国公路报,2004.

[3] 高海昌,冯博琴,朱利.智能优化算法求解TSP问题[J].控制与决策,2006.

[4] 王凌.智能优化算法及其应用[M].北京：清华大学出版社,2001.

[5] 康立山,谢云.非数值并行算法[M].北京:科学出版社,1994.

收稿日期：2008-03-17

作者简介：盛国华（1984-），男，硕士，主要研究方向：指挥自动化和战场数字化；陈玉金，男，硕士。

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”