An efficient simulated annealing schedule
J. Lam · 1988
The popularity of simulated annealing comes from its ability to find close to optimal solutions for NP- hard combinatorial optimization problems. Unfortunately, the method has a major drawback: its massive requirement of computation time. In this dissertation, we present an efficient annealing schedule which speeds up simulated annealing by a factor of up to twenty-four when compared with general schedules currently available in the literature. The efficient annealing schedule, which lowers the temperature at every step and keeps the system in quasi-equilibrium at all times, is derived from a new quasiequilibrium criterion. For a given move generation strategy and a given number of steps, this schedule is shown to give the minimum final average cost among all schedules that maintain the system in quasi-equilibrium. Furthermore, with the introduction of two models, we derive an alternate form of this schedule that relates move generation to temperature decrement. At every step, the move generation is controlled to minimize the response time of the system to a change