An Efficient Simulated Annealing Schedule
Jimmy Lam
Report 8818
September 1988
Department of Computer Science, 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, 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 quasi-equilibrium 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 of temperature, leading to the largest decrement in average cost while satisfying the quasi-equilibrium criterion. Most of the practical applications of simulated annealing have been in complicated problem domains, where algorithms either did not exist or performed poorly. To assess the performance of simulated annealing as a general method for solving combinatorial optimization problems, we also compare the method with efficient heuristics on well-studied problems: the traveling salesman problem and the graph partition problem. For high quality solutions and for problems with a small number of close to optimal solutions, our test results indicate that simulated annealing out-performs the heuristics by Lin and Kernighan and by Karp for the traveling salesman problem, and multiple executions of the heuristic by Fiduccia and Mattheyses for the graph partition problem.