改进新解产生方式及温度函数的模拟退火算法
2015-05-30 22:01彭乔姿卢宇婷林禹攸王颖喆
智能计算机与应用 2015年5期
彭乔姿 卢宇婷 林禹攸 王颖喆
摘要：简单介绍了传统模拟退火算法的流程、算法所涉及的重要参数、当下模拟退火算法改进的主要改进角度以及一种已有的改进算法——加温退火法。提出了一类基于改进新解产生方式及温度函数的模拟退火算法，一共包含四种新的改进算法，命名为：多粒子寻优模拟退火算法、混合温度模拟退火算法、混合多粒子寻优模拟退火算法、加温多粒子寻优模拟退火算法。最后分别将这四种改进算法应用于求解Sobolg函数最小值和碎纸片拼接问题。实验证明改进后的算法是有效的，分别在解的质量以及算法效率上有所提升。关键词：模拟退火算法；新解产生方式；温度函数；Sobolg函数；碎纸片拼接问题
中图分类号：TP18， TP30 文献标识码：A 文章编号：2095-2163（2015）05-
Simulated Annealing Algorithm based on Improving Production of New Solutions and Temperature Function
PENG Qiaozi， LU Yuting， LIN Yuyou， WANG Yingzhe
（School of Mathematics Science， Beijing Normal University， Beijing 100875， China ）
Abstract： The paper simply introduces the traditional simulated annealing algorithm through its process， key parameters， main aspects of improvement of the algorithm at present， and a new improvement named Simulated Annealing Algorithm with Heating Process which was put forward by other scholars. Then the paper puts forward a new type of simulated annealing algorithm based on improving production of new solutions and temperature function， including four improved algorithms which are named Multi-objectives Optimization Simulated Annealing Algorithm， Combined Temperature Simulated Annealing Algorithm， Combined Multi-objectives Optimization Simulated Annealing Algorithm and Multi-objectives Optimization Simulated Annealing Algorithm with Heating Process respectively. At last， the paper applies these four improved algorithms to determine the minimum value of Sobolg function and restore the shredded paper respectively. The experiments demonstrate that the new type of simulated annealing algorithm is effective and show the improvement of both the solutions of those two problems and algorithms efficiency.
Key words： Simulated Annealing Algorithm； Production of New Solutions； Temperature Function； Sobolg Function； Restoration of the Shredded Psaper
0 引 言
模拟退火算法 （Simulated Annealing Algorithm）是一种应用广泛的随机优化算法，最早的思想是由N. Metropolis等人于1953年提出。1983 年，S. Kirkpatrick等成功地将退火思想引入到组合优化领域。具体地，这是基于Monte-Carlo迭代求解策略的一种随机优化算法，能够模拟物理中固体物质的退火过程。模拟退火算法是一种通用的优化算法，理论上具有概率的全局优化性能，其在工程中获得更大发展和普及应用的同时，更在现如今这个大数据的时代背景下，表现了重要而广阔的发展应用空间。但是模拟退火算法也相应存在一些缺点。具体地，其收敛速度较慢、计算时间较长，并且当解决一些问题时在有限时间内却无法得到最优解。
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。
基于此，本文分别对Sobolg函数的最小值求解和碎纸片拼接进行探究，验证改进模拟算法算法功效， Sobolg函数为复杂天气系统中一个重要的实验函数[1]，其形式如下：
（1）
其中， ，
1 传统模拟退火算法
模拟退火算法[2]在给定的控制参数初值下，从随机的可行解出发，持续进行“产生新解—判断—接受/舍弃”的迭代过程，在迭代递减时产生一系列的Markov链，通过计算系统的时间演化过程，逐步逼近问题的最优解。停止准则达到后，根据控制参数衰减函数减小控制参数的值，重复进行上述步骤，就可以在控制参数达到终止时，最终求得组合优化问题的整体最优解。这一搜索方法是结构化、随机化的。求解步骤如下：
（1）初始化：选定初始控制温度和马氏链长度，并在可行解空间中选定一个初始解；
（2）产生新状态：根据控制参数温度衰减函数依次降低控制温度，控制温度每降低一次产生一个随机扰动，得到一个新状态；
（3）产生新解：根据状态接受函数判断是否接受这个新状态作为新解；
（4）输出最优解：根据停止准则判定算法是否终止，若不终止则返回（2）直到满足停止准则输出最优解。
2 模拟退火算法的主要改进设计及加温退火法
虽然模拟退火算法所得解能够依概率收敛到全局最优解[3]，但是其收敛速度比较慢，而且计算时间比较长，这些都在相当程度上降低了该算法的效率，导致模拟退火算法在实际应用中有较大的局限性，因此，不断有学者对传统的模拟退火算法提出一定改进，其目的主要是提高解的质量（解质）以及算法效率。改进设计主要表述为“移动策略”和“冷却进度表”。其中，改进移动策略即为改进新解产生方式，改进冷却进度表即改进冷却进度表中所涉及的主要控制参数：降温函数、初末温和马氏链长度。
加温退火法[3]通过改变初始解的选取方式达到提高解的质量的目的。其算法流程为：对组合优化问题实例的任给的初始解，先令初温T0=0，然后进行若干次试验，当且仅当目标函数值增大时接受其转移，同时令T0按某个增量函数h（T）增加，当试验结束时，以所得的T0值作为控制参数T的初值，并以此时的当前解作为初始解 开始退火。
3 改进算法
为使得算法能保存当前最优解，四种算法都增加了记忆功能，即把当前最优解记忆下来。
3.1 多粒子寻优模拟退火算法
这一改进是基于“移动策略”，目的是在允许时间范围内，提高解质。
将传统模拟退火算法中产生新解时的“一次扰动”求得新解，替换成“n次扰动”，分别计算n次扰动对应状态的函数值，选择其中函数值最小的作为新解。因为当前解的邻域内的每一个点都可以作为新解，假如x*是该邻域内的一个使得目标函数可达极小值的解，按照传统模拟退火算法的流程，可能需要循环i次才能够达到这个解。但如果一次生成n个解择优作为新解的话，达到x*的概率加大，并且循环次数也可以减少。如果马氏链的长度不变的话，生成的解的质量应该会有所提高。
下面通过Sobol g函数的例子来研究生成解个数与解质及运行时间所形成的数值变量关系。
初末温温度比是100：1，温度函数是TK= Ts ，马氏链长度都是200时，分别生成1、2、3、5、7、9个解，重复运行30次，计算平均解质与平均运行时间，结果如表1所示。
从表1可得，解质随生成解个数的增加而呈现提升态势。解质从1到2变化较大，之后解质变化转为很小。运行时间则基本上与生成解的个数成正比。
考虑到解质和运行时间的单位不同，将最小值估计和运行时间作乘积后再作图，结果如图1所示。
由图1可知，生成2个解时解质变化提高最快，时间增加较少，算法效率最高。因此对Sobol g函数发生的改进中，选择生成两个解择优作为新解来进行验证。此外，由于问题不同，该改进中生成新解的个数选择是不同的，但由上述分析可以推测，无论是哪种具体问题，生成新解的个数也不会是越多越好。为使算法运行可得较高的效率，可以选择使解质改变最大、运行时间很长的生成解个数作为改进方案。
一次生成多个解择优会导致程序运行时间增长，这是因为对应改进相当于是加长了马氏链的长度。因此，在给定解的精度后，可以适当缩短马氏链长度，来控制运行时间。
3.2混合温度模拟退火算法
该处是从“冷却进度表”实施改进，目的是缩短运行时间。
冷却进度表中三种温度函数降温过程中变化如图2所示。由图2可知，在温度变化次数k比较小时，变化速度由快到慢的依次是代数式收敛1/k、对数式收敛1/log（k）、指数式收敛0.99k；在温度变化次数较大时，代数式函数1/k和指数式收敛0.99k的变化速度都很快，而对数式收敛1/log（k）的变化速度却非常慢。根据模拟退火的收敛性理论，即温度函数应选取比对数式收敛1/log（k）变化态势更慢的类型，才可以保证算法依概率1收敛到全局最优解。但对数式收敛1/log（k）的算法运行时间过长，具体实际中很难获得使用。为加快算法的运行速度，选择将两种温度函数拼接到一起，前m次温度函数使用， 希望能迅速找到全局最优解所在的邻域，m次之后的温度函数使用 ，以减少算法运行时间为总之，使其能够在一定精度范围内较快地搜索到最优解的估计值。
选择使用降温函数：
（2）
其中，m是预先固定的值。由上面三种温度函数下降图可知，找到log函数的拐点所对应的变化次数作为m。对log函数求导，可得m=15。
3.3 混合多粒子寻优模拟退火算法
在这个算法中，从“移动策略”和“冷却进度表”两方面实行改进，将多粒子寻优模拟退火算法、混合温度模拟退火算法相结合，即降温函数选择混合降温函数，产生新解则更改为产生两个解择优作为新解，由此而达到提高解的质量的显示效果作用。
3.4 加温多粒子寻优模拟退火算法
在这个算法中，从“移动策略”和“冷却进度表”两方面来执行改进，将加温退火法与多粒子寻优模拟退火算法相结合，即先用加温退火法来得到所需的初温，再进行多粒子寻优，达到提高解的质量，进而减少运行时间的作用。
4 将改进算法应用于实例验证算法功效
下面将多粒子寻优模拟退火算法、混合温度模拟退火算法用于求解Sobolg函数最小值和碎纸片拼接问题进行实例验证，将混合多粒子寻优模拟退火算法、加温多粒子寻优模拟退火算法用于求解碎纸片拼接问题进行实例验证。
4.1 应用于求解Sobol g函数最小值
下面分别将传统的模拟退火算法（即改进前的模拟退火算法）、多粒子寻优模拟退火算法及混合温度模拟退火算法用于求解Sobolg函数最小值，并分别将改进后与改进前的算法进行了对比统计，得出算法改进功效。
4.1.1 算法流程
（1）多粒子寻优模拟退火算法
Step 1：给定初温t0、末温tf、马氏链长度L，令温度t=t0。随机生成一个5维的均匀分布随机数作为初始解x0，计算其目标函数值作为当前目标函数值Gc，将初始解记为当前解xc。再令最优解和最优目标函数值xb和Gb分别为xc和Gc，令k=1；
Step 2：令r=1。产生2个5维的正态扰动，进行一定的处理使之加到当前解上不会超出定义域。记这两个解为x1、x2，并计算其对应的目标函数值G1、G2，选择结果中最小的作为新解，记为xn，相应的目标函数值记为Gn；
Step 3：比较Gn和Gc：若Gn
Step 4：若r<=L，重复step 2。若r=L，判断t是否小于tf，若是，则进行step 5；若不是，令t=t0*0.99^k，k=k+1，再回到step 2。
Step 5：输出最优解和最优目标函数值。
（2）混合温度模拟退火算法
将上面算法过程中的Step 2、Step 4修改为以下的Step 2、Step 4：
Step 2：令r=1。产生1个5维的正态扰动，进行一定的处理使之加到当前解上不会超出定义域。记这个新解为xn，并计算目标函数值Gn；
Step 4：若r<=L，重复step 2。若r=L，判断t是否小于tf，若是，则进行step 5；若不是，判断k是否小于15，若是，令t=t0/log（k+1），k=k+1；若不是，则令t=t0*0.99^k，k=k+1，再回到step 2。
4.1.2 运行结果及分析：
（1）多粒子寻优模拟退火算法
固定马氏链长度L=100，末温为1，初温分别为50，100，200，300，500，1 000，重复运行30次，一次产生2个解择优作为新解。
温度函数为TK= 时，改进前和改进后的解质及运行时间如图3、图4所示。
温度函数为TK= 时（由于运行时间关系只呈现两组数据），改进前和改进后的算法所得解的质量和运行时间如表2所示。
解质上，改进后解质比改进前解质精确度提高了10倍，而改进后运行时间则约为改进前运行时间的3倍。
综上，多粒子寻优模拟退火适用于使用的降温函数是TK= 、TK= ，这种温度下降较快、运行时间也不是很长的算法，能够在允许时间范围内得到比传统模拟退火算法更为精确的解，而对于本身下降速度较慢、运行时间很长的TK= 来说，这种改进则有些得不偿失。
（2）混合温度模拟退火算法
固定末温是1，初温50、100、200、300、500、1 000，马氏链长度300，重复30次取平均。改进后解质及运行时间比较如图7、图8所示。（图7中横坐标是初温，纵坐标是最优解）
由图7、图8可知，解质方面，在初温较低时，改进后的解质明显优于改进前TK= 的解质，与 的解质相差不大；在初温较高时，三种函数的解质相差不大。与初末温比是10：1的降温函数TK= 的解质相比，虽比其稍差但却有所接近。运行时间方面，改进后的运行时间比改进前温度函数是 的运行时间普遍要更短，这一结论符合前面的理论分析。在初温较低时，改进后的运行时间则大于改进前TK= 的运行时间；在初温较高时，改进后的运行时间却要低于TK= 的运行时间。而且，改进后的运行时间整体上要少于初末温比是10：1时降温函数TK= 的运行时间。
综上，改进后的算法受初末温比影响小，解质比较稳定，且与解质较稳定的降温函数是 的算法相比，运行时间有所减少。
4.2 应用于求解碎纸片拼接问题
下面分别将传统的模拟退火算法（即改进前的模拟退火算法）、多粒子寻优模拟退火算法、混合温度模拟退火算法、混合多粒子寻优模拟退火算法及加温多粒子寻优模拟退火算法用于求解碎纸片拼接问题，纸片为碎纸机既纵切又横切的情形，中文单面被切为1 119个碎片[4]，最后分别将四种改进算法的实际功效进行了仿真对比。
4.2.1 算法流程
将已分成11类的碎纸片依次编号为1、2、…、11，对应地将用模拟退火算法顺序拼接编号为1至11的碎纸片类。
（1） 碎纸片类拼接传统模拟退火算法步骤
Step 1：依照初始化过程，设置温度初值，随机生成纸片初始位置，根据距离矩阵算出初始位置下距离函数值，选择降温函数是 （C<1，充分接近1）。
Step 2：在温度下，利用均匀分布对纸片位置进行一次随机扰动，得到每张纸片的新位置，运用Metropolis准则决定纸片是否向新位置转移，记录纸片位置转移后的最小距离函数值及其所对应的纸片位置（最优纸片位置）；
Step 3：重复进行step 2，直至达到循环次数满足层内停止准则。记录下过程中的最小距离函数值及其所对应的纸片位置；
Step 4：改变温度TK，重复进行step 2、3，直至温度达到预先设置的终值1，温度达到终值后，由step 2、step 3确定的纸片位置终态的最优纸片位置（即“记忆”）则将是最终拼接结果。
（2） 多粒子寻优模拟退火算法将（1） Step 2中“利用均匀分布对纸片位置进行一次随机扰动”改为“利用均匀分布对该纸片位置进行n次随机扰动，比较n次随机扰动后的距离函数，选取距离函数最小的扰动作为纸片扰动新位置”。
（3） 混合温度模拟退火算法将（1）中温度变化改为“前n次的温度函数为TK= ，之后温度函数为TK= ”。
（4） 加温多粒子寻优模拟退火算法将加温模拟退火算法和多粒子寻优模拟退火算法的改进实现了应用结合。
（5） 混合多粒子寻优温度模拟退火算法将混合温度模拟退火算法和多粒子寻优模拟退火算法的改进实现了应用结合。
4.2.2 运行结果
中文碎纸片横纵拼接，已将属于同一横条的纸片归为一类，进行纸片横向拼接。以下退火算法（除涉及加温的算法外）初温均为100，末温均为1。
混合温度多粒子模拟退火算法：
粒子数为5；前15次降温函数为TK= ，之后降温函数为TK= ；马氏链长度为1 000。 所得解平均需要人工干预1.866 67次；
平均运行时间为111.488 3。
4.2.3 结果分析
由表3可知，多粒子寻优模拟退火算法的解质优于传统模拟退火算法和加温模拟退火算法，但其平均运行时间比后两个算法更长，在获得较好解质的同时，花费了较多的时间。
混合温度模拟退火算法的解质优于传统模拟退火算法及多粒子寻优模拟退火算法，运行时间与传统模拟退火算法相差不大，在以上两个只从一个角度实行改进的算法中，算法呈现的运行时间最短，解质最优。混合温度模拟退火算法前阶段的TK= 的下降速度在k<16时大于TK= ， 后阶段的TK= 的下降速度在k>15时大于TK= ，因此混合模拟退火算法的运行速度更快，从运行结果可知其解质优于传统模拟退火算法。
加温多粒子寻优模拟退火算法与混合温度多粒子模拟退火算法解质相差不大，前者的平均运行时间约为后者的2.4倍，因为前者比后者的降温函数的下降速度要更快。
5 结束语
本文从不同的改进角度提出了多粒子寻优模拟退火算法和混合温度模拟退火算法，在此基础上，结合已有加温退火算法，构造了加温多粒子寻优模拟退火算法与混合温度多粒子寻优模拟退火算法。实例运算结果表明，采用多粒子寻优模拟退火算法可以显著提高求解全局最优化问题的解质，采用混合温度模拟退火算法可以提高求解全局最优化问题的算法效率，加温多粒子寻优模拟退火算法与混合温度多粒子寻优模拟退火算法，均达到算法改进的目的。
另外，通过对比这四种算法的求解结果还得到一个结论：只从一个角度进行改进的算法所得结果明显优于同时从两个角度进行改进的算法，表现为所得解质相差不大但是时间大大减少，因而在综合考虑解质及算法效率，并对算法效率要求较高的情况下，选择只是变化一个角度的改进算法将会更好。
参考文献：
[1] 刘来福，黄海洋，等. 数学建模实验[M]. 北京：北京师范大学出版社，2014.
[2] MISEVICIUS A. A modified Simulated Annealing Algorithm for the quadratic assignment problem[J]. INFORMATICA， 2003， 14（ 4）：497–514.
[3] 康立山，等. 非数值并行算法（第一册）：模拟退火算法[M]. 北京：科学出版社，1994-4：29-30，84-124
[4] 马俊明，赖楚廷，等. 基于文字特征的规则碎纸片自动拼接[J]. 汕头大学学报（自然科学版），2014，29： 4-10.
