Jeremy De Bonet, Charles Isbell, Paul Viola
In many optimization problems, the structure of solutions reflects complex relationships between the different input parameters. For example, experience may tell us that certain parameters are closely related and should not be explored independently. Similarly, ex(cid:173) perience may establish that a subset of parameters must take on particular values. Any search of the cost landscape should take advantage of these relationships. We present MIMIC, a framework in which we analyze the global structure of the optimization land(cid:173) scape. A novel and efficient algorithm for the estimation of this structure is derived. We use knowledge of this structure to guide a randomized search through the solution space and, in turn, to re(cid:173) fine our estimate ofthe structure. Our technique obtains significant speed gains over other randomized optimization procedures.