IEEE Computational Intelligence Magazine - May 2018 - 32

User-Defined

Calculated

Problem State

Hyper-Heuristic

Best
Solution
Selector

Actions
Features

0.1
0.5
0.8

0.3
0.2
0.9

0.7
0.2
0.5

1
0
2

Features

Distance Calculation

Hyper-Heuristic

Rules

Selector

Fobj
Instances

Action

(a)

0.4

0.7

0.8

(b)

FigurE 1 Overview of the hyper-heuristic model (a) and its inner workings (b). In this framework, the problem state is a vector that characterizes the instance being solved in its current stage. The hyper-heuristic contains a set of rules where the condition is represented also by a vector
and their action corresponds, in this case, to specific heuristics.

model represents the problem by a set of features. These can be
as simple as the size of the problem, or as complex as a relation
between different values of each problem.
It is worth mentioning that the hyper-heuristic model used
in this work closely resembles Learning Classifier Systems (LCS).
Similarities focus on the way rules are generated and how they
are applied based on the problem features. In fact, there are some
works for selection hyper-heuristics that deepen into the way
LCS can generate or be used as hyper-heuristics [19], [20].
As can be seen in Fig. 1 (left), the user provides four elements. The first one is the set of instances that will be solved.
The second one is an objective function for measuring the
quality of the solution. The remaining ones are the set of features and solvers. Using these information, the model randomly
selects a subset of instances for training itself. For a given selector, the hyper-heuristic selects the first instance and calculates
its features, FT. With this starting point, it calculates the Euclidean distance to each rule, and applies the action (i.e., the heuristic) of the closest one. This process is depicted in Fig. 1
(right). After an action, the problem state changes. The process
is repeated until the instance is solved. At this point, the hyperheuristic moves to the next instance and the process continues
until finishing all of them.
As mentioned before, the model used in this work has the
ability to train itself. Here, this means an iterative procedure,
where a messy genetic algorithm evolves a population of selectors. To do so, the process described above is carried out for
each selector, and the objective function defined by the user
guides the evolution. In this work, we used a steady-state configuration with a population size of 20, a crossover rate of 1.0
and a mutation rate of 0.1. Furthermore, we allowed the algorithm to run for 100 cycles (i.e., generations).
1) an Illustrative Example
Aiming to better clarify how selection hyper-heuristics work,
we now present a simple, but useful, example. Imagine a prob-

IEEE ComputatIonal IntEllIgEnCE magazInE | may 2018

lem where you have a set of items and need to split them into
two subsets with the lowest possible difference. Therefore, the
quality of a solution can be measured through Eq. 1, where
item yx represents element x from subset y, and N y represents
the number of elements in subset y.
Q=

i=1

j=1

/ item 1i - / item 2j .

(1)

One way of solving this problem requires two steps. First, assign
all items to a single subset (i.e., subset 1). Then, choose some
items for moving to the other subset (i.e., subset 2). Here, item
transfer should stop if subset 2 represents, at least, half the items.
Item selection can be done through two low-level heuristics:
the Max load, and the Min load. Both can perform well or
poorly, depending on the problem instance. For example, if the
set of items is [10 1 1 1 1 1 1 1 1 1 1 1 1], both heuristics yield
a perfect split (Q = 0). However, if the set is [10 9 8 1 1 2 2 1 1
1 1 1 1], the quality is 15 for the Max heuristic and 1 for the
Min heuristic. Moreover, if the set comprises [10 3 4 2 10 10 1
1 1 1 1 1 1], the Max heuristic yields a solution with Q = 14
while the Min yields one with Q = 6.
A hyper-heuristic may represent a better approach, but it
requires a way of mapping features to actions (i.e., the rules).
Here, a single feature ^F1h can be defined as shown in Eq. 2,
and one rule can be defined for each action.
N2

/ item 2j

F1 =

j=1
N1

i=1

j=1

/ item 1i + / item 2j

(2)

Figure 2 shows a sample set of rules (top) and its corresponding zone of influence (bottom). This means that, whenever the feature value is below 0.25, an item will be moved
following the Max heuristic. For higher feature values, it will
be moved according to the Min heuristic. For example, consider the last instance. The first two items will be selected using

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - May 2018