Information Technology Reference
In-Depth Information
drawn from the task distribution, b) each solver is run many times on each training task,
and c) a model is fit to the outcomes observed in training. In the test phase that follows,
repeatedly, (1) a test task is drawn from the same task distribution, (2) the model predicts
the likely outcomes of each solver, (3) the portfolio selects and runs a solver for some
duration, (4) the run's outcome conditions later predictions, and (5) the process continues
from (2) until a time limit expires.
The models of solver behavior are two latent class models: a multinomial mixture that
captures the basic correlations between solvers, runs, and problem instances, and a mixture
of Dirichlet compound multinomial distributions that also captures the tendency of solver
outcomes to recur. Each model was embedded in a portfolio of diverse SAT solvers and
evaluated on competition benchmarks. Both models support effective problem solving, and
the DCM-based portfolio is competitive with the most prominent modern portfolio method
for SAT (Xu 2009).
4.4 Functions of heuristic rules
Rice introduced the poly-algorithm concept (Rice 1968) in the context of parallel numeric
software. He proposes the use of functions that can select, from a set of algorithms, the best
to solve a given situation. After the Rice work, other researchers have formulated different
functions that are presented in (Li 1997, Brewer 1995). The majority of the proposed
functions are simple heuristic rules about structural features of the parameters of the
instance that is being solved, or about the computational environment. The definition of the
rules requires of the human experience.
The objective of the proposed methodology in (Beck 2004) is to find the best solution to a
new instance, when a total limit time T is given. Firstly, the selection strategies for a set of
algorithms A were formulated and denominated as prediction rules, these are: Selection is
based on the cost of the best solution found by each algorithm; Selection is based on the
change in the cost of the best solutions found at 10 second intervals; Selection is based on the
extrapolation of the current cost and slope to a predicted cost at T.
These rules are applied for the training dataset and the optimal sampling time t* (required
time to select the algorithm with the less solution error) is identified for each of them.
After, when a new instance is given, each prediction rule is utilized to find the algorithm
with the best found solution in a time tp = |A| x t*, and it is executed in the remaining
time
tr
= T - tp. One of the advantages is that the methodology can be applied to different
problems and algorithms. Nevertheless, the new dataset must have similarity with the
training dataset.
4.5 Machine learning
The algorithm selection problem is focused by Lagoudakis and Littam in (Lagoudakis 2000)
as a minimization problem of execution total time, which is solved with a Reinforced
Learning algorithm (RL). Two classical problems were focused: selecting and ordering. A
function that predicts the best algorithm for a new instance using its problem size is
determined by means of training. The learned function permits to combine several recursive
algorithms to improve its performance: the actual problem is divided in subproblems in
