next up previous

4.1.3 Annealing Schedule     continued...

Decrementing the Temperature

The simplest and most common temperature decrement rule is:

where is constant close to, but smaller than, 1. This exponential cooling scheme (ECS) was first proposed Kirkpatrick et al. [39] with . Randelman and Grest [54] compared this strategy with a linear cooling scheme (LCS) in which T is reduced every L trials:

They found the reductions achieved using the two schemes to be comparable, and also noted that the final value of f was, in general, improved with slower cooling rates, at the expense, of course, of greater computational effort. Finally, they observed that the algorithm performance depended more on the cooling rate than on the individual values of and L. Obviously, care must be taken to avoid negative temperatures when using the LCS.

Many researchers have proposed more elaborate annealing schedules, most of which are in some respect adaptive, using statistical measures of the algorithm's current performance to modify its control parameters. These are well reviewed by van Laarhoven and Aarts [42].