Discussion: Adaptive Schedules

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 $60\%$ 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.

download thesis