Skip to main content
SpringerLink
Log in
Book cover

Brazilian Conference on Intelligent Systems

BRACIS 2021: Intelligent Systems pp 155–169Cite as

Dynamic Learning in Hyper-Heuristics to Solve Flowshop Problems

  • Conference paper
  • First Online:

  • 590 Accesses

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 13073))

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.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

Notes

  1. 1.

    Tuning and Testing instances, as well as the code used in the paper, are available at https://github.com/lucasmpavelski/Adaptive-IG.

References

  1. Auer, P.: Using confidence bounds for exploitation-exploration trade-offs. J. Mach. Learn. Res. 3(9), 397–422 (2002)

    Google Scholar 

  2. Baker, K.R., Trietsch, D.: Principles of Sequencing and Scheduling. Wiley Publishing, New Jersey USA (2009)

    Google Scholar 

  3. 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

  4. 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

    Chapter  Google Scholar 

  5. 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

  6. 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

    Article  MathSciNet  MATH  Google Scholar 

  7. 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

    Article  Google Scholar 

  8. 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

  9. 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)

    Google Scholar 

  10. Kerschke, P., Hoos, H.H., Neumann, F., Trautmann, H.: Automated algorithm selection: survey and perspectives. Evol. Comput. 27(1), 3–45 (2019)

    Article  Google Scholar 

  11. 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

    Article  Google Scholar 

  12. 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

  13. 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

    Article  MathSciNet  Google Scholar 

  14. 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

    Article  Google Scholar 

  15. Pillay, N., Qu, R.: Hyper-heuristics: theory and applications. Springer Nature, 1 edn. (2018). https://doi.org/10.1007/978-3-319-96514-7

  16. 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

  17. 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

  18. 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

    Article  MATH  Google Scholar 

  19. Russo, D., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z.: A Tutorial on Thompson Sampling. arXiv:1707.02038 [cs] (2020)

  20. 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

  21. Stützle, T.: Applying iterated local search to the permutation flow shop problem. Technical report, FG Intellektik, TU Darmstadt, Darmstadt, Germany (1998)

    Google Scholar 

  22. Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. Adaptive Computation and Machine Learning Series. 2nd edn. The MIT Press, Cambridge, Massachusetts (2018)

    Google Scholar 

  23. 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)

    Google Scholar 

  24. 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)

    Google Scholar 

  25. 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

    Article  Google Scholar 

  26. 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

    Article  Google Scholar 

Download references

Acknowledgment

M. Delgado acknowledges CNPq (grants 439226/2018-0, 314699/2020-1) for her partial financial support.

Author information

Authors and Affiliations

  1. CPGEI - Universidade Tecnológica Federal do Paraná, Curitiba, Brazil

    Lucas Marcondes Pavelski & Myriam Delgado

  2. CRIStAL - Univ. Lille, CNRS - Centrale Lille - UMR 9189, 59000, Lille, France

    Marie-Éléonore Kessaci

Authors
  1. Lucas Marcondes Pavelski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marie-Éléonore Kessaci
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Myriam Delgado
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lucas Marcondes Pavelski .

Editor information

Editors and Affiliations

  1. Universidade Federal de Sergipe, São Cristóvão, Brazil

    André Britto

  2. Universidade de São Paulo, São Paulo, Brazil

    Karina Valdivia Delgado

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics

Search

Navigation