EVALUATION OF SIMULATED TEMPERING 
                         FOR OPTIMIZATION PROBLEMS


                               Thomas Rose

                             Paul Coddington

                              Enzo Marinari


                              
                               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 can be used to simulate such 
systems on a computer.  These simulations are useful for understanding problems
such as the thermal, electronic, and magnetic properties of matter, diffusion, 
percolation, quantum chemistry, and quantum field theory. 


             SIMULATED TEMPERING FOR DISORDERED PHYSICAL SYSTEMS 

     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 certain disordered spin models of
magnetic materials.  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 other disordered systems, such as spin 
glasses.


            SIMULATED TEMPERING FOR GENERAL OPTIMIZATION PROBLEMS

     In addition to the potential benefits offered by simulated tempering for
simulating physical systems, the algorithm might also be applicable to general
optimization problems.  This belief is founded on the relation of simulated 
tempering to the well known Monte Carlo technique called simulated annealing.
Simulated annealing has demonstrated its ability to find approximate solutions
to general optimization problems.  Because of the similarity between these two 
algorithms, it is believed that simulated tempering should do at least as well 
as simulated annealing in general optimization problems.
 

               ADVANTAGES OF THE SIMULATED TEMPERING ALGORITHM

     Simulated tempering is similar to simulated annealing, however whereas in
annealing every temperature change drives the system out of equilibrium, in 
tempering a Metropolis-like update is performed on the temperature while the 
system is kept at equilibrium.  One advantage tempering has over annealing is 
that while the optimal cooling schedule is not known for annealing, with 
tempering, the changes in temperature are at least partly determined by the 
system under investigation.  Also, simulated annealing only finds one local 
minimum which is hoped to approximate the global minimum.  With tempering many
local minima are obtained and the smallest can be chosen as an approximation to
the global minimum. 


                    PARALLELIZATION OF THE ALGORITHM

     The simulated tempering algorithm was implemented on the SIMD-architecture
DECmpp using the MasPar Parallel Application Language (MPL), which is a data-
parallel version of C.  The main computational cost of the simulated tempering
algorithm is the update of the spins, which is done using the standard local 
Metropolis Monte Carlo algorithm.  This is straightforward to parallelize using
domain decomposition.  Since the algorithm is local and regular, perfect load
balancing and good efficiency was achieved.  


                               RESULTS