IEEE Computational Intelligence Magazine - May 2018 - 37

each scenario (i.e., with no transformation and for the Linear, Exponential,
Feature Distribution
Preliminary
Instance Analysis
S-shaped, and RBF kernel). We also
Effect of Transformations
include experiments for the combination
of kernel with Linear and S-shaped
15 Runs Each (Two Features)
Performance Comparison
transformations. This leads to 105 selecInitial
All Transformations
Statistical Testing
tion hyper-heuristics (15 × 7). First, we
present their average performance. We
compare it against standalone heuristics
15 Runs Each (Eight Features)
Performance Comparison
Advanced
and baseline selection hyper-heuristics
All Transformations
Statistical Testing
(i.e., with no transformation). Moreover,
we compare our data against that of a
30 Runs Each
Performance Comparison
Confirmatory
synthetic oracle, which can perfectly preBest Transformation
Statistical Testing
dict the best solver for tackling each
instance. Because such solver does not
exist, we build it by using the best solu- FigurE 9 Overview of the four-stage methodology adopted in this work.
tion (among the base heuristics) for each
the correlation between profit and weight. It is important to
instance.We consider it important to highlight that such a process
highlight that each metric is normalized so that their values fall
is infeasible for a real application, but useful as a benchmark.
in the [0, 1] range. Therefore, the first three features are divided
As a second approach, we analyze how stable the data are.
We focus on the success rate and on the search cost of each
by the maximum profit within the instance. The next three
selection hyper-heuristic (see Sect. II-E). We wrap this section
ones are, thus, divided by the maximum weight. The final feaup with a one-tailed Wilcoxon statistical test to determine sigture is increased by one and divided in half. Please bear in mind
nificant increases in the performance of each approach.
that the maximum values are dynamic as they are calculated
from the items remaining in the instance.
Lastly, but not less important, it is worth mentioning that total
C. Advanced Testing
profit is used as the metric for two events. The first one is trainThis stage deepens the previous one by analyzing the effect of
ing the selection hyper-heuristics.The second one is assessing the
transformations over the whole set of eight features (see Sect. II-E).
eventual performance gain derived from the transformation. Also,
Again, we run 15 repetitions of each experiment. We also deterit is important to highlight that the aforementioned profit corremine the performance gain of using each transformation. Moresponds to the sum of profits achieved on each instance. As such,
over, we execute a one-tailed Wilcoxon statistical test to determine
throughout training profit is calculated over 30 instances, but it is
whether a significant performance increase can be achieved.
calculated over 570 throughout testing. As before, we run a onetailed Wilcoxon statistical test to determine whether a significant
D. Confirmatory Testing
increase in profit can be achieved.
In this final stage, we explore the generality of our proposed
approach.Therefore, we select a different domain and generate 30
base selection hyper-heuristics and 30 with the best transformaV. Results and Discussion
tion (more about this in Section V-D). In this work, we chose
This section presents the main results of our work. To make
the knapsack problem, mainly due to its popularity and usefulness,
things easier for the reader, the structure presented in the
and because knowledge about this combinatorial optimization
methodology (Sect. IV) is preserved, reserving one subsection
problem is widespread. Our tests consider two sets of 600 instancfor each main stage.
es each: one with 50 items, and one with 100 items. Each set was
built up with the instances from [29], covering groups 11 to 16.
A. Preliminary Testing
In accordance with previous tests, we trained each selection
Figure 10 shows the distribution of all features in the training
hyper-heuristic using 5% of the instances (i.e., 30).
set, and their transformations. In most cases, the S-shaped transIn this stage, selection hyper-heuristics can select among
formation expands representative data more than the Linear
four popular heuristics. The first three select the item based on
transformation does. Also, in all cases the median of the former
the maximum profit, the minimum weight, or the best profit/
was lower than that of the latter. Another thing worth mentionweight ratio, respectively. The fourth one selects items in their
ing at this point is that the model used in a previous work does
default order. Moreover, selection hyper-heuristics map an
not expand the feature range from zero to unity. However, it
instance based on seven features calculated over the items
allows for values all the way to zero (see Figure 4). This may
remaining in the instance. Three of them use information from
provide it with more flexibility for advanced stages of the search
the profit, and correspond to the mean, median, and standard
where features may migrate to lower regions.
deviation. Another three correspond to the mean, median, and
Figure 11 shows the regions that each instance influences.
standard deviation of the weight. The final one is a measure of
Data are shown for the original features (left), and for the ones

may 2018 | IEEE ComputatIonal IntEllIgEnCE magazInE

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