Highest utility first search across multiple levels of stochastic design

Many design problems are solved using multiple levels of abstraction, where a design at one level has combinatorially many children at the next level. A stochastic optimization methods, such as simulated annealing, genetic algorithms and multi-start hill climbing, is often used in such cases to generate the children of a design. This gives rise to a search tree for the overall problem characterized by a large branching factor, objects at different levels that are hard to compare, and a child-generator that is too expensive to run more than a few times at each level. We present the Highest Utility First Search (HUFS) control algorithm for searching such trees. HUFS is based on an estimate we derive for the expected utility of starting the design process from any given design alternative, where utility reflects both the intrinsic value of the final result and the cost in computing resources it will take to get that result. We also present an empirical study applying HUFS to the problem of VLSI module placement, in which HUFS demonstrates significantly better performance than the common `waterfall' control method.