Abstract
Selection hyper-heuristics have proven to be effective in solving various real-world problems. Hyper-heuristics differ from traditional heuristic approaches in that they explore a heuristic space rather than a solution space. These techniques select constructive or perturbative heuristics to construct a solution or improve an existing solution respectively. Previous work has shown that the set of problem-specific heuristics made available to the hyper-heuristic for selection has an impact on the performance of the hyper-heuristic. Hence, there have been initiatives to determine the appropriate set of heuristics that the hyper-heuristic can select from. However, there has not been much research done in this area. Furthermore, previous work has focused on determining a set of heuristics that is used throughout the lifespan of the hyper-heuristic with no change to this set during the application of the hyper-heuristic. This paper investigates dynamic heuristic set selection (DHSS) which applies dominance to select the set of heuristics at different points during the lifespan of a selection hyper-heuristic. The DHSS approach was evaluated on the benchmark set for the CHeSC cross-domain hyper-heuristic challenge. DHSS was found to improve the performance of the best performing hyper-heuristic for this challenge.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adriaensen, S., Brys, T., Nowé, A.: Fair-share ILS: a simple state-of-the-art iterated local search hyperheuristic. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 1303–1310 (2014)
Alvarez-Benitez, J.E., Everson, R.M., Fieldsend, J.E.: A MOPSO algorithm based exclusively on pareto dominance concepts. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.) EMO 2005. LNCS, vol. 3410, pp. 459–473. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31880-4_32
Chan, C.Y., Xue, F., Ip, W.H., Cheung, C.F.: A hyper-heuristic inspired by pearl hunting. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, pp. 349–353. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34413-8_26
Drake, J.H., Kheiri, A., Özcan, E., Burke, E.K.: Recent advances in selection hyper-heuristics. Eur. J. Oper. Res. 285(2), 405–428 (2020)
Burke, E.K., et al.: The cross-domain heuristic search challenge – an international research competition. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 631–634. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25566-3_49
Gutierrez-Rodríguez, A.E., et al.: Applying automatic heuristic-filtering to improve hyper-heuristic performance. In: 2017 IEEE Congress on Evolutionary Computation (CEC), pp. 2638–2644. IEEE (2017)
Hassan, A., Pillay, N.: Java library for dynamic heuristic set selection, September 2021. https://github.com/Al-Madina/Dynamic-Heuristic-Sets
Hsiao, P.C., Chiang, T.C., Fu, L.C.: A VNS-based hyper-heuristic with adaptive computational budget of local search. In: 2012 IEEE Congress on Evolutionary Computation, pp. 1–8. IEEE (2012)
Hyde, M., Ochoa, G., Vázquez-Rodríguez, J.A., Curtois, T.: A hyflex module for the max-sat problem. University of Nottingham, Technical report, pp. 3–6 (2011)
Meignan, D.: An evolutionary programming hyper-heuristic with co-evolution for CHeSC11. In: The 53rd Annual Conference of the UK Operational Research Society (OR53), vol. 3 (2011)
Mısır, M., Verbeeck, K., De Causmaecker, P., Vanden Berghe, G.: The effect of the set of low-level heuristics on the performance of selection hyper-heuristics. In: Coello, C.A.C., Cutello, V., Deb, K., Forrest, S., Nicosia, G., Pavone, M. (eds.) PPSN 2012. LNCS, vol. 7492, pp. 408–417. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32964-7_41
Mısır, M., Verbeeck, K., De Causmaecker, P., Vanden Berghe, G.: An intelligent hyper-heuristic framework for CHeSC 2011. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, pp. 461–466. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34413-8_45
Ochoa, G., et al.: HyFlex: a benchmark framework for cross-domain heuristic search. In: Hao, J.-K., Middendorf, M. (eds.) EvoCOP 2012. LNCS, vol. 7245, pp. 136–147. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29124-1_12
Pillay, N., Qu, R.: Hyper-Heuristics: Theory and Applications. Natural Computing Series, Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-96514-7
Pillay, N.: A review of hyper-heuristics for educational timetabling. Ann. Oper. Res. 239(1), 3–38 (2016)
Soria-Alcaraz, J.A., Ochoa, G., Sotelo-Figeroa, M.A., Burke, E.K.: A methodology for determining an effective subset of heuristics in selection hyper-heuristics. Eur. J. Oper. Res. 260(3), 972–983 (2017)
Vázquez-Rodrıguez, J.A., Ochoa, G., Curtois, T., Hyde, M.: A hyflex module for the permutation flow shop problem. School of Computer Science, University of Nottingham, Technical report (2009)
Acknowledgments
This work is funded as part of the Multichoice Research Chair in Machine Learning at the University of Pretoria, South Africa. This work is based on the research supported wholly/in part by the National Research Foundation of South Africa (Grant Numbers 46712). Opinions expressed and conclusions arrived at, are those of the author and are not necessarily to be attributed to the NRF. This work is run on the Lengau Cluster of the Center for High Performance Computing, South Africa.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Hassan, A., Pillay, N. (2021). Dynamic Heuristic Set Selection for Cross-Domain Selection Hyper-heuristics. In: Aranha, C., Martín-Vide, C., Vega-Rodríguez, M.A. (eds) Theory and Practice of Natural Computing. TPNC 2021. Lecture Notes in Computer Science(), vol 13082. Springer, Cham. https://doi.org/10.1007/978-3-030-90425-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-90425-8_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-90424-1
Online ISBN: 978-3-030-90425-8
eBook Packages: Computer ScienceComputer Science (R0)