Information Technology Reference
In-Depth Information
each recursive step, and the most adequate algorithm in size is used for each of them. This
work is extended to backtracking algorithms to SAT problem in (Lagoudakis 2001).
A system (PHYTHIA-II) to select the most appropriated software to solve a scientific
problem is proposed in (Houstis 2002). The user introduces the problem features (operators
of the equation, its domain, values of the variables, etc.) and time requirements and allowed
error. The principal components of PHYTHIA-II are the statistical analysis, pattern
extraction module and inference engine. The first consists in ranking the algorithms
performance data by means of Friedman rank sums (Hollander 1973). The second utilizes
different machine learning methods to extract performance patterns and represent them
with decision and logic rules. The third is the process to correspond the features of a new
problem with the produced rules; the objective is to predict the best algorithm and the most
appropriated parameters to solve the problem.
The METAL research group proposed a method to select the most appropriate classification
algorithm for a set of similar instances (Soares 2003). They used a K-nearest neighborhood
algorithm to identify the group of instances from a historical registry that exhibit similar
features to those of a new instance group. The algorithm performance on instances of
historical registry is known and is used to predict the best algorithms for the new instance
group. The similarity among instances groups is obtained considering three types of
problem features: general, statistical and derived from information theory.
A Bayesian approach is proposed in (Guo, 2004) to construct an algorithm selection
system which is applied to the Sorting and Most Probable Explanation (MPE) problems.
From a set of training instances, their features and the run time of the best algorithm that
solves each instance are utilized to build the Bayesian network. Guo proposed four
representative indexes from the Sorting problem features: the size of the input
permutation and three presortedness measures. For the MPE problem he utilizes general
features of the problem and several statistical indexes of the Bayesian network that
represents the problem.
A methodology for instance based selection of solver's policies that solves instances of the
SAT problem was proposed by (Nikolic 2009). The policies are heuristics that guide the
search process. Different configurations of these policies are solution strategies. The problem
structure of all instances was characterized by indices. The problem instances were grouped
by the values of these indices, forming instances families. All problem instances were solved
by all solution strategies. The best solution strategy for each family is selected. The k-nearest
neighbor algorithm selects the solution strategy for a new input instance. The results of the
performance of the algorithm ARGOSmart, that performs the proposed methodology, were
superior to ARGOSAT algorithm.
5. Approaches to building algorithm selectors
In this chapter we solve ASP with two approaches: meta-learning and hyper-heuristics. The
meta-learning approach is oriented to learning about classification using machine learning
methods; three methods are explored to solve an optimization problem: Discriminant
Analysis (Pérez, 2004), C4.5 and the Self-Organising Neural Network. The hyper-heuristic
approach is oriented to automatically produce an adequate combination of available low-
level heuristics in order to effectively solve a given instance (Burke et al., 2010); a hyper-
