IEEE Computational Intelligence Magazine - May 2018 - 41
VI. Conclusions and Future Work
Throughout this work we defined two approaches for carrying
out an explicit transformation of features, and one for doing so
implicitly. Our aim was to improve the performance of selection
hyper-heuristics. We tested these ideas, and their combinations,
on the widely used domain of CSPs. We found that, when considering two features, all transformations help the selection
hyper-heuristic to generate solvers that perform closer (on average) to a synthetic oracle. Moreover, the S-shaped and the kernel-based transformations increased the median SR in about
15% while decreasing the median search cost in about 20,000
ACC. This means that both approaches led to a higher number
of instances being solved while reducing the cost of solving
them. Even so, combining both ideas did not prove fruitful. Linear transformation was the only one enhanced by adding the
kernel, improving its success rate but hindering its search cost.
Increasing the number of features up to eight did not work as
well for the S-shaped transformation as it did for the kernel. This
time around the median success rate of both approaches lurked
around 90%, but only the latter exhibited almost no variation
(except for a few outliers). Similarly, the search cost was better
through both approaches. In fact, the median search cost of the
S-shaped transformation was the lowest one, being 5,000 adjusted
consistency checks lower than that without the transformation.
Only the one using kernel had a small variation, exhibiting a standard deviation almost 40% lower than that of the original approach.
Because of the aforementioned, we determined that the pure
Kernel approach was the best way of incorporating transformations
into selection hyper-heuristics. A confirmatory test run on the
Knapsack domain considered instances with 50 and 100 items. Data
revealed that the standard deviation of the profit achieved by hyperheuristics could be reduced by almost 30% and 20% (respectively),
making transformations a worthwhile effort. Moreover, a statistical
test confirmed a significant increase in the performance of selection
hyper-heuristics for the set with 100 items. Thus, we recommend
following this idea and applying it to different domains and under
different conditions, as to better assess how its benefits propagate.
In this work, we defined c as the inverse of the number of features. However, some exploratory tests (omitted due to space
restrictions) revealed that this may not always be the best approach
for selecting it. Therefore, a future research avenue in this path
could relate to improving the kernel-based transformation. This
could be done by designing a procedure that tailors c to each
problem domain. In other words, one that tailors it to different
configurations, e.g., by using information not only from the number of features but also from their nature. Another path worth following is to carry out a more extensive testing, e.g., by increasing
the number and variety of instances and features. Such testing
should include a careful analysis of all the different combinations of
features, focusing on the effect of feature transformations on the
performance of hyper-heuristics.
Acknowledgment
This research was partially supported by CONACyT Basic
Science Projects under grants 241461, 221551 and 287479,
and ITESM Research Group with Strategic Focus in Intelligent Systems.
References
[1] E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and R. Qu,
"Hyper-heuristics: A survey of the state of the art," J. Oper. Res. Soc., vol. 64, no. 12,
pp. 1695-1724, Dec. 2013.
[2] J. C. Ortiz-Bayliss, H. Terashima-Marín, and S. E. Conant-Pablos, "Learning vector
quantization for variable ordering in constraint satisfaction problems," Pattern Recognit.
Lett., vol. 34, no. 4, pp. 423-432, Mar. 2013.
[3] T. N. Ferreira, J. A. P. Lima, A. Strickler, J. N. Kuk, S. R. Vergilio, and A. Pozo,
"Hyper-heuristic based product selection for software product line testing," IEEE Comput. Intell. Mag., vol. 12, no. 2, pp. 34-45, Apr. 2017.
[4] I. Guyon and A. Elisseeff, "An introduction to variable and feature selection," J.
Mach. Learn. Res., vol. 3, no. Mar, pp. 1157-1182, Mar. 2003.
[5] S. García, J. Luengo, and F. Herrera, Data Preprocessing in Data Mining, vol. 72. New
York: Springer, 2014.
[6] B. Xue and M. Zhang, "Evolutionary computation for feature manipulation: Key
challenges and future directions," in Proc. IEEE Congr. Evolutionary Computation, Vancouver, Canada, July 2016, pp. 3061-3067.
[7] B. Xue, M. Zhang, W. N. Browne, and X. Yao, "A survey on evolutionary computation approaches to feature selection," IEEE Trans. Evol. Comput., vol. 20, no. 4, pp.
606-626, Aug. 2016.
[8] D. Pyle, Data Preparation for Data Mining, 1st ed. San Francisco, CA: Morgan Kaufmann, 1999.
[9] K. Smith-Miles and L. Lopes, "Measuring instance difficulty for combinatorial optimization problems," Comput. Oper. Res., vol. 39, no. 5, pp. 875-889, May 2012.
[10] M. Montazeri, "HHFS: Hyper-heuristic feature selection," Intell. Data Anal., vol.
20, no. 4, pp. 953-974, June 2016.
[11] E. Hart, K. Sims, K. Kamimura, and B. Gardiner, "A hybrid method for feature
construction and selection to improve wind-damage prediction in the forestry sector," in
Proc. Genetic Evolutionary Computation Conf., Berlin, Germany, July 2017, pp. 1121-1128.
[12] I. Amaya, J. C. Ortiz-Bayliss, A. E. Gutiérrez-Rodríguez, H. Terashima-Marín, and C. A.
Coello Coello, "Improving hyper-heuristic performance through feature transformation," in
Proc. IEEE Congr. Evolutionary Computation, San Sebastian, Spain, June 2017, pp. 2614-2621.
[13] B. Schölkopf and A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. Cambridge, MA: MIT Press, 2002.
[14] D. H. Wolpert and W. G. Macready, "No free lunch theorems for optimization,"
IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 67-82, Apr. 1997.
[15] J. R. Rice, "The algorithm selection problem," in Advances in Computers, vol. 15.
1976, pp. 65-118.
[16] E. O'Mahony, E. Hebrard, A. Holland, C. Nugent, and B. O'Sullivan, "Using casebased reasoning in an algorithm portfolio for constraint solving," in Proc. Irish Conf.,
Artificial Intelligence and Cognitive Science, Cork City, Ireland, Aug. 2008, pp. 210-216.
[17] Y. Malitsky and M. Sellmann, "Instance-specific algorithm configuration as a
method for non-model-based portfolio generation," in Integration of AI and OR Techniques
in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2012. Lecture
Notes in Computer Science, N. Beldiceanu, N. Jussien, and É. Pinson, Eds. Berlin, Germany: Springer, 2012, pp. 244-259.
[18] J. C. Ortiz-Bayliss, H. Terashima-Marín, and S. E. Conant-Pablos, "Combine and
conquer: An evolutionary hyper-heuristic approach for solving constraint satisfaction
problems," Artif. Intell. Rev., vol. 46, no. 3, pp. 327-349, Oct. 2016.
[19] J. G. Marín-Blázquez and S. Schulenburg, "Multi-step environment learning classifier systems applied to hyper-heuristics," in Proc. 8th Annu. Conf. Genetic and Evolutionary
Computation, Seattle, WA, July 2006, pp. 1521-1528.
[20] J. C. Ortiz-Bayliss, H. Terashima-Marín, and S. E. Conant-Pablos, "Using learning
classifier systems to design selective hyper-heuristics for constraint satisfaction problems,"
in Proc. IEEE Congr. Evolutionary Computation, Cancun, Mexico, June 2013, pp. 2618-2625.
[21] V. N. Vapnik, The Nature of Statistical Learning Theory. New York: Springer-Verlag, 1995.
[22] J. Berlier and J. McCollum, "A constraint satisfaction algorithm for microcontroller
selection and pin assignment," in Proc. IEEE SoutheastCon, Concord, MA, Mar. 2010,
pp. 348-351.
[23] S. V. Bochkarev, M. V. Ovsyannikov, A. B. Petrochenkov, and S. A. Bukhanov,
"Structural synthesis of complex electrotechnical equipment on the basis of the constraint
satisfaction method," Russian Elect. Eng., vol. 86, no. 6, pp. 362-366, June 2015.
[24] I. P. Gent, P. Prosser, and T. Walsh, "The constrainedness of search," in Proc. Association Advancement Artificial Intelligence Conf. '96, Portland, OR, Aug. 1999, pp. 246-252.
[25] S. A. Bittle and M. S. Fox, "Learning and using hyper-heuristics for variable and
value ordering in constraint satisfaction problems," in Proc. ACM 11th Annu. Conf. Companion Genetic Evolutionary Computation: Late Breaking Papers, Quebec, Canada, July 2009,
pp. 2209-2212.
[26] F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais, "Boosting systematic search by
weighting constraints," in Proc. European Conf. Artificial Intelligence, Valencia, Spain, Aug.
2004, pp. 146-150.
[27] A. J. Bagnall and G. C. Cawley, "On the use of default parameter settings in the empirical evaluation of classification algorithms," CoRR, vol. abs/1703.06777, Mar. 2017.
[28] J. C. Bezdek and R. J. Hathaway, "VAT: A tool for visual assessment of (cluster) tendency," in Proc. Int. Joint Conf. Neural Networks, Honolulu, HI, May 2002, vol. 3. pp. 2225-2230.
[29] D. Pisinger, "Where are the hard knapsack problems?" Comput. Oper. Res., vol. 32,
no. 9, pp. 2271-2284, Sept. 2005.
may 2018 | IEEE ComputatIonal IntEllIgEnCE magazInE
41
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