Information Technology Reference
In-Depth Information
identify problem dependent features based on domain knowledge of what makes a
particular instance challenging or easy to solve; the second is a more general set of features
derived from landscape analysis (Schiavinotto & Stützle, 2007; Czogalla & Fink, 2009). To
define the set of features that describe the characteristics of the instances is a difficult task
that requires expert domain knowledge of the problem. The indices of characterization
should be carefully chosen, so as to permit a correct discrimination of the difficulty of the
instances to explain the algorithms performance. There is little that will be learned via a
knowledge discovery process if the features selected to characterize the instances do not
have any differentiation power (Smith-Miles et al., 2009).
On the other hand, portfolio creation and algorithm selection has received a lot of attention
in areas that deal with solving computationally hard problems (Leyton-Brown et al., 2003;
O'Mahony et al., 2008). The current state of the art is such that often there are many
algorithms and systems for solving the same kind of problem; each with its own
performance on a particular problem. Machine learning is an established method of
addressing ASP (Lobjois & Lemâitre, 1998; Fink, 1998). Given the performance of each
algorithm on a set of training problems, we try to predict the performance on unseen
problems (Kotthoff et al., 2011). There have been many studies in the area of algorithm
performance prediction, which is strongly related to algorithm selection in the sense that
supervised learning or regression models are used to predict the performance ranking of a
set of algorithms, given a set of features of the instances (Smith-Miles & Lopes, 2012).
In the selection of the efficient mapping mechanism a challenging research goal is to design
a run-time system that can repeatedly execute a program, learning over time to make
decisions that maximize the performance measure. Since the right decisions may depend on
the problem size and parameters, the machine characteristics and load, the data distribution,
and other uncertain factors, this can be quite challenging. Some works treats algorithms in a
black-box manner: each time a single algorithm is selected and applied to the given instance
then a regression analysis or machine learning techniques are used to build a predictive
model of the performance of the algorithms given the features of the instances (Lobjois &
Lemâitre, 1998; Fink, 1998; Leyton-Brown et al., 2003; Ali & Smith, 2006). Other works focus
on dynamic selection of algorithm components while the instance is being solved. In that
sense, each instance is solved by a mixture of algorithms formed dynamically at run-time
(Lagoudakis & Littman, 2000; Samulowitz & Memisevic, 2007; Streeter et al., 2007). The use
of efficient mapping mechanism in intelligent systems is described in the next section.
3. Applications of algorithm selection to real world and theorists problems
The principles applied to ASP can be used in a wide range of applications in the real world
and theoretical. Generally an application that solves a real problem is an extended version of
parameters and constraints in another application that solves a theoretical problem. The
nature of the algorithm selection problem is dynamic because it must incorporate new
knowledge periodically, in order to preserve the efficacy of selection strategies. This section
describes some applications to real-world complex problems, such as knowledge discovery
and data mining, bioinformatics and Web services. It also describes some applications to
solve complex theoretical problems; some examples are NP-hard problems, also called
combinatorial optimization problems.
