IEEE Computational Intelligence Magazine - May 2018 - 31

I. Introduction

yper-heuristics have emerged in recent years as a
strategy for combining the strengths of different
heuristics into a single method. Their aim is to provide more flexibility when solving a wider variety
of optimization problems [1]. Initially, authors used the term
hyper-heuristic to describe heuristics for choosing heuristics.
Nowadays, this definition also includes the automatic generation of heuristics. Thus, hyper-heuristics operate at a higher
level of generality by working with low-level heuristics rather
than by solving a problem. Burke et al. present an in-depth
survey about the topic in [1].
Selection hyper-heuristics represent a subset that relies on a
mechanism for interpreting the problem state and deciding the
most suitable heuristic to apply. One of the main challenges for
automating this decision is how to properly characterize such a
state, to allow a correct mapping to heuristics. There are different ways to get such a mapping. Examples include machine
learning [2] and evolutionary algorithms [3]. Despite this, the
effectiveness of the selection depends greatly on the predictive
power of the feature set [4].
Feature preprocessing is a major step in data mining and it
plays a central role in the generalization performance of the
models. This step encompasses selection, generation and transformation [5]. Feature selection seeks to choose a subset of the
most relevant features, for the problem at hand. Feature generation focuses on getting a new set of more discriminating features by combining primitive ones. Feature transformation aims
at adapting the set of features to help learning algorithms
improve their learning stage. Xue et al. offer a comprehensive
review on feature selection and generation in [6], [7]. Similarly,
other authors give an in-depth discussion on feature transformation in [5], [8].
In recent years, there has been an interest in studying feature
preprocessing for hyper-heuristics. Outstanding applications
include [9]-[11]. In [9], Smith-Miles and Lopes studied the relationships between critical features of problem instances and algorithm performance. Besides, Montazeri explored feature
selection through genetic algorithms in [10]. Additionally, Hart et
al. analyzed the effect of feature generation in hyper-heuristics
[11]. Most early studies in hyper-heuristics have focused on feature selection or feature generation while neglecting an analysis
of feature transformation to empower hyper-heuristics. The only
work in this regard is [12], where several transforming functions
were proposed. Such functions required a manual tuning of
parameters. Moreover, the authors failed to assess their scalability
beyond two dimensions, and its generalization for several problem domains. To the best of our knowledge, no previous study
has adapted the transformation functions and explored kernel
transformations [13]. Our hypothesis is that doing so may facilitate the rule-creation process (see Sect. V-A). This, in turn, may
allow selection hyper-heuristics to work on higher dimensional
spaces and for a broader set of domains, enhancing them.
Thus, this paper makes two main contributions. First, it proposes explicit transformations, based on linear and S-shaped

functions, with parameters tailored to the distribution of each
feature. Second, it exchanges the distance function for one
using a radial basis function kernel. Our experimental results
confirm the validity of the proposed methods for improving
the performance of selection hyper-heuristics in two optimization domains.
The rest of the paper is organized as follows. Section II
presents the preliminaries for properly understanding this work.
We delve in the inner workings of a hyper-heuristic, and on
the problems related to using features directly. Moreover, we
present work previously done to explore the feasibility of using
feature transformations. In this section we also present the main
ideas regarding kernels and our test domain. Afterwards, we
describe our proposed approach (Section III), focusing on the
definition of the transformations. Section IV describes the
experimental methodology adopted in this work, which was
split into four stages. Section V presents the obtained data and
their discussion. Striving to facilitate the meaning of our data,
we split this section into the same four stages as Section IV.
Finally, the conclusions and some possible paths for future work
are laid out in Section VI.
II. Preliminaries

We begin this section by describing what hyper-heuristics are
and how they operate. We focus on selection hyper-heuristics
since it is the approach used in this work, although it is worth
highlighting that other types of hyper-heuristics exist. After
that, we explain two problems related to features and how
transforming them may prove helpful. We then summarize the
main idea behind a previously reported work dealing with feature transformations. We wrap this section up by discussing the
main ideas behind a notion known as Kernel and the domain in
which we carry out our experiments.
A. Hyper-Heuristics

The No-Free-Lunch (NFL) theorem [14] implies that there is
no algorithm that best solves all kinds of problems. Thus, a
recent and recurring alternative is to use a strategy for combining many feasible solvers. Each of the problems that requires
being solved is usually referred to as an "instance". Even if this
is a clever way to try and circumvent the restrictions posed by
the NFL theorem, a recursive problem arises: the algorithm
selection problem [15]. Here, focus migrates to finding a proper
way to carry out the selection in such a way that turns out to
be beneficial. Several approaches rely on this idea to improve
the generality of their solution method [16], [17], but detailing
them is beyond the scope of this manuscript.
Throughout this work we use an evolutionary hyper-heuristic model proposed in [18]. This model falls into the category
of selection hyper-heuristics, and it is depicted in Fig. 1. The
idea is to solve a given instance using a combination of algorithms, ruled by a "selector". The pillar for this idea is that a
partially solved problem may not be as efficiently solved by the
same algorithm and, thus, a change should be made. To identify
the moment in which it is appropriate to switch the solver, this

may 2018 | IEEE ComputatIonal IntEllIgEnCE magazInE

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