Information Technology Reference
In-Depth Information
2. The Algorithm Selection Problem (ASP)
Many optimization problems can be solved by multiple algorithms, with different
performance for different problem characteristics. Although some algorithms are better than
others on average, there is not a best algorithm for all the possible instances of a given
problem. This phenomenon is most pronounced among algorithms for solving NP-Hard
problems, because runtimes for these algorithms are often highly variable from instance to
instance of a problem (Leyton-Brown et al., 2003). In fact, it has long been recognized that
there is no single algorithm or system that will achieve the best performance in all cases
(Wolpert & Macready, 1997). Instead we are likely to attain better results, on average, across
many different classes of a problem, if we tailor the selection of an algorithm to the
characteristics of the problem instance (Smith-Miles et al., 2009). To address this concern, in
the last decades researches has developed technology to automatically choose an
appropriate optimization algorithm to solve a given instance of a problem, in order to obtain
the best performance.
Recent work has focused on creating algorithm portfolios, which contain a selection of state
of the art algorithms. To solve a particular problem with this portfolio, a pre-processing step
is run where the suitability of each algorithm in the portfolio for the problem at hand is
assessed. This step often involves some kind of machine learning, as the actual performance
of each algorithm on the given, unseen problem is unknown (Kotthoff et al., 2011).
The Algorithm Selection Problem (ASP) was first described by John R. Rice in 1976 (Rice,
1976) he defined this problem as: learning a mapping from feature space to algorithm
performance space, and acknowledged the importance of selecting the right features to
characterize the hardness of problem instances (Smith-Miles & Lopes, 2012). This definition
includes tree important characteristics (Rice, 1976):
a.
Problem Space
: The set of all possible instance of the problem. There are a big number of
independent characteristics that describe the different instances which are important for
the algorithm selection and performance. Some of these characteristics and their
influences on algorithm performance are usually unknown.
b.
Algorithm Space
: The set of all possible algorithms that can be used to solve the problem.
The dimension of this set could be unimaginable, and the influence of the algorithm
characteristics is uncertain.
c.
Performance Measure
: The criteria used to measure the performance of a particular
algorithm for a particular problem and see how difficult to solve (hard) is the instance.
There is considerable uncertainly in the use and interpretation of these measures (e. g.
some prefer fast execution, others effectiveness, others simplicity).
Rice proposed a basic model for this problem, which seeks to predict which algorithm from
a subset of the algorithm space is likely to perform best based on measurable features of a
collection of the problem space: Given a problem subset of the problem space
P
, a subset of
the algorithm space
A
, a mapping from
P
to
A
and the performance space
Y
. The Algorithm
Selection Problem can be formally defined as: for a particular problem instance
p
∈
P
, find
the selection mapping
S
(
p
) into the algorithm space
A
, such that the selected algorithm
a
∈
A
maximizes the performance measure
y
for
y
(
a,p
)
∈
Y
. This basic abstract model is
illustrated in Figure 1 (Rice, 1976; Smith-Miles & Lopes, 2012).
