Optimal annealing schedules using simulated tempering

P.D. Coddington, G.C. Fox, E. Marinari†, C.-H. Wu

Northeast Parallel Architectures Center, Syracuse University, 111 College Place, Syracuse, NY 13244, U.S.A.

T. Rose

Department of Computer Science, University of Texas of the Permian Basin, Odessa, TX ????, U.S.A.

M. Shore

Department of Computer Science, Florida State University, Tallahassee, FL ????, U.S.A.

July 13, 1993

We introduce a novel approach to the application of simulated annealing to global optimization problems. Our method is based on the related technique of simulated tempering, which ensures that the system remains in thermodynamic equilibrium throughout the annealing procedure, thereby guaranteeing that the method probabilistically finds the optimum solution. This method also uses an improved adaptive annealing schedule, which is generally much faster than the logarithmic annealing schedule which guarantees optimality for standard simulated annealing, and we show that it can be as fast as the more commonly used exponential annealing schedule.

† Permanent Address: Dipartimento di Fisica, Università di Roma Tor Vergata, Via E. Carnevale, 00173 Roma, Italy.

I. INTRODUCTION

Simulated annealing is a popular and effective method for tackling difficult global optimization problems [3–5]. The main reasons for its popularity are that it is simple, it can be applied to very general optimization problems, and it has been shown to probabilistically find the optimum solution [5, 6].

Simulated annealing is based on the ideas and techniques of statistical mechanics [7]. The cost function to be minimized is identified with the energy function of a thermodynamic system, a parameter analogous to temperature is introduced, and at each temperature the system configuration is changed using a Monte Carlo procedure [2], so that the energy of the system approaches an equilibrium Gibbs distribution [7]. The temperature parameter is gradually lowered until the system reaches zero temperature, for which equilibrium is the state of minimum energy (the ground state), that is, the solution of the optimization problem. This method is analogous to the annealing of a metal, the process whereby the metal is heated to high temperature, and then cooled very slowly so that it crystallizes into a strong, stable formation with few defects. This is opposed to quenching, where the metal is cooled very quickly and will generally be in a local minimum of the energy which has many more defects and is not as robust.

The main problem with simulated annealing is that every time the temperature is decreased, the system is driven out of equilibrium. In order to guarantee that the system is still in (or near) equilibrium by the time zero temperature is reached, the temperature must be decreased very slowly (logarithmically), which means that this technique can be extremely CPU intensive and time consuming. This has led to the use of similar techniques which have been called simulated quenching [5], which use a faster (exponential) annealing but do not guarantee an optimum solution. In many cases this approach works extremely well, finding solutions which are close to optimal.

However there is a trade-off here, since increasing the rate of annealing will reduce the time taken but will generally result in poorer solutions. In many cases ad hoc or trial-and-error methods are used to find a good annealing schedule, which governs how rapidly the temperature is reduced.

Many methods have been proposed for creating adaptive annealing schedules, which are determined dynamically using information on the statistical mechanics of the system which can be measured at run-time [9–14]. These methods generally work better than predetermined exponential schedules, since they allow the temperature to be reduced as rapidly as possible while still keeping the system “close” to equilibrium. However it has not been proven that these methods will generate an optimal solution.

Recently a new Monte Carlo technique was introduced that is similar to simulated annealing, but extends it so that Monte Carlo methods are used for both aspects of annealing – changing the system configuration and changing the temperature – in such a way that the system is always in equilibrium [8]. Since in this case the temperature becomes a dynamic variable which can be increased or decreased, this method is called simulated tempering, in analogy to the tempering of metals, where a metal is strengthened by repeated heating and cooling cycles.

The idea of using simulated annealing for general optimization problems was based on its use in Monte Carlo simulations of statistical mechanics problems which involve finding the ground states of simple models of magnetism, such as the Ising Spin Glass [16]. This model has many states which have local minima of the energy which are close to the global minimum, so that finding the ground state is a hard global optimization problem. In most statistical mechanics problems the regions of interest, such as phase transitions, are at non-zero temperature, where it is the free energy (a combination of energy and entropy) which is minimized [7]. Simulated tempering has been shown to be very effective at finding the equilibrium behavior of the Random Field Ising Model, a model with similar properties (frustration and disorder) to the Ising Spin Glass, but which has a phase transition at non-zero temperature [8].

Here we introduce a novel approach to solving global optimization problems which combines the techniques of simulated annealing and simulated tempering. The basic idea is that of simulated annealing, however the temperature is decreased probabilistically, using the Monte Carlo approach of simulated tempering, so that the system remains in thermodynamic equilibrium throughout the annealing procedure, thus guaranteeing that this method can find an optimum solution. However the annealing schedule will generally be much faster than true simulated annealing, and we show for some test problems that it can be as fast as simulated quenching.

We show that this method incorporates adaptive annealing in a natural and “symbiotic” way. Adaptive techniques can be used to determine the parameters (such as the appropriate temperature changes) required for efficient simulated tempering, and tempering can be used to improve on standard adaptive annealing schedules which are generally hampered by large statistical errors in the run-time data required to dynamically determine the schedule. We believe that simulated tempering can be used to determine a near-optimal schedule for simulated annealing which probabilistically guarantees finding the solution to a global optimization problem.

We present a brief overview of simulated annealing in section II and simulated tempering in section III. In section IV we show how tempering can be applied to simulated annealing, and section V shows how this method can be improved by incorporating an adaptive annealing schedule. We present our results for the Ising Spin Glass and Traveling Salesman problems in section VI, and then discuss possible variations and improvements to the algorithm in section VII.

II. SIMULATED ANNEALING

Background to annealing.

III. SIMULATED TEMPERING

Background to tempering.

IV. ANNEALING USING SIMULATED TEMPERING

Simple method we are currently doing (as implemented by Wu) of annealing first to find energies, g’s, etc, then repeating the annealing but using tempering to stay in equilibrium.

Can we prove that tempering allows us to use an exponential schedule in general and stay in equilibrium? Or maybe we need to have a logarithmic part near a phase transition?? How about the adaptive schedule of Salamon et al.?? Can we relate the tempering schedule to the Geman and Geman proof?

V. AN ADAPTIVE ANNEALING SCHEDULE USING SIMULATED TEMPERING

Background to previous attempts to do adaptive annealing schedules.

1) How we do it without tempering.

2) How we do it with tempering. How adaptive schedules relate naturally to tempering, e.g. Salamon et al. schedule looks very much like Enzo’s result for choosing the change in temperature.

VI. RESULTS A. The Ising Spin Glass B. The Traveling Salesman Problem

VII. FURTHER OPTIMIZATION BY SIMULATED TEMPERING

Outline the idea that once we have a good temperature schedule and parameters, we can now run full tempering on it to continue exploring many local minima without having to waste time running at high temperatures, setting up the schedule, etc. We can even dynamically improve the schedule by adjusting the parameters so that the scceptances for changing temperature are close to \frac{1}{2}. Reference the next paper [18].

VIII. CONCLUSIONS

We have done some really excellent work and gotten some truly amazing results.

ACKNOWLEDGMENTS

Work supported in part by the Center for Research on Parallel Computation with NSF cooperative agreement No. CCR-9120008, and by Department of Energy grants DE-FG03-85ER25009 and DE-AC03-81ER40050. T. Rose and M. Shore were sponsored by the NSF Research Experience for Undergraduates Program in High-Performance Computing conducted by the Northeast Parallel Architectures Center at Syracuse University, funded by NSF Grant CDA-9200577, Syracuse University, and the GE Foundation Faculty for the Future Program.

Anything else???

REFERENCES

[1] N. Metropolis et al., J. Chem. Phys. 21, 1087 (1953).

[2] K. Binder ed., Monte Carlo Methods in Statistical Physics, (Springer-Verlag, Berlin, 1986); K. Binder and D.W. Heermann, Monte Carlo Simulation in Statistical Physics, (Springer-Verlag, Berlin, 1988); H. Gould and J. Tobochnik, An Introduction to Computer Simulation Methods, Vol. 2, (Addison-Wesley, Reading, Mass., 1988).

[3] M. Pincus, Oper. Res. 18, 1225 (1970); S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, Science 220, 671 (1983).

[4] P.J.M. van Laarhoven and E.H.L. Aarts, Simulated Annealing: Theory and Applications, (D. Reidel, Dordrecht, the Netherlands, 1987).

[5] L. Ingber, “Simulated annealing: Practice versus theory”, to be published in Statistics and Computing, 1993.

[6] S. Geman and D. Geman, IEEE Trans. Patt. Anal. Mac. Int. 6, 721 (1984).

[7] Some good stat mech books???

[8] E. Marinari and G. Parisi, Europhys. Lett. 19, 451 (1992);

[9] R. Otten and L. van Ginneken, in IEEE Proceedings of the International Conference on Computer Design (Port Chester, New York, 1984).

[10] F. Romeo, A. Sangiovanni-Vincentelli and C. Sechen, in IEEE Proceedings of the International Conference on Computer Design (Port Chester, New York, 1984).

[11] J. Lam and J.-M. Delosme, in IEEE Proceedings of the International Conference on Computer Design (1986).

[12] S. Rees and R.C. Ball, J. Phys. A 20, 1239 (1987).

[13] P. Salamon et al., Comp. Phys. Comm. 49, 423 (1988); J.D. Nulton and P. Salamon, Phys. Rev. A 37, 1351 (1988); B. Andresen et al., J. Phys. 49, 1485 (1988).

[14] B. Hajek,

[15] A.D. Sokal, in Computer Simulation Studies in Condensed Matter Physics: Recent Developments, eds. D.P. Landau et al. (Springer-Verlag, Berlin-Heidelberg, 1988); A.D. Sokal, in Proc. of the International Conference on Lattice Field Theory, Tallahassee, October 1990, Nucl. Phys. B (Proc. Suppl.) 20, 55 (1991).

[16] K. Binder and A.P. Young, Rev. Mod. Phys. 58, 801 (1986); D. Chowdhury, Spin Glasses and Other Frustrated Systems, (Princeton University Press, Princeton, NJ, 1986); M. Mezard and G. Parisi, Spin Glass Theory and Beyond, (World Scientific, Singapore, 1987).

[17] M.B. Priestley, Spectral Analysis and Time Series, (Academic Press, London, 1981).

[18] P.D. Coddington, G.C. Fox, E. Marinari, and C.-H. Wu, “Optimization by simulated tempering”, in preparation.

THINGS WE NEED TO DO:

1. See if tempering works for an exponential temperature schedule on a large system (256^{2}).

2. Compare the relaxation of the minimum energy for the exponential schedule with and without tempering, and for different exponents α.

3. Get a good adaptive schedule working.

4. Compare the relaxation of the minimum energy for the adaptive schedule with and without tempering.

5. Try it on the TSP, and compare with other annealing methods and results.

6. A rigorous proof that tempering guarantees (probabilistically) finding the optimal solution.