Information Technology Reference
In-Depth Information
automated approach for constructing per-instance algorithm portfolios for SAT that use so-
called empirical hardness models to choose among their constituent solvers. This approach
takes as input a distribution of problem instances and a set of component solvers, and
constructs a portfolio optimizing a given objective function (such as mean runtime, percent
of instances solved, or score in a competition). The algorithm selection approach is based on
the idea of building an approximate runtime predictor, which can be seen as a heuristic
approximation to a perfect oracle. Specifically, they use machine learning techniques to
build an empirical hardness model, a computationally inexpensive predictor of an
algorithm's runtime on a given problem instance based on features of the instance and the
algorithm's past performance. By modeling several algorithms and, at runtime, choosing the
algorithm predicted to have the best performance; empirical hardness models can serve as
the basis for an algorithm portfolio that solves the algorithm selection problem
automatically.
3.8 Vehicle routing problem
In (Ruiz-Vanoye et al., 2008) the main contribution of this paper is to propose statistical
complexity indicators applied to the Vehicle Routing Problem with Time Windows
(VRPTW) instances in order that it allows to select appropriately the algorithm that better
solves a VRPTW instance. In order to verify the proposed indicators, they used the
discriminant analysis contained in SPSS software, such as a machine learning method to
find the relation between the characteristics of the problem and the performance of
algorithms (Perez et al., 2004), as well as the execution of 3 variants of the genetic algorithms
and the random search algorithm. The results obtained in this work showed a good
percentage of prediction taking into account that this based on statistical techniques and not
on data-mining techniques. By means of the experimentation, authors conclude that it is
possible to create indicators applied to VRPTW that help appropriately to predict the
algorithm that better solves the instances of the VRPTW.
4. Related work on automatic algorithm selection
In this section some examples of related works of the reviewed literature are classified by
Methods or methodologies utilized for establishing the relation between the problems and
algorithms, and solve the algorithm selection problem. 2.1. Solution Environments, where
the algorithm selection problem is boarded, are described in section 2.2.
4.1 Simple statistical tests
The most common method to compare experimentally algorithms consists in the
complementary use of a set of simple well-known statistical tests: The Sign, Wilcoxon and
Friedman tests, among others. The tests are based on the determination of the differences in
the average performance, which is observed experimentally: if the differences among the
algorithms are significant statistically, the algorithm with the best results is considered as
superior (Lawler 1985). Reeves comments that a heuristic with good averaged performance,
but with high dispersion, has a very high risk to show a poor or low performance in many
instances (Reeves 1993). He suggests as alternative to formulate for each algorithm, a utility
function adjusted to a gamma distribution, whose parameters permit to compare the
heuristics on a range of risk value.
Search WWH ::




Custom Search