From trose@mailbox.syr.edu Wed Jul 29 14:05:32 1992 Received: from mailbox.syr.edu by spica.npac.syr.edu (4.1/I-1.98K) id AA24026; Wed, 29 Jul 92 14:05:30 EDT From: trose@mailbox.syr.edu (Thomas Rose) Received: from skunk.cns.syr.EDU by mailbox.syr.edu (4.1/CNS) id AA07187; Wed, 29 Jul 92 14:06:24 EDT Received: by skunk.cns.syr.EDU (4.1/Spike-2.0) id AA02181; Wed, 29 Jul 92 14:04:49 EDT Date: Wed, 29 Jul 92 14:04:49 EDT Message-Id: <9207291804.AA02181@skunk.cns.syr.EDU> To: paulc@nova.npac.syr.edu Subject: Rough draft Status: R Dr. Coddington, feel free to make any changes to the following. I'll drop by your office sometime after lunch today (Wed.). Tom 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 the algorithm has been shown to greatly improve the simula- tion of a specific spin model when compared to conventional Monte Carlo tech- niques. 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 simulating the Ising spin glass is then analyzed. 1. INTRODUCTION Frequently in physics, physical systems involving many degrees of freedom arise. To derive properties of such systems using the normal approach of me- chanics would prove impossible because of the many possible configurations. Conventional Monte Carlo techniques employ pseudo-random number generators in order to simulate such systems which are probabilistic or statistical in nature. 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 with many different coexisting con- figurations at finite non-zero temperature. This procedure is shown to greatly improve over other metropolis and cluster methods for simulating the Random Field Ising Model in reference [1]. Because of its recent development, however, the potentials 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 glass. 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 > 0. Spin glass is one such system whose simulation begins by assigning certain values to the microscopic degrees of freedom (atom positions, spin directions). The spin directions 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( -E * B ) where B is proportional to 1/T and E is the systems internal energy for the configuration. For spin glass the equation for E is: >From these simulations one is able to determine the average magnetization of the system, the specific heat of the system, and numerous other observables. For spin glass one starts with an initial configuration and repeats the following steps over and over again: 1) Select one spin for flipping. 2) Compute the energy change resulting from this flip. 3) Calculate the "transition probability" W = exp( (change in E) * B ) for this flip. 4) Generate a random number x beween zero and one. 5) If x < W, flip the spin, otherwise do not flip the spin. 6) Analyze the resulting configuration as desired. Simulated annealing is a useful Monte Carlo technique which is used for sim- ulations similar to this. In annealing, one "heats" up the system to some high temperature and slowly "cools" it, following some predetermined schedule, to the desired temperature. This results in the approximate minimization of the energy of the system. However, a straightforward generalization of the algorithm for the simulation of this system is not possible. This is because at T > 0, 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 effec- tive 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 spin glass includes the following steps which are done after a predetermined number of the above steps: 1) Generate a random number y between zero and one. 2) If y < 5 attempt to decrease the temperature, otherwise, increase the temperature. 3) Accept the temperature change with a probability proportional to the change in temperature. 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 tempera- ture (i.e., outside the array), the current temperature is used. ii) The change in temperature, and hence, the array of temperatures, is made 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 [1]. The above algorithm is implemented on the DECmpp using the MasPar Parallel Application Language. RESULTS, DISCUSSION, CONCLUSION - N/A ACKNOWLEDGEMENTS REFERENCES [1] Marinari, Enzo and Giorgio Parisi, Simulated Tempering: A New Montecarlo Technique, Submitted to Europhyid. Letters, February 20, 1992. ETC.