*Why do our adaptive approaches seem to work well? What makes the
standard deviation of grade differences a good barometer for detecting
apparent equilibrium?*
From experience, we've seen that running briefly at high temperatures
and longer at lower temperatures produces good results, and this is
sensible because, equilibrium is approached more quickly at
high temperatures. The overall structure of the solution is
shaped at high temperatures, while at low temperatures the fine
details of the solution are resolved [EFC98]. After many moves,
approaching equilibrium, we want to cool the temperature, making it
more difficult to make a bad move.

The standard deviation indicates the spread in the grade changes of the moves being attempted or accepted. Since one standard deviation includes about of all the grade changes, larger standard deviations indicate motion, while smaller ones reflect similar grade changes, perhaps an indication of `settling'. In the attempt-based scheme, which includes the zero grade differences in its history and calculations, a zero standard deviation could also be an indication of settling.

The only cooling schedule that can potentially `reheat' the
temperature is **sa4**. The temperature is directly proportional to
the average standard deviations of the changes in cost. Since the
standard deviation can be larger or smaller, the temperature change is
non-monotonic. Our approach is similar to the RFC method
described in [EFC98], ``Reheating is done when the temperature
drops below the phase transition (the point of maximum specific heat)
and there has been no decrease in cost for a specified number of
iterations,... Reheating increases the temperature above the phase
transition to produce enough of a change in the configuration to allow
it to explore other minima when the temperature is again reduced.''
Although we borrowed the notion of a relationship between *specific heat*^{} and temperature, we use the square root of the
variance of cost changes as a basis for setting the temperature. Due
to the reheating possibilities, running times for **sa4** are less
predictable than with the other two dynamic schemes as seen in Figures
3.1 through 3.3.