Generation of Near-Optimal Solutions Using ILP-Guided Sampling
  Our interest in this paper is in optimisation problems that are intractable
to solve by direct numerical optimisation, but nevertheless have significant
amounts of relevant domain-specific knowledge. The category of heuristic search
techniques known as estimation of distribution algorithms (EDAs) seek to
incrementally sample from probability distributions in which optimal (or
near-optimal) solutions have increasingly higher probabilities. Can we use
domain knowledge to assist the estimation of these distributions? To answer
this in the affirmative, we need: (a)a general-purpose technique for the
incorporation of domain knowledge when constructing models for optimal values;
and (b)a way of using these models to generate new data samples. Here we
investigate a combination of the use of Inductive Logic Programming (ILP) for
(a), and standard logic-programming machinery to generate new samples for (b).
Specifically, on each iteration of distribution estimation, an ILP engine is
used to construct a model for good solutions. The resulting theory is then used
to guide the generation of new data instances, which are now restricted to
those derivable using the ILP model in conjunction with the background
knowledge). We demonstrate the approach on two optimisation problems
(predicting optimal depth-of-win for the KRK endgame, and job-shop scheduling).
Our results are promising: (a)On each iteration of distribution estimation,
samples obtained with an ILP theory have a substantially greater proportion of
good solutions than samples without a theory; and (b)On termination of
distribution estimation, samples obtained with an ILP theory contain more
near-optimal samples than samples without a theory. Taken together, these
results suggest that the use of ILP-constructed theories could be a useful
technique for incorporating complex domain-knowledge into estimation
distribution procedures.
