Abstract
The choice of heuristic operators is strongly related to the performance of a (meta-)heuristic algorithm. Hence, applying an automated selection approach can increase the robustness of an optimization system. In this work, we investigate the use of a reinforcement learning technique as the selection mechanism of a hyper-heuristic algorithm. Specifically, we use the approximate Q-learning using an Artificial Neural Network as function approximation. Moreover, we evaluate different sets of metrics for representing the state of the environment, which in this scenario, must indicate the search stage of the optimization algorithm. The experiments conducted on six combinatorial problem domains indicate that, with simple state measures (combining the last action vector and fitness improvement rate), our approach yields better results compared to a state-of-the-art Multi-Armed Bandit approach, which does not have state representation.
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
Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47(2), 235–256 (2002)
Blum, C., Puchinger, J., Raidl, G.R., Roli, A.: Hybrid metaheuristics in combinatorial optimization: a survey. Appl. Soft Comput. 11(6), 4135–4151 (2011)
Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Woodward, J.R.: A classification of hyper-heuristic approaches. In: Gendreau, M., Potvin, JY. (eds.) Handbook of Metaheuristics. ISOR, vol. 146, pp. 449–468. Springer, Boston (2010). https://doi.org/10.1007/978-1-4419-1665-5_15
Buzdalova, A., Kononov, V., Buzdalov, M.: Selecting evolutionary operators using reinforcement learning: initial explorations. In: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 1033–1036 (2014)
Fialho, Á.: Adaptive Operator Selection for Optimization. Université Paris Sud - Paris XI (Dec, Theses (2010)
Handoko, S.D., Nguyen, D.T., Yuan, Z., Lau, H.C.: Reinforcement learning for adaptive operator selection in memetic search applied to quadratic assignment problem. In: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 193–194. GECCO Comp 2014, Association for Computing Machinery, New York, NY, USA (2014)
Kirkpatrick, S., Gelatt, C.D., Jr., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Li, K., Fialho, Á., Kwong, S., Zhang, Q.: Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evolution. Comput. 18(1), 114–130 (2014)
Mısır, M., Verbeeck, K., De Causmaecker, P., Berghe, G.V.: 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
Mosadegh, H., Ghomi, S.F., Süer, G.A.: Stochastic mixed-model assembly line sequencing problem: mathematical modeling and q-learning based simulated annealing hyper-heuristics. Eur. J. Oper. Res. 282(2), 530–544 (2020)
Ochoa, G., et al.: HyFlex: a benchmark framework for cross-domain heuristic search. In: Hao, J.K., Middendorf, M. (eds.) European Conference on Evolutionary Computation in Combinatorial Optimisation(EvoCOP 2012), LNCS, vol. 7245, pp. 136–147. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29124-1_12
Pedregosa, F., et al.: Scikit-learn: machine learning in Python. J. Mach. Learn. Res. 12, 2825–2830 (2011)
Sharma, M., Komninos, A., López-Ibáñez, M., Kazakov, D.: Deep reinforcement learning based parameter control in differential evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 709–717 (2019)
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)
Sutton, R.S., Barto, A.G.: Reinforcement Learning, Second Edition: An Introduction. MIT Press (2018)
Teng, T.H., Handoko, S.D., Lau, H.C.: Self-organizing neural network for adaptive operator selection in evolutionary search. In: Festa, P., Sellmann, M., Vanschoren, J. (eds.) Learning and Intelligent Optimization. LNTCS, vol 10079, pp. 187–202. LNCS, Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50349-3_13
Watkins, C.J.C.H., Dayan, P.: Q-learning. Mach. Learn. 8(3), 279–292 (1992)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dantas, A., Pozo, A. (2022). The Impact of State Representation on Approximate Q-Learning for a Selection Hyper-heuristic. In: Xavier-Junior, J.C., Rios, R.A. (eds) Intelligent Systems. BRACIS 2022. Lecture Notes in Computer Science(), vol 13653. Springer, Cham. https://doi.org/10.1007/978-3-031-21686-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-031-21686-2_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-21685-5
Online ISBN: 978-3-031-21686-2
eBook Packages: Computer ScienceComputer Science (R0)