IEEE Computational Intelligence Magazine - May 2018 - 35
A. Proposed Explicit Feature Transformations
This section presents two explicit transformations for a single feature (i). Expressions are given in terms of a midpoint (M i),and a
half-width (W i). For this work, we considered that every point in
the training set may be meaningful within the test set and should
be preserved.Thus, we defined M i = (max ( fi ) + min ( fi )) /2 and
W i = (max ( fi ) - min ( fi )) /2. Here, fi is a vector containing the
values of feature i for the training instances. Figure 5 shows the
location of all instances used in this work (except for the confirmatory testing; please refer to Sect. IV for more details). This plot
corresponds to information yielded by a Principal Component
Analysis (PCA) that was used to reduce the data from eight to
two features. Moreover, data have been separated into training
(stars) and testing (diamonds). Besides, the train/test ratio that will
be used in the tests was also considered here. As Fig. 5 shows,
unsolved and solved instances are spread out throughout the feature domain. Furthermore, the unsolved training instances (black
stars) that seem away from the other ones actually share their
location with unsolved testing instances (magenta diamonds).
Therefore, if the hyper-heuristic uses this information during its
training, it may perform better. Besides, as instances are solved,
their features shift locations until reaching the spot indicated by
red stars (training instances) and by green diamonds (testing
instances). Using the transformation from [12] does not guarantee
that every value will be included. On the other hand, using the
Reduced Feature 2
We explore two fronts for improving the predictive power of
features in selection hyper-heuristics: explicit and implicit transformations. Our motivation for doing so is twofold. The first
one is that original features may change a lot throughout the
first iterations, but eventually arrive at a point of negligible
change. By using feature transformations this behavior could be
delayed. The second one is that part of the feature space may be
wasted by considering feature values that never (or scarcely)
appear in practice and that belong to the same solver. Through
feature transformation these regions could be compressed, raising the importance of regions that belong to different solvers.
We now provide the main elements of each transformation, and
throughout this work we also explore the eventual benefit of
combining them (see Sect. IV).
4
2
0
Test (S)
Test (E)
Train (S)
Train (E)
-2
-4
-4
-2
0
2
Reduced Feature 1
4
FigurE 5 Plot of initial (S) and final (E) features used in this work.
Data have been reduced from eight to two features by using PCA.
1.0
Transformed Feature i
III. Our Proposed Approach
current proposal, the hyper-heuristic can adapt to the data presented in the training instances.
Figure 6 shows both transformations. The idea is to map
values within a given range to the full feasible interval, i.e.,
[0, 1]. In the Linear case (top), the way in which the feature is
distributed remains unaffected by using Eq. 8. In the S-shaped
case (bottom), extreme values are smoothed out and the middle
region is highlighted via Eq. 9.
0.8
0.6
0.4
Wi
0.2
0.0
0.0
Mi
0.2
0.4
0.6
Feature i
(a)
0.8
1.0
0.8
1.0
1.0
Transformed Feature i
In all cases, the performance of the methods for solving
CSPs was measured by using at least one of the following
metrics [12]:
❏ Consistency Checks (CC): Total revisions of constraints
after an instance ends, such that the larger the number of constraints, the more expensive the search becomes. This value is
used in the objective function during the training phase of the
hyper-heuristics.
❏ Adjusted Consistency Checks (ACC): Similar to the previous one, but discarding instances where the solver times out.
❏ Success Rate (SR): Relation between the number of
completed and tested instances. The higher the rate, the better the solver.
0.8
0.6
0.4
Wi
0.2
0.0
0.0
Mi
0.2
0.4
0.6
Feature i
(b)
FigurE 6 Overview of the Linear (top) and S-shaped (bottom) transformations used in this work. M i is the center of the transformation
and W i represents its half-width.
may 2018 | IEEE ComputatIonal IntEllIgEnCE magazInE
35
Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - May 2018
Contents
IEEE Computational Intelligence Magazine - May 2018 - Cover1
IEEE Computational Intelligence Magazine - May 2018 - Cover2
IEEE Computational Intelligence Magazine - May 2018 - Contents
IEEE Computational Intelligence Magazine - May 2018 - 2
IEEE Computational Intelligence Magazine - May 2018 - 3
IEEE Computational Intelligence Magazine - May 2018 - 4
IEEE Computational Intelligence Magazine - May 2018 - 5
IEEE Computational Intelligence Magazine - May 2018 - 6
IEEE Computational Intelligence Magazine - May 2018 - 7
IEEE Computational Intelligence Magazine - May 2018 - 8
IEEE Computational Intelligence Magazine - May 2018 - 9
IEEE Computational Intelligence Magazine - May 2018 - 10
IEEE Computational Intelligence Magazine - May 2018 - 11
IEEE Computational Intelligence Magazine - May 2018 - 12
IEEE Computational Intelligence Magazine - May 2018 - 13
IEEE Computational Intelligence Magazine - May 2018 - 14
IEEE Computational Intelligence Magazine - May 2018 - 15
IEEE Computational Intelligence Magazine - May 2018 - 16
IEEE Computational Intelligence Magazine - May 2018 - 17
IEEE Computational Intelligence Magazine - May 2018 - 18
IEEE Computational Intelligence Magazine - May 2018 - 19
IEEE Computational Intelligence Magazine - May 2018 - 20
IEEE Computational Intelligence Magazine - May 2018 - 21
IEEE Computational Intelligence Magazine - May 2018 - 22
IEEE Computational Intelligence Magazine - May 2018 - 23
IEEE Computational Intelligence Magazine - May 2018 - 24
IEEE Computational Intelligence Magazine - May 2018 - 25
IEEE Computational Intelligence Magazine - May 2018 - 26
IEEE Computational Intelligence Magazine - May 2018 - 27
IEEE Computational Intelligence Magazine - May 2018 - 28
IEEE Computational Intelligence Magazine - May 2018 - 29
IEEE Computational Intelligence Magazine - May 2018 - 30
IEEE Computational Intelligence Magazine - May 2018 - 31
IEEE Computational Intelligence Magazine - May 2018 - 32
IEEE Computational Intelligence Magazine - May 2018 - 33
IEEE Computational Intelligence Magazine - May 2018 - 34
IEEE Computational Intelligence Magazine - May 2018 - 35
IEEE Computational Intelligence Magazine - May 2018 - 36
IEEE Computational Intelligence Magazine - May 2018 - 37
IEEE Computational Intelligence Magazine - May 2018 - 38
IEEE Computational Intelligence Magazine - May 2018 - 39
IEEE Computational Intelligence Magazine - May 2018 - 40
IEEE Computational Intelligence Magazine - May 2018 - 41
IEEE Computational Intelligence Magazine - May 2018 - 42
IEEE Computational Intelligence Magazine - May 2018 - 43
IEEE Computational Intelligence Magazine - May 2018 - 44
IEEE Computational Intelligence Magazine - May 2018 - 45
IEEE Computational Intelligence Magazine - May 2018 - 46
IEEE Computational Intelligence Magazine - May 2018 - 47
IEEE Computational Intelligence Magazine - May 2018 - 48
IEEE Computational Intelligence Magazine - May 2018 - 49
IEEE Computational Intelligence Magazine - May 2018 - 50
IEEE Computational Intelligence Magazine - May 2018 - 51
IEEE Computational Intelligence Magazine - May 2018 - 52
IEEE Computational Intelligence Magazine - May 2018 - 53
IEEE Computational Intelligence Magazine - May 2018 - 54
IEEE Computational Intelligence Magazine - May 2018 - 55
IEEE Computational Intelligence Magazine - May 2018 - 56
IEEE Computational Intelligence Magazine - May 2018 - 57
IEEE Computational Intelligence Magazine - May 2018 - 58
IEEE Computational Intelligence Magazine - May 2018 - 59
IEEE Computational Intelligence Magazine - May 2018 - 60
IEEE Computational Intelligence Magazine - May 2018 - 61
IEEE Computational Intelligence Magazine - May 2018 - 62
IEEE Computational Intelligence Magazine - May 2018 - 63
IEEE Computational Intelligence Magazine - May 2018 - 64
IEEE Computational Intelligence Magazine - May 2018 - 65
IEEE Computational Intelligence Magazine - May 2018 - 66
IEEE Computational Intelligence Magazine - May 2018 - 67
IEEE Computational Intelligence Magazine - May 2018 - 68
IEEE Computational Intelligence Magazine - May 2018 - 69
IEEE Computational Intelligence Magazine - May 2018 - 70
IEEE Computational Intelligence Magazine - May 2018 - 71
IEEE Computational Intelligence Magazine - May 2018 - 72
IEEE Computational Intelligence Magazine - May 2018 - 73
IEEE Computational Intelligence Magazine - May 2018 - 74
IEEE Computational Intelligence Magazine - May 2018 - 75
IEEE Computational Intelligence Magazine - May 2018 - 76
IEEE Computational Intelligence Magazine - May 2018 - 77
IEEE Computational Intelligence Magazine - May 2018 - 78
IEEE Computational Intelligence Magazine - May 2018 - 79
IEEE Computational Intelligence Magazine - May 2018 - 80
IEEE Computational Intelligence Magazine - May 2018 - Cover3
IEEE Computational Intelligence Magazine - May 2018 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com