An Efficient Simulated Annealing Schedule: Derivation
Jimmy Lam and Jean-Marc Delosme
Report 8816
September 1988
Department of Computer Science, Yale University.
Department of Electrical Engineering, Yale University.
Abstract
The popularity of simulated annealing comes from its ability to find close to optimal solutions for NP-hard combinatorial optimization problems. Unfortunately, current implementations of the method usually require massive computation time. This paper presents a general annealing schedule which speeds up simulated annealing significantly when compared with general schedules available in the literature. The annealing schedule, which lowers the temperature at every step and keeps the system in quasi-equilibrium at all times, is derived from a new quasi-equilibrium criterion. For a given move generation strategy, this schedule is shown to give the minimum final average cost among all schedules that maintain the system in quasi- equilibrium. An alternate form of the schedule is derived that explicitly relates move generation to temperature decrement. This leads to a control method for the move generation strategy that further minimizes the final average cost.