Information Technology Reference
In-Depth Information
Fig. 1. The Algorithm Selection Problem (ASP)
The Figure 2 shows the dimensions of ASP and allows see a higher level of abstraction
scope. There are three dimensions: 1) in the
x
-axis expresses a set of algorithms of solution
s
,
t
,
w
,
y
,
z
, 2)
z
-axis shows a set of instances of the problem
a, b, c, d
, and a new instance
e
to solve, 3) in the
y
-axis the set of values of the results of applying the algorithms to each of
the instances is represented by vertical lines. As shown in figure, to solve the instance
a
and
b
the algorithms have different performances, it is noteworthy that no algorithm is superior
to others in solving all instances. Moreover, as shown in figure the algorithm
s
has a
different performance by solving each of the instances. Finally the problem to be solved is to
select for the new instance
e
the algorithm that will solve better.
Fig. 2. Dimensions of algorithm selection problem
As we can see in the definition of the Algorithm Selection Problem there are three principal
aspects that must be tackled in order to solve the problem:
a.
The
selection of the set features of the problem
that might be indicative of the performance
of the algorithms.
b.
The
selection of the set of algorithms
that together allow to solve the largest number of
instances of the problem with the highest performance.
c.
The
selection of an efficient mapping mechanism
that permits to select the best algorithm to
maximize the performance measure.
Some studies have been focused in construct a suitable set of features that adequately
measure the relative difficulty of the instances of the problem (Smith-Miles et al., 2009;
Messelis et al., 2009; Madani et al., 2009; Quiroz, 2009; Smith-Miles & Lopes, 2012).
Generally there are two main approaches used to characterize the instances: the first is to
