Convergence and finite-time behavior of Simulated Annealing.

Simulated Annealing, proposed by Kirkpatrick, is a randomized algorithm for finding globally optimum, least-cost, configurations in large-scale, NP complete problems in which the cost function may have many local minima. At the m(th) step of the algorithm, first a new configuration is generated randomly from the neighbors of the current configurations, then it is accepted with probability 1 if its cost is less than before, with probability e(-delta (c)/T(m)) if its cost is greater than before. T(m), called the "temperature", is a controlling parameter which changes with m from high initial values to low final values according to a "cooling schedule". Simulated Annealing has been applied with encouraging results to VLSI cell placement and routing problems, to several problems arising in automated design and also to the traveling salesman problem.