论文部分内容阅读
摘 要： 旅行售货员问题（Traveling salesman problem）是计算机算法中的一个经典的难解问题，已被证明是一个NP-C（Nondeterministic Polynomial-Completeness）问题，其计算复杂度O（n！），无法找到一个多项式算法解决此类问题。本文利用最优化理论中的模拟退火法，简述了TSP问题的近似算法。
关键词： 旅行售货员问题 NP-C 近似算法 模拟退火法 遗传算法
1.旅行售货员问题（Traveling salesman problem）
旅行售货员问题（TSP）或称为货郎担问题，可描述为：设有n个城市及表示城市i到城市j的距离D=|d■|，其中d■>0，d■=d■，并有d■ d■≥d■，且d■=0（i，j=1，2，3，…，n），一个货郎从一个城市出发，不重复地遍历所有城市并回到起点，求一条路程最短的路径。
这个问题已被证明是一个NP-C（Nondeterministic Polynomial-Completeness）问题，其计算复杂度为O（n！），目前还不能找出一个多项式算法解决此类问题，但解决此类问题有较大的现实意义。例如：在网络通信中求解路由问题时，可用节点间的路径长度代表网络节点间的通信代价，而求解一条代价最小路由回路即可转化为TSP问题的求解。
下面将简述TSP问题的两种不同近似算法：模拟退火算法、遗传算法。
2.模拟退火算法
KIRKPATRICK等于1983年首先提出模拟退火算法。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/（kT），其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表（Cooling Schedule）控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
2.1模拟退火算法的模型
模拟退火算法可以分解为解空间、目标函数和初始解三部分。
模拟退火的基本思想：（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步。
2.2在TSP问题中的应用
2.2.1解空间与初始解
将TSP的一个解表示为一个循环排列π=（π■，π■，…，π■），也可表示为：π■→π■→…π■的一条路径，必须满足π■≠π■（i≠j的解才是可行解），π■（1≤i≤n）是该路径中第i个经过的城市，所有的可行解的集合构成解空间S。在TSP问题中解空间S为{1，2，…，n}的循环排列，其中每一循环排列表示遍访n个城市的一条回路，并约定π■=π■，初始解定为{1，2，…，n}。
2.2.2目标函数
f（π）=min■d■ （1）
式中：■d■为访问所有城市的路径长度。
2.2.3新解的产生
采用二邻域法这样一种改进的相邻状态变换方法。如下图所示，设（s，f）是讨论问题的一个实例，而n■是一个二变换领域结构，则二变换n■（p，q）可看成是城市p与q间路径的反向接入。
图1 路径变换
变换后的新路径是π■…π■π■…π■π■π■…π■（u 2.2.4随机移动准则
采用METROPOLIS准则，由随机移动接受概率
p■（i？圯j）=1 f（j）≤f（i）exp[■]f（j）>f（i） （2）
上式中：t为控制参数，确定是否接受从当前解i到新解j的转移。计算开始时t取较大值（与固体的熔解温度相对应），在进行足够多的转移后，缓慢减小t值（与“徐徐”降温相对应），如此重复，直至满足某个停止准则时计算终止。
2.2.5算法描述
在本算法中，采用随机数发生器来交换两城市访问次序的方法产生新解，冷却进度表的衰减函数设为α，MAPKOB链的长度取为城市数n的100倍。城市坐标初始化按照前面的方法产生初始回路，并计算总路径长度。
（1）采用二变换法更改初始路径，并得到一条新路径，计算更改后总路径与初始路径的长度差△f；
（2）如果满足METROPOLIS准则，则更换路径的行走方式，否则重复过程（1）；
（3）取衰减函数α，随着t■=αt■（k=1，2，3，…，n）而降温，并转向（1）；
（4）当满足停止准则而采用某一t值时，接受新解次数以小于10n为准。当次数大于该值时，则执行降温过程，重新执行退火过程。 在程序中，随机数发生器确定之后，需要经过多次实际选取合适温度计划表中的各个参数，包括控制参数t及其衰减函数α，对应MAPKOB链的长度本程序选择如下：
（1）控制参数t=0.5；
（2）衰减函数α=0.95；
（3）MAPKOB链的长度L■=100n（n表示城市数）.
根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：
Procedure TSPSA：
begin
init-of-T；{T为初始温度}
S={1，……，n}；{S为初始值}
termination=false；
while termination=false
begin
for i=1 to L do
begin generate（S′form S）；{从当前回路S产生新回路S′}
Δt：=f（S′））-f（S）；{f（S）为路径总长}
IF（Δt<0） OR （EXP（-Δt/T）>Random-of-[0，1]）
S=S′；
IF the-halt-condition-is-TRUE THEN
termination=true；
End；
T_lower；
End；
End
3.结语
模拟退火算法在解决TSP问题中显示了与一般常用算法不同的优越性，具有思路清晰、使用灵活的特点。模拟退火算法可以在较短时间内求得更优近似解，而且允许任意选取初始路径和随机数序列，故减少了算法求解路径的前期工作量。随着METEOPOLIS规则的引入，使算法在解决问题时不再完全依赖初始路径，并保证了最终路径在二邻域的最优。
参考文献：
[1]Michael R.Garey，David S.Johnson COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP-Completeness W.H.FREEMAN AND COMPANY，1979.
[2]高尚.基于Matlab遗传算法优化工具箱的优化计算.微型电脑应用，2002.
[3]康立山，谢云，尤矢勇，等.模拟退火算法[M].北京：科学出版社，1994：50-97.
文章授江苏省职业教育教学改革研究课题ZYB56资助。
关键词： 旅行售货员问题 NP-C 近似算法 模拟退火法 遗传算法
1.旅行售货员问题（Traveling salesman problem）
旅行售货员问题（TSP）或称为货郎担问题，可描述为：设有n个城市及表示城市i到城市j的距离D=|d■|，其中d■>0，d■=d■，并有d■ d■≥d■，且d■=0（i，j=1，2，3，…，n），一个货郎从一个城市出发，不重复地遍历所有城市并回到起点，求一条路程最短的路径。
这个问题已被证明是一个NP-C（Nondeterministic Polynomial-Completeness）问题，其计算复杂度为O（n！），目前还不能找出一个多项式算法解决此类问题，但解决此类问题有较大的现实意义。例如：在网络通信中求解路由问题时，可用节点间的路径长度代表网络节点间的通信代价，而求解一条代价最小路由回路即可转化为TSP问题的求解。
下面将简述TSP问题的两种不同近似算法：模拟退火算法、遗传算法。
2.模拟退火算法
KIRKPATRICK等于1983年首先提出模拟退火算法。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/（kT），其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表（Cooling Schedule）控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
2.1模拟退火算法的模型
模拟退火算法可以分解为解空间、目标函数和初始解三部分。
模拟退火的基本思想：（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步。
2.2在TSP问题中的应用
2.2.1解空间与初始解
将TSP的一个解表示为一个循环排列π=（π■，π■，…，π■），也可表示为：π■→π■→…π■的一条路径，必须满足π■≠π■（i≠j的解才是可行解），π■（1≤i≤n）是该路径中第i个经过的城市，所有的可行解的集合构成解空间S。在TSP问题中解空间S为{1，2，…，n}的循环排列，其中每一循环排列表示遍访n个城市的一条回路，并约定π■=π■，初始解定为{1，2，…，n}。
2.2.2目标函数
f（π）=min■d■ （1）
式中：■d■为访问所有城市的路径长度。
2.2.3新解的产生
采用二邻域法这样一种改进的相邻状态变换方法。如下图所示，设（s，f）是讨论问题的一个实例，而n■是一个二变换领域结构，则二变换n■（p，q）可看成是城市p与q间路径的反向接入。
图1 路径变换
变换后的新路径是π■…π■π■…π■π■π■…π■（u
采用METROPOLIS准则，由随机移动接受概率
p■（i？圯j）=1 f（j）≤f（i）exp[■]f（j）>f（i） （2）
上式中：t为控制参数，确定是否接受从当前解i到新解j的转移。计算开始时t取较大值（与固体的熔解温度相对应），在进行足够多的转移后，缓慢减小t值（与“徐徐”降温相对应），如此重复，直至满足某个停止准则时计算终止。
2.2.5算法描述
在本算法中，采用随机数发生器来交换两城市访问次序的方法产生新解，冷却进度表的衰减函数设为α，MAPKOB链的长度取为城市数n的100倍。城市坐标初始化按照前面的方法产生初始回路，并计算总路径长度。
（1）采用二变换法更改初始路径，并得到一条新路径，计算更改后总路径与初始路径的长度差△f；
（2）如果满足METROPOLIS准则，则更换路径的行走方式，否则重复过程（1）；
（3）取衰减函数α，随着t■=αt■（k=1，2，3，…，n）而降温，并转向（1）；
（4）当满足停止准则而采用某一t值时，接受新解次数以小于10n为准。当次数大于该值时，则执行降温过程，重新执行退火过程。 在程序中，随机数发生器确定之后，需要经过多次实际选取合适温度计划表中的各个参数，包括控制参数t及其衰减函数α，对应MAPKOB链的长度本程序选择如下：
（1）控制参数t=0.5；
（2）衰减函数α=0.95；
（3）MAPKOB链的长度L■=100n（n表示城市数）.
根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：
Procedure TSPSA：
begin
init-of-T；{T为初始温度}
S={1，……，n}；{S为初始值}
termination=false；
while termination=false
begin
for i=1 to L do
begin generate（S′form S）；{从当前回路S产生新回路S′}
Δt：=f（S′））-f（S）；{f（S）为路径总长}
IF（Δt<0） OR （EXP（-Δt/T）>Random-of-[0，1]）
S=S′；
IF the-halt-condition-is-TRUE THEN
termination=true；
End；
T_lower；
End；
End
3.结语
模拟退火算法在解决TSP问题中显示了与一般常用算法不同的优越性，具有思路清晰、使用灵活的特点。模拟退火算法可以在较短时间内求得更优近似解，而且允许任意选取初始路径和随机数序列，故减少了算法求解路径的前期工作量。随着METEOPOLIS规则的引入，使算法在解决问题时不再完全依赖初始路径，并保证了最终路径在二邻域的最优。
参考文献：
[1]Michael R.Garey，David S.Johnson COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP-Completeness W.H.FREEMAN AND COMPANY，1979.
[2]高尚.基于Matlab遗传算法优化工具箱的优化计算.微型电脑应用，2002.
[3]康立山，谢云，尤矢勇，等.模拟退火算法[M].北京：科学出版社，1994：50-97.
文章授江苏省职业教育教学改革研究课题ZYB56资助。