On the Acceleration of Simulated Annealing

The simulated annealing paradigm is a general-purpose stochastic optimization technique that has proven to be an effective tool for approximating globally optimal solutions to many types of NP-hard combinatorial optimization problems. Simulated annealing is based on an analogy with the physical annealing process—a technique in the field of condensed matter physics for obtaining the minimum-energy state of a solid. The paradigm has proven to be especially effective in the field of VLSI design automation. The major drawback of the paradigm is its typically high and sometimes prohibitive computational cost. Accelerating the paradigm has been an active area of research since its introduction in 1983. This dissertation explores two methods of acceleration—a uni-processor approach called two-stage simulated annealing and a multi-processor approach called population-oriented simulated annealing.