Stochastic combinatorial optimization techniques, such as simulated annealing and genetic algorithms, have become increasingly important in design automation as the size of design problems have grown and the design objectives have become increasingly complex. However, stochastic algorithms are, often slow since a large number of random design perturbations are required to achieve an acceptable result-they have no built-in "intelligence". In this paper, it is shown that statistical learning techniques can improve the quality of results and reduce the number of expensive cost-function evaluations for stochastic optimization for a particular solution quality. In particular, simulated annealing was selected as a representative stochastic optimization approach and a two-dimensional cell-based layout placement problem was used to evaluate the utility of such a learning-based approach. In this paper, we used regression to learn the properties of the solution space and tested the trained algorithm on a number of examples to demonstrate the improvement gained. A general response model is constructed by learning from the annealing of benchmark circuits. This model is then used in the trained simulated annealing, which returns significantly better annealing quality than the untrained algorithm for the same number of moves in the solution space. The annealing quality improvement was 15%-43% for the set of examples used in training and 7%-21% when the trained algorithm was applied to new examples.

Although becoming increasingly important, stochastic algorithms are often slow since a large number of random design perturbations are required to achieve an acceptable result-they have no built-in "intelligence". In this work, we used regression to learn the swap evaluation function while simulated annealing is applied to 2D standard-cell placement problem. The learned evaluation function is then applied to the trained simulated annealing algorithm (TSA). The annealing quality improvement of TSA was 15%/spl sim/43% for the set of examples used in learning and 7%/spl sim/21% for new examples. With the same amount of CPU time, TSA could improve the annealing quality by up to 28% for some benchmark circuits we tested. In addition the use of the evaluation function successfully predicted the effect of the windowed sampling technique and derived the informally accepted advantages of windowing from the test set automatically.