朱静丽

（英德广播电视大学，广东 英德 513000）

用模拟退火算法求解TSP

朱静丽

（英德广播电视大学，广东 英德 513000）

货郎担问题，即TSP（Travelling Salesman Problem），是一个组合优化问题。具有NPC计算复杂性。本文分析了模拟退火算法模型，研究了用模拟退火算法求解TSP算法的可行性，并给出了用模拟退火算法求解TSP问题的具体实现方法。

模拟退火原理；算法；TSP

一、货郎担问题

货郎担问题，即TSP（Travelling Salesman Problem），也叫旅行商问题，是数学领域中著名问题之一。其一般提法为：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。如图1所示，显然左边的路程要小于右边的路程。

图1 TSP的示意图

货郎担问题（TSP问题）是一个组合优化问题。具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来，并逐一比较，选出最小的路径。虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的。以每秒1亿次的计算速度来估算，如果TSP问题包含20个城市时，求解时间长达350年；如果要处理30个城市，则求解时间更长达1+10e16年。如此长的时间，在实际中完成是不现实的。基于模拟退火算法在处理全局优化、离散变量优化等困难问题中，具有传统优化算法无可比拟的优势。尝试用模拟退火算法求解。

二、模拟退火算法

（一）模拟退火算法原理

模拟退火算法原理来源于固体退火：将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/（kT），其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表（Cooling Schedule）控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

（二）模拟退火算法的模型

模拟退火算法可以分解为解空间、目标函数和初始解三部分。

模拟退火的基本思想:

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

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.如果满足终止条件则输出当前解作为最优解，结束程序。

终止条件通常取为连续若干个新解都没有被接受时终止算法。

7.T逐渐减少，且T-〉0，然后转第2步。

三、模拟退火算法求解TSP

求解TSP的模拟退火算法模型描述如下:

解空间：解空间 S是遍访每个城市恰好一次的所有路经，解可以表示为{w1,w2 ,…, wn}，w1, …, wn是1,2,…,n的一个排列，表明w1城市出发，依次经过w2, …, wn城市，再返回w1城市。初始解可选为（1,…, n） ;

目标函数：目标函数为访问所有城市的路径总长度；要求的最优路径为目标函数为最小值时对应的路径。新路径的产生：随机产生1和n之间的两相异数k和m，不妨假设k〈m，则将原路径

（w1,w2,…,wk,wk+1,…,wm,wm+1,…,wn）

变为新路径：

（w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn）上述变换方法就是将k和m对应的两个城市在路径序列中交换位置,称为2-opt映射。

四、代码实现

UINT SACompution(LPVOID pParam)

以上程序在Windows XP Professional、Visual C++ 6.0、STLport 4.6.2环境下调试完成。模拟退火算法一种新的随机搜索方法，经实验研究，能有效解决组合优化问题，与以往的近似算法相比，模拟退火算法具有使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点。

[1] 刘晓禹，张洪强. 基于模拟退火算法的城市公交线路铺设分析[J]. 交通科技与经济，2010，5.

[2] 朱振方，刘培玉，张洪军，王美方. 基于退火遗传算法的网络信息过滤系统研究[J]. 计算机工程与设计，2009，2.

[3] 徐俊杰. 利用微正则退火算法求解车辆路径问题[J]. 安庆师范学院学报（自然科学版），2009，2 .

Simulated annealing algorithm for TSP

ZHU Jing-li

Traveling salesman problem, that TSP (Travelling Salesman Problem), is a combinatorial optimization problem. Computational complexity with the NPC. This paper analyzes the simulated annealing algorithm model to study the simulated annealing algorithm for TSP of the algorithm, and gives the simulated annealing algorithm for TSP on the specific implementation.

Simulated annealing principles; algorithms; TSP

TP3

A

1008-7427（2011）09-0159-02

2011-07-20