Predictive Search Distributions

Estimation of Distribution Algorithms (EDAs) are a popular approach to learn a probability distribution over the \good" solutions to a combinatorial optimization problem. Here we consider the case where there is a collection of such optimization problems with learned distributions, and where each problem can be characterized by some vector of features. Now we can dene a machine learning problem to predict the distribution of good solutions q(sjx) for a new problem with features x, where s denotes a solution. This predictive distribution is then used to focus the search. We demonstrate the utility of our method on a compiler optimization task where the goal is to nd a sequence of code transformations to make the code run fastest. Results on a set of 12 dierent benchmarks on two distinct architectures show that our approach consistently leads to signicant improvements in performance.