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

模拟退火算法由于有很好的数学特性－以概率1收敛于全局最优值，再加上其算法本身与特定的问题无关，因此被广泛地用于各种组合优化问题。但是，模拟退火算法又具有收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等特点，使得它在不少应用中成为一种低效甚至是不可行的算法。文中提出一种混合SPMD模拟退火算法，在克服经典模拟退火算法内在串行性的同时，进一步和下山法结合起来，并综合多种优化方法，在一定的处理机规模内取得了可扩展和并行效果，显著提高了算法的收敛速度，克服了算法性能对初始值和参数选择的过分依赖，在提高算法性能的同时，方便了算法的使用。该算法已在一个机群系统THNPSC－1上得以实现，并在材料科学的一个定量电子晶体学研究问题中得到应用，降低了该问题的求解时间，提高了求解质量。

Hybrid SPMD Simulated Annealing Algorithm and Its Applications

Simulated Annealing (SA) is a frequently used stochasticalgorithm 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 high quality solution with high speed. The conclusion is that SA can be parallelized with high performance and for complex optimization problems, different methods can be combines together and in different phases, and different method can be used to speed up the optimization procedure.