24 A. Elyasaf et al.
(which takes the heuristic function with the maximal value). However, when we do
not need to guarantee optimality or when we do not use only admissible heuristics,
a good solution can be found in a more efficient way.
1.4 Hyper Heuristics
Within combinatorial optimization, the term hyper-heuristics was first used in 2000
(Cowling et al. 2000 ) to describe heuristics to choose heuristics. This definition of
hyper-heuristics was expanded later (Burke et al. 2010 ) to refer to an automated
methodology for selecting or generating heuristics to solve hard computational
search problems. In the process of hyper-heuristics learning, heuristics and domain
knowledge are used as building blocks. These heuristics can be of high level, usually
complex and memory-consuming (e.g., landmarks and pattern databases), or low-
level domain knowledge and heuristics that are usually intuitive and straightforward
to implement and compute.
Hyper-heuristics have been applied in many research fields, among them:
- Classical planning (Yoon et al. 2008 ; Fawcett et al. 2011 ; Hoffmann and Nebel
2001 ). - Classical NP-Complete domains, e.g., personnel scheduling (Burke et al. 2003 ),
traveling salesman (Oltean 2005 ), and vehicle routing (Garrido and Rojas 2010 ). - Classical AI domains and puzzles, e.g., the Rush Hour puzzle (Hauptman et al.
2009 ), the game of FreeCell (Elyasaf et al. 2012 ), and the Tile Puzzle (Arfaee
et al. 2010 ; Samadi et al. 2008 ).
The growing research interest in techniques for automating the design of heuristic
search methods motivates the search for automatic systems for generating hyper-
heuristics.
1.5 Our Approach: Learning Hyper Heuristics for the Task
of Mining RNA Sequence-Structure Motifs
In this paper, we present a novel way for mining RNA sequence-structure motifs.
We translate the problem into a search graph and devise 97 heuristics for this
domain. Next, we use these heuristics as building blocks for learning hyper
heuristics using HH-Evolver—an evolutionary algorithm system designed for this
type of learning.
This is still work in progress and as yet we have no results to report. However,
given the interest in the methodology and its previous success in other domains we
are hopeful that these shall be forthcoming soon.
The contributions of this work are as follows: