IEEE Computational Intelligence Magazine - May 2018 - 33

the Max heuristic, since feature values are 0 and 0.22. When
selecting the third item, the feature value goes up to 0.43. Thus,
from this point onward all items are selected using the Min
heuristic, until the feature becomes, at least, equal to 0.5.
Through this approach, problem instances one and three can be
perfectly solved (i.e., Q = 0 ), while the second one can be
solved with Q = 1, thus making it a better solver.
B. Problems Derived from Using Features Directly

Using the aforementioned model with raw features may exhibit
two drawbacks [12]: likeliness and stagnation. The former
appears when two problem instances with similar features are
best solved by different actions (e.g., at the boundary of regions
best solved by both actions). Should one rule (from the selector)
be closest to both states, one of them would not be solved in
the best possible way. Similarly, if problem states best solved by
the same action are apart, clustering them frees up space to distribute them among other actions. Figure 3 shows an example
of both scenarios. In the figure, each circle represents the best
location for a rule, and their corresponding actions are given by
A i . The square marker represents the current state of a problem, indicated by FT , and where the action to be taken, A T ,
must be decided by using the closest point. However, on the left,
rules one and three are so clustered that a small error when
placing them (e.g., when evolving), could lead to a wrong decision. At the right, transformations help by clustering alike
regions and expanding troublesome ones, allowing for a
smoother change in the performance of a selector-in-training.
The second problem, to which we refer to as stagnation, is
related to the nature of optimization procedures [12]. During
the first iterations, improvements are significant and quite common. As the search progresses, they become less frequent and
less significant. For our hyper-heuristic model, stagnation
reflects on a population of selectors with small differences in
both, features and performance. Nonetheless, by transforming
features we can expand part of the feature space, allowing for a
bigger variation which may lead to improvements.

R A =
Max

0.50

FigurE 2 An example of a set of rules (top) and its corresponding
zone of influence (bottom).

C. Previous Work Related to Feature Transformations

Feature transformation is an active research field in machine
learning, where the idea is to use information from the original
features to create new ones with improved predictive power.
Several methods have been proposed. Some of the best known
methods are normalization, standardization, and polynomial
transformation [5]. An emerging area is the use of evolutionary
computation for taking into account the behavior of the recognition system [6]. In spite of its success, this approach is computationally costly.
We have previously studied feature transformation for
improving the performance of selection hyper-heuristics. In
[12], we applied Eq. 3, where K = 5 is a parameter we determined empirically, and which behaves as shown in Fig. 4. To
improve upon that idea, in this work we test two new transformations and a way for tailoring them to each feature (Sect. III).
U (x) = 1 - 2· c e

-K·x

- e -K .
m
1 + e -K·x

0.6
0.4

FT : AT
A3
A1
0.2

0.4
0.6
Feature 1
(a)

0.8

1.0

(3)

D. Kernels

Kernel functions implicitly embed mapping functions, and
were popularized by Support Vector Machines [21] and the socalled kernel trick. This has enabled them to learn nonlinear
functions, greatly improving their performance.

Feature 2 (Transformed)

A2
A2

Feature 2

Stop

1.0

0.8

0.0
0.0

Min

0.25

1.0

0.2

0.20 Max
0.30 Min

A2
A2

0.8
0.6
0.4

FT : AT

0.2
0.0
0.0

A1
0.2
0.4
0.6
0.8
Feature 1 (Transformed)

1.0

(b)

FigurE 3 Distribution of rules before (a) and after (b) feature transformation. Square: Current state of the problem. Circles: Ideal location of
rules. Ai: Actions of each ideal rule.

may 2018 | IEEE ComputatIonal IntEllIgEnCE magazInE

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