混合SPMD模拟退火算法及其应用  

Hybrid SPMD Simulated Annealing Algorithm and Its Applications

作　　者：都志辉[1] 李三立[1] 吴梦月[2] 李树有[2] 朱静[2] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]清华大学材料科学与工程学院,北京100084

出　　处：《计算机学报》2001年第1期91-98,共8页Chinese Journal of Computers

基　　金：教育部博士后科学基金;清华大学骨干人才支持计划资助

摘　　要：模拟退火算法由于有很好的数学特性——以概率 1收敛于全局最优值 ,再加上其算法本身与特定的问题无关 ,因此被广泛地用于各种组合优化问题 .但是 ,模拟退火算法又具有收敛速度慢 ,执行时间长 ,算法性能与初始值有关及参数敏感等缺点 ,使得它在不少应用中成为一种低效甚至是不可行的算法 .文中提出一种混合 SPMD模拟退火算法 ,在克服经典模拟退火算法内在串行性的同时 ,进一步和下山法结合起来 ,并综合多种优化方法 ,在一定的处理机规模内取得了可扩展的并行效果 ,显著提高了算法的收敛速度 ,克服了算法性能对初始值和参数选择的过分依赖 ,在提高算法性能的同时 ,方便了算法的使用 .该算法已在一个机群系统 THNPSC- 1上得以实现 ,并在材料科学的一个定量电子晶体学研究问题中得到应用 ,降低了该问题的求解时间 ,提高了求解质量 .Simulated Annealing (SA) is a frequently used stochastic algorithm to deal with combinatorial optimization problems and it converges with probability infinitely close to 1. However, this parameter sensitive algorithm causes long execution time which prevents it from being accepted for many real applications. Serial SA method has been discussed not only in pure algorithm research but also in many applications. How to parallelize the SA algorithm and how to improve its performance is what this paper concerns. In the research of complex parallel applications, we find that the features of different calculation phases are quite different. One algorithm can only suit for one special phase. So if only one pure algorithm is used in these applications, the performance is not high. The paper presents a hybrid SPMD (Single Program Multiple Data) algorithm which combines SA with local search algorithm——Downhill. The hybrid method not only keeps the convergence of SA but also improves the convergence speed of SA. Approximate solutions can be found quickly for complex optimization problems and more precise solutions can also be found by employing the same algorithm to fine tune the approximate solutions. SA is an essential serial algorithm, but the SPMD algorithm breaks up the serial bottleneck of SA and in some range its performance scales up with the increase of processors. At the same time, the SPMD algorithm does not require careful choice of control parameters. Cluster computing is a new kind of parallel computing mode and has been used in many fields. It is chosen as our experimental environment not only because it is a typical parallel environment but also because it is available easily. The algorithm has been implemented on a cluster system THNPSC 1. Fives typical multiple maximum functions are used to test the SPMD algorithm. The results show that the algorithm can always find the best values. The application on a quantitative electron crystallography problem shows that the algorithm is robust and it can find

关 键 词：模拟退火算法 SPMD 组合优化 并行算法 计算机 

分 类 号：O242.1[理学—计算数学] TP301.6[理学—数学]