Best-so-far vs. where-you-are: New perspectives on simulatedannealing for CAD

摘要

The simulated annealing (SA) algorithm has been applied to everyndifficult optimization problem in VLSI (very large scale integration)nCAD. Existing SA implementations use monotone decreasing, or cooling,ntemperature schedules motivated by the algorithm's proof of optimalitynas well as by an analogy with statistical thermodynamics. This paperngives strong evidence that challenges the correctness of using suchnschedules. Specifically, the theoretical framework under which monotonencooling schedules is proved optimal fails to capture the practicalnapplication of simulated annealing. In practice, the algorithm runs forna finite rather than infinite amount of time; and the algorithm returnsnthe best solution visited during the entire run ("best-so-far") rathernthan the last solution visited ("where-you-are"). For small instances ofnclassic VLSI CAD problems, the authors determine annealing schedulesnthat are optimal in terms of the expected quality of the best-so-farnsolution. These optimal schedules do not decrease monotonically, but arenin fact either periodic or warming. (When the goal is to optimize thencost of the where-you-are solution, they confirm the traditional wisdomnof cooling.) The results open up many new research directions,nparticularly how to choose annealing temperatures dynamically tonoptimize the quality of the finite time, best-so-far solution