Hybrid SPMD Simulated Annealing Algorithm and Its Applications
Du Zhi · Chinese Journal of Computers · 2001
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 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.