EVALUATION OF SIMULATED TEMPERING FOR OPTIMIZATION PROBLEMS Thomas Rose Paul Coddington Enzo Marinari Abstract The application of massively parallel computers in simulating disordered physical systems and in the search for global minima of discrete optimization problems is addressed. Simulated tempering is a new algorithm which is presented as an alternative to the Monte Carlo procedure known as simulated annealing. A sequential version of this algorithm has been shown to greatly improve the simulation of a specific spin model when compared to conventional Monte Carlo techniques. A parallel version of the algorithm is implemented on the DECmpp using the MasPar Parallel Application Language. The performance of the parallel version of the algorithm for finding the ground state of an Ising spin glass is then analyzed. 1. INTRODUCTION Frequently in physics, systems involving many degrees of freedom arise. To derive properties of such systems using the normal approaches of classical mechanics would prove impossible because of the complexity of the system, so in many cases statistical mechanics is used to give a probabilistic description of the physical system. Monte Carlo techniques employing pseudo-random number generators can be used to simulate such systems which are probabilistic or statistical in nature [1]. These simulations are useful for describing the thermal, electronic, and magnetic properties of matter, metallic alloys, diffusion, percolation, quantum chemistry, field theory, etc. Simulated tempering is a new Monte Carlo technique which has been proposed for effectively simulating physical systems which have different coexisting phases at some non-zero temperature. This procedure has been shown to greatly improve over other Monte Carlo methods for simulating the Random Field Ising Model [2]. Because of its recent development, however, the potential of this algorithm have not yet been fully investigated. It is believed that simulated tempering might overcome the difficulties encountered by conventional Monte Carlo techniques in simulating spin glasses and other disordered systems. ** GENERAL OPTIMIZATION PROBLEMS, SIM ANNEAL. ** 2. FORMULATION OF SIMULATED TEMPERING ALGORITHM Models in which the many degrees of freedom are located on a lattice and interact locally are frequently used to simulate typical physical systems. In statistical thermodynamics the state of the system is characterized by some temperature T. The spin glass is one such system whose simulation begins by assigning certain values to the microscopic degrees of freedom (atom positions, electron spins). In this case the possible spin values are called "spin up" and "spin down" and are assigned values of +1 and -1, respectively. All possible configurations of the system contribute to the thermal average at non-zero temperature and are weighted according to the Boltzmann factor exp( -B * E ), where B is proportional to 1/T and E is the internal energy for the configuration. For spin glass the equation for E is: E = - sum_ J_{i,j} s_i s_j , where s_i and s_j are the spins, and J_{i,j} denotes the interaction between them. From these simulations one is able to determine the average magnetization of the system, the average energy and specific heat of the system, and numerous other quantities which are experimentally observable. For Monte Carlo simulation of the spin glass using the standard Metropolis algorithm [3], one starts with an initial configuration of spins and repeats the following steps over and over again: 1) Select one spin to flip (i.e. change from "up" to "down", or vice versa). 2) Compute the energy change resulting from this flip. 3) Calculate the "transition probability" W = exp( - B * (change in E) ) for this flip. 4) Generate a random number x beween zero and one. 5) If x < W, flip the spin, otherwise leave it unchanged. 6) Analyze the resulting configuration as desired. Simulated annealing is a useful Monte Carlo technique which is used for simulations similar to this. In annealing, one "heats" up the system to some high temperature and slowly "cools" it, following some predetermined schedule, to a low temperature. This is done for the same reason that annealing is used in manufacturing steel and other metals, which is that "quenching" the system (i.e. cooling it very rapidly) results in a metastable configuration of the system, whereas slow cooling results in the approximate minimization of the energy, and consequently a more stable configuration. A straightforward generalization of simulated annealing for a general problem is not possible. This is because we are often interesting in simulating systems at non-zero temperature, where it is not the energy of the system which must be minimized but the free energy. Simulated tempering is similar to simulated annealing but offers an effective way to minimize free energy. The difference between tempering and annealing is that where every change in temperature in annealing drives the system out of equilibrium, tempering consists of changing the temperature while remaining at equilibrium. The complete simulated tempering algorithm for simulating a spin glass includes the following steps which are done after a predetermined number of Metropolis iterations: 1) Generate a random number y between zero and one. 2) If y < 0.5 attempt to decrease the temperature, otherwise, attempt to increase the temperature. 3) Accept the temperature change with a "transition probability" proportional to exp( - (change in B) * E ). Some footnotes are necessary to further clarify the above three steps: i) The different temperatures are stored in an array with the temperature whose observables are desired typically being the median value. When the temperature to be updated is an extreme value, there is only one possible temperature change. In this case, if the random number produced in step 1 would result in moving to a non-existent temperature (i.e., outside the array), the current temperature is used. ii) The amount by which the temperatures are changed, and hence, the values in array of temperatures, is determined before the actual execution of the code. This choice is made such that the acceptance of a temperature change is neither too high nor too low. This choice is dependent on the system being simulated and the temperature under investigation. For a discussion on effectively choosing the changes in temperature see ref. [2]. 3. USING SIMULATED TEMPERING FOR OPTIMIZATION Simulated annealing was originally used to find the ground state of a spin glass, which is a hard (NP-complete) optimization problem. It was later realised that this method could be applied to a general optimization problem, by simply replacing the energy of the system by the cost function to be minimized, and introducing a fictitious temperature parameter [4]. This has proven to be a very effective optimization technique for many difficult optimization problems. One problem with simulated annealing is that the optimal cooling schedule is not known, and must be determined by trial and error. With simulated tempering, the changes in temperature are at least partly determined by the system, with a Metropolis-like update. Also, in simulated annealing, there is only one cooling step, which finds a single local minimum, which is hoped to be close to the global minimum. With simulated tempering the system is constantly being heated and cooled, so many local minima are obtained, and the smallest one can be chosen as an approximation to the global minimum. It is therefore likely that simulated tempering will do at least as well as simulated annealing in general optimization problems. To check this possibility, simulated tempering was used to find the ground state of a spin glass. This corresponds to setting one of the temperatures in the array to be T = 0. There are still some free parameters in this problem, such as the number of possible temperatures and their values, and the number of Metropolis sweeps performed at each temperature, and methods for choosing these parameters also need to be investigated, as well as the performance of tempering compared to annealing. 4. IMPLEMENTATION OF THE ALGORITHM ON A PARALLEL COMPUTER The above algorithm is implemented on the DECmpp using the MasPar Parallel Application Language (MPL), a parallel version of C. * Description of the DECmpp, the parallel program, etc. to follow. * RESULTS, DISCUSSION, CONCLUSION - to be added later. ACKNOWLEDGEMENTS REFERENCES [1] Refs on Monte Carlo methods. [2] E. Marinari and G. Parisi, "Simulated Tempering: A New Montecarlo Technique", submitted to Europhys. Lett., February 1992. [3] N. Metropolis et al., J. Chem. Phys. 21, 1087 (1953). [4] Refs on Simulated annealing.