Abstract
Hyper-heuristics (HHs) are algorithms suitable for designing heuristics. HHs perform the search divided in two levels: they look for heuristic components in the high level and the heuristic is used, in the low level, to solve a set of instances of one or more problems. Different from offline HHs, hyper-heuristics with dynamic learning select or generate heuristics during the search. This paper proposes a hyper-heuristic associated with a dynamic learning strategy for selecting Iterated Greedy (IG) components. The proposal is capable of selecting appropriate values for six IG components: local search, perturbation, destruction size, neighborhood size, destruction position and local search focus. The proposed HH is tested with six dynamic adaptation strategies: random, \(\epsilon \)-greedy, probability matching, multi-armed bandit, LinUCB, and Thompson Sampling (TS). The hyper-parameters of each strategy are tuned by irace. As a testbed, we use several instances with four different sizes (20, 50, 100 and 200 jobs) of three different formulations of flowshop problems (permutation, no-wait, no-idle), two distinct objectives (makespan, flowtime), and four processing time distributions (uniform, exponential and job or machine correlated). The results show that different strategies are most suitable for adapting different IG components, TS performs quite well for all components and, except for local search, using adaptation is always beneficial when compared with the IG running with standard parameters.
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
Notes
- 1.
Tuning and Testing instances, as well as the code used in the paper, are available at https://github.com/lucasmpavelski/Adaptive-IG.
References
Auer, P.: Using confidence bounds for exploitation-exploration trade-offs. J. Mach. Learn. Res. 3(9), 397–422 (2002)
Baker, K.R., Trietsch, D.: Principles of Sequencing and Scheduling. Wiley Publishing, New Jersey USA (2009)
Burcin, O.F., Sagir, M.: Iterated greedy algorithms enhanced by hyper-heuristic based learning for hybrid flexible flowshop scheduling problem with sequence dependent setup times: a case study at a manufacturing plant. Comput. Oper. Res. 125, 105044 (2021). https://doi.org/10.1016/j.cor.2020.105044
Burke, E.K., Hyde, M.R., Kendall, G., Ochoa, G., Özcan, E., Woodward, J.R.: A classification of hyper-heuristic approaches: revisited. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics. ISORMS, vol. 272, pp. 453–477. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-91086-4_14
Chakhlevitch, K., Cowling, P.: Hyperheuristics: recent developments. In: Studies in Computational Intelligence, vol. 136, pp. 3–29. Springer, Berlin, Heidelberg (2008). https://doi.org/10.1007/978-3-540-79438-7_1
Dubois-Lacoste, J., Pagnozzi, F., Stützle, T.: An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem. Comput. Oper. Res. 81, 160–166 (2017). https://doi.org/10.1016/j.cor.2016.12.021
Goldberg, D.E.: Probability matching, the magnitude of reinforcement, and classifier system Bidding. Mach. Learn. 5(4), 407–425 (1990). https://doi.org/10.1023/A:1022681708029
Gupta, N., Granmo, O.C., Agrawala, A.: Thompson sampling for dynamic multi-armed bandits. In: 2011 10th International Conference on Machine Learning and Applications and Workshops, pp. 484–489. IEEE, Honolulu, HI, USA (2011). https://doi.org/10.1109/ICMLA.2011.144
Humeau, J., Liefooghe, A., Talbi, E.G., Verel, S.: ParadisEO-MO: From Fitness Landscape Analysis to Efficient Local Search Algorithms. Research Report RR-7871, INRIA (2013)
Kerschke, P., Hoos, H.H., Neumann, F., Trautmann, H.: Automated algorithm selection: survey and perspectives. Evol. Comput. 27(1), 3–45 (2019)
Li, K., Fialho, A., Kwong, S., Zhang, Q.: Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 18(1), 114–130 (2014). https://doi.org/10.1109/TEVC.2013.2239648
Li, L., Chu, W., Langford, J., Schapire, R.E.: A contextual-bandit approach to personalized news article recommendation. In: Proceedings of the 19th International Conference on World Wide Web - WWW ’10, p. 661. ACM Press, Raleigh, North Carolina, USA (2010). https://doi.org/10.1145/1772690.1772758
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L.P., Stützle, T., Birattari, M.: The irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43–58 (2016). https://doi.org/10.1016/j.orp.2016.09.002
Pappa, G.L., Ochoa, G., Hyde, M.R., Freitas, A.A., Woodward, J., Swan, J.: Contrasting meta-learning and hyper-heuristic research: the role of evolutionary algorithms. Genetic Program. Evolvable Mach. 15(1), 3–35 (2013). https://doi.org/10.1007/s10710-013-9186-9
Pillay, N., Qu, R.: Hyper-heuristics: theory and applications. Springer Nature, 1 edn. (2018). https://doi.org/10.1007/978-3-319-96514-7
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, Brisbane, Australia (2012). https://doi.org/10.1109/CEC.2012.6252969
Pitzer, E., Affenzeller, M.: Recent Advances in Intelligent Engineering Systems. Studies in Computational Intelligence, vol. 378, chap. A Comprehensive Survey on Fitness Landscape Analysis, pp. 161–186. Springer, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-23229-9
Ruiz, R., Stützle, T.: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur. J. Oper. Res. 177(3), 2033–2049 (2007). https://doi.org/10.1016/j.ejor.2005.12.009
Russo, D., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z.: A Tutorial on Thompson Sampling. arXiv:1707.02038 [cs] (2020)
Sapkal, S.U., Laha, D.: A heuristic for no-wait flow shop scheduling. Int. J. Adv. Manuf. Technol. 1, 1327–1338 (2013). https://doi.org/10.1007/s00170-013-4924-y
Stützle, T.: Applying iterated local search to the permutation flow shop problem. Technical report, FG Intellektik, TU Darmstadt, Darmstadt, Germany (1998)
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. Adaptive Computation and Machine Learning Series. 2nd edn. The MIT Press, Cambridge, Massachusetts (2018)
Tasgetiren, M.F., Pan, Q.K., Suganthan, P.N., Liang, Y.C.: A discrete differential evolution algorithm for the no-wait flowshop scheduling problem with total flowtime criterion. In: 2007 IEEE Symposium on Computational Intelligence in Scheduling, pp. 251–258. IEEE, Honolulu, USA (2007)
Watson, J.P., Barbulescu, L., Howe, A.E., Whitley, L.D.: Algorithm performance and problem structure for flow-shop scheduling. In: AAAI/IAAI, pp. 688–695. American Association for Artificial Intelligence, Menlo Park, CA, USA (1999)
Yahyaoui, H., Krichen, S., Derbel, B., Talbi, E.G.: A hybrid ILS-VND based hyper-heuristic for permutation flowshop scheduling problem. Procedia Comput. Sci. 60, 632–641 (2015). https://doi.org/10.1016/j.procs.2015.08.199
Zhang, L., Wang, L., Zheng, D.Z.: An adaptive genetic algorithm with multiple operators for flowshop scheduling. Int. J. Adv. Manuf. Technol. 27(5–6), 580–587 (2006). https://doi.org/10.1007/s00170-004-2223-3
Acknowledgment
M. Delgado acknowledges CNPq (grants 439226/2018-0, 314699/2020-1) for her partial financial support.
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
Pavelski, L.M., Kessaci, MÉ., Delgado, M. (2021). Dynamic Learning in Hyper-Heuristics to Solve Flowshop Problems. In: Britto, A., Valdivia Delgado, K. (eds) Intelligent Systems. BRACIS 2021. Lecture Notes in Computer Science(), vol 13073. Springer, Cham. https://doi.org/10.1007/978-3-030-91702-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-91702-9_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-91701-2
Online ISBN: 978-3-030-91702-9
eBook Packages: Computer ScienceComputer Science (R0)