摘要：模拟退火算法是一种能应用到求最小值问题或连续更新的学习过程（随机或决定性的）。在此过程中，每一步更新过程的长度都与相应的参数成正比，这些参数扮演着温度的角色。标准模拟退火算法仅进行串行优化，其效率很难提高。因此，考虑引入多种群群体优化机制构造并行算法，并对接受准则进行讨论。
关键词：模拟退火；并行计算MPI
中图分类号：TP311文献标识码： A文章编号：1009-3044(2008)25-1523-02
The Research on Parallel Algorithm of Simulation Annealing
WANG Wei
(Mathematic and Information Science College Gansu Lianhe University, Lanzhou 730000, China)
Abstract: Simulation Annealing is a technique which can be applied to any minimization or learning process based on successive update steps (either random or deterministic) where the update step length is proportional to an arbitrarily set parameter which can play the role of a temperature. Simulation annealing only use serial optimize method, it"s difficult to improve efficiency. So, we try to use multi-colony optimize mechanism to form parallel algorithm, and discussed accept rule.
Key words: simulation annealing; parallel compute; MPI
1 引言
模拟退火算法是从某一较高初温开始，采用具有概率突跳特性的接受准则在解空间中进行随机搜索，随着温度的下降重复抽样，整个过程直到各温度下的抽样稳定，最终得到问题的全局最优解。其实质结构为内外两层循环。外层循环控制温度的下降，内部的循环则在当前温度下重复抽样，直到抽样稳定为止。标准模拟退火算法仅对一个解进行串行优化，其效率很难提高。因此，考虑引入多种群群体优化机制，构造出并行模拟退火算法PSA[1]，以提高算法的使用效率。
2 模拟退火算法
在实际的应用中，由计算机随机的产生一组解，计算其目标函数值的方差作为初始温度[2]。温度更新函数Ti+1=λTi,λ∈(0,1)，为使温度下降不至过快，λ取值一般接近于1。基本流程图的描述[3]如图1所示。
3 并行策略及算法描述
3.1 并行的策略
在PSA中，首先初始化过程随机产生k个规模为M的进化种群，并计算种群中每个解的目标函数值，将每个种群中的最优解保存后，状态产生函数在每个解的领域内产生kM个候选解，并计算候选解的目标函数值。若候选解的目标函数值大于当前的解，则取而代之，不则根据接受准则判断是否接受。这样形成了新一代种群。若k个新种群中有优于历史最优解的个体则保留此个体。随后继续重复抽样过程直到当前温度下的抽样稳定后进行退温操作，当温度低于某个终止温度时算法结束。再从K个种群最优解中选出一个最优解作为最终得到的全局最优解。
3.2 算法描述
初始化：产生k个规模为M的种群
并行计算每个初始解的目标函数值并保留各种群的最优解
While (T>Tc)//Tc是循环终止的温度值
{ While(抽样过程未达到稳定)
{ For(i=1;i<=k M;i++)
{
在当前解的邻域内产生一个候选解；
计算候选解的目标函数并根据接受准则判断是否接受
}
判断各种群中是否出现历史最优解，若有则保留之
判断此温度下是否达到抽样稳定；稳定则跳出本循环
}
退温操作；
判断当前温度值是否等于或低于Tc，若是则跳出本循环
}
在k个历史最优解中选出一个最优的解；
输出结果，算法结束
4 算法讨论
4.1 接受准则选取
若准则接收采取最优解，则浪费大量的处理器时间，难以提高加速比。若准则选取最早通过的解，则可能得到更好的加速比，但是不能保证解的质量，而且很可能不如串行算法的解。因此，最好能够寻找一种既能保持解的质量又能提高时间效率的接受准则。
我们提出一种最快结束准则，即最快结束Metropolis循环的处理器给其它运行中的处理器发出停止运行信号，其它处理接收到信号后并不马上停止运行，而是等待正在处理的局部解的过程结束之后才停止。这样所以处理器结束之后都会得到一个解，设计一个进程用来比较各个处理器得到的解，根据接受最优解准则，接受一个最优解。将此最优解保存在共享存储器中，并发送给所有的处理器。很明显这种方法不但可以得到满意的加速比而且能够很好的改善解的质量。
4.2 变量与模型扰动的选择
传统的算法容易放弃在退火过程中找到的很好的解，而最终找到的解不一定比中间最优解好[4]，因此在退火过程中寻求一个记忆功能的全局变量非常有意义，不改变接受准则，但可以较快收敛过程。
采用文献[5]中的方法产生新状态，即依赖于温度的似Cauchy方法，其特点是：在高温情况下进行大范围的搜索，在低温时仅在模型附近进行搜索，因此，其易于迅速跳出局部极值，加快了收敛速度。
4.3 温度更新
采用的控制温度衰减函数为：Ti+1=λTi,λ∈(0,1) 退火过程是慢速降温，允许的时间重新分布，达到温度的状态，因此符合金属的降温规律。
5 结论
此算法采用的并行策略，各处理器这间可以通过共享存储器互相影响或改变，是一种完全异步的并行策略，具有很好的灵活性，能够很好的发挥每个处理器的处理能力，其编程采用MPI与C语言相结合的方试。进一步可以将粗粒度与细粒度的并行算法相结合，得到混合型的并行模拟退火算法，以提高算法的灵活性。
参考文献：
[1] 李树有，都志辉，吴梦月. 模拟退火算法的并行实现及应用[J]. 物理学报，2001,50(7):24-27.
[2] 谢云.模拟退火算法的原理与实现[J]. 高等学校计算数学学报，1999,(3):212-216.
[3] 康立山，谢云.非数值并行算法—模拟退火算法[M]. 北京：科学出版社，2000.
[4] 王华秋，基于模拟退火的并行粒子群优化研究[J]. 控制与决策,2005,(5):500-504.
[5] Ingber L. Very fast simulated reannealing[J]. Mathematical and Computer Modeling, 1989,12(8):967-980.