Searching Stochastically-Generated Multi-Abstraction-Level Design Spaces

Louis Steinberg

We present a new algorithm called Highest Utility First Search (HUFS) for searching trees characterized by large branching factor, the absence of a heuristic to compare nodes at different levels of the tree, and a child generator that is both expensive to run and stochastic in nature. Such trees arise naturally, for instance, in problems such as microprocessor design which involve candidate designs at several levels of abstraction and which use stochastic optimizers such as genetic algorithms or simulated annealing to generate a candidate at one level from a parent at the previous level. This report explains the HUFS algorithm and presents experimental results demonstrating the advantages of HUFS over alternative methods.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.