Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Reinforcement Learning for Multi-Neighborhood Local Search in Combinatorial Optimization

  • Conference paper
  • First Online:
Machine Learning, Optimization, and Data Science (LOD 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14506))

  • 466 Accesses

Abstract

This study investigates the application of reinforcement learning for the adaptive tuning of neighborhood probabilities in stochastic multi-neighborhood search. The aim is to provide a more flexible and robust tuning method for heterogeneous scenarios than traditional offline tuning. We propose a novel mix of learning components for multi-neighborhood Simulated Annealing, which considers both cost- and time-effectiveness of moves. To assess the performance of our approach we employ two real-world case studies in timetabling, namely examination timetabling and sports timetabling, for which multi-neighborhood Simulated Annealing has already obtained remarkable results using offline tuning techniques. Experimental data show that our approach obtains better results than the analogous algorithm that uses state-of-the-art offline tuning on benchmarking datasets while requiring less tuning effort.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.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

Institutional subscriptions

Notes

  1. 1.

    The running time was scaled based on the ratio of performance on the different machines.

References

  1. Adriaensen, S., et al.: Automated dynamic algorithm configuration. J. Artif. Intell. Res. 75, 1633–1699 (2022)

    Article  MathSciNet  Google Scholar 

  2. Alicastro, M., Ferone, D., Festa, P., Fugaro, S., Pastore, T.: A reinforcement learning iterated local search for makespan minimization in additive manufacturing machine scheduling problems. Comput. Oper. Res. 131, 105272 (2021)

    Article  MathSciNet  Google Scholar 

  3. Anagnostopoulos, A., Michel, L., Van Hentenryck, P., Vergados, Y.: A simulated annealing approach to the traveling tournament problem. J. Sched. 9(2), 177–193 (2006)

    Article  Google Scholar 

  4. Bartz-Beielstein, T., et al.: Benchmarking in optimization: best practice and open issues. CoRR, arXiv abs/2007.03488 (2020)

    Google Scholar 

  5. Bellio, R., Ceschia, S., Di Gaspero, L., Schaerf, A.: Two-stage multi-neighborhood simulated annealing for uncapacitated examination timetabling. Comput. Oper. Res. 132, 105300 (2021)

    Article  MathSciNet  Google Scholar 

  6. Bellio, R., Ceschia, S., Di Gaspero, L., Schaerf, A., Urli, T.: Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem. Comput. Oper. Res. 65, 83–92 (2016)

    Article  MathSciNet  Google Scholar 

  7. Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur. J. Oper. Res. 290(2), 405–421 (2021)

    Article  MathSciNet  Google Scholar 

  8. Burke, E.K., Hyde, M.R., Kendall, G., Ochoa, G., Özcan, E., Woodward, J.: A classification of hyper-heuristic approaches: revisited. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 272, pp. 453–477. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-91086-4_14

  9. Carter, M., Laporte, G., Lee, S.: Examination timetabling: algorithmic strategies and applications. J. Oper. Res. Soc. 74, 373–383 (1996)

    Article  Google Scholar 

  10. Ceschia, S., Di Gaspero, L., Schaerf, A.: Educational timetabling: problems, benchmarks, and state-of-the-art results. Eur. J. Oper. Res. 308(1), 1–18 (2023)

    Article  MathSciNet  Google Scholar 

  11. Doerr, B., Doerr, C.: Theory of parameter control for discrete black-box optimization: provable performance gains through dynamic parameter choices. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation. NCS, pp. 271–321. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4_6

  12. Fialho, A., Da Costa, L., Schoenauer, M., Sebag, M.: Analyzing bandit-based adaptive operator selection mechanisms. Ann. Math. Artif. Intell. 60(1–2), 25–64 (2010)

    Article  MathSciNet  Google Scholar 

  13. Franzin, A., Stützle, T.: Revisiting simulated annealing: a component-based analysis. Comput. Oper. Res. 104, 191–206 (2019)

    Article  MathSciNet  Google Scholar 

  14. Glover, F., Kochenberger, G.: Handbook of Metaheuristics, vol. 57. Springer, Berlin, Heidelberg (2006). ISBN 978-1402072635

    Google Scholar 

  15. Gunawan, A., Lau, H.C., Lu, K.: Adopt: combining parameter tuning and adaptive operator ordering for solving a class of orienteering problems. Comput. Ind. Eng. 121, 82–96 (2018)

    Article  Google Scholar 

  16. Huang, C., Li, Y., Yao, X.: A survey of automatic parameter tuning methods for metaheuristics. IEEE Trans. Evolut. Comput. 24(2), 201–216 (2020)

    Article  Google Scholar 

  17. Hutter, F., Hoos, H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: Coello, C.A.C. (eds.) Learning and Intelligent Optimization. LION 2011. LNCS, vol. 6683, pp. 507–523. Springer, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25566-3_40

  18. Kadioglu, S., Malitsky, Y., Sellmann, M., Tierney, K.: ISAC-instance-specific algorithm configuration. In: ECAI 2010, pp. 751–756. IOS Press (2010)

    Google Scholar 

  19. Kallestad, J., Hasibi, R., Hemmati, A., Sörensen, K.: A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems. Eur. J. Oper. Res. 309(1), 446–468 (2023)

    Article  MathSciNet  Google Scholar 

  20. Karimi-Mamaghan, M., Mohammadi, M., Meyer, P., Karimi-Mamaghan, A., Talbi, E.G.: Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art. Eur. J. Oper. Res. 296(2), 393–422 (2022)

    Article  MathSciNet  Google Scholar 

  21. Kheiri, A., Gretsista, A., Keedwell, E., Lulli, G., Epitropakis, M., Burke, E.: A hyper-heuristic approach based upon a hidden Markov model for the multi-stage nurse rostering problem. Comput. Oper. Res. 130, 105221 (2021)

    Article  MathSciNet  Google Scholar 

  22. KhudaBukhsh, A., Xu, L., Hoos, H., Leyton-Brown, K.: SATenstein: automatically building local search SAT solvers from components. Artif. Intell. 232, 20–42 (2016)

    Article  MathSciNet  Google Scholar 

  23. Lamaz-Fernandez, C., Martinez-Sykora, A., Potts, C.: Scheduling double round-robin sports tournaments. In: Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling, vol. 2 (2021)

    Google Scholar 

  24. Li, J., Pardalos, P.M., Sun, H., Pei, J., Zhang, Y.: Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups. Expert Syst. Appl. 42(7), 3551–3561 (2015)

    Article  Google Scholar 

  25. López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L.P., Birattari, M., Stützle, T.: The irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43–58 (2016)

    MathSciNet  Google Scholar 

  26. Lü, Z., Hao, J.K.: Adaptive neighborhood search for nurse rostering. Eur. J. Oper. Res. 218(3), 865–876 (2012)

    Article  Google Scholar 

  27. Mara, S., Norcahyo, R., Jodiawan, P., Lusiantoro, L., Rifai, A.P.: A survey of adaptive large neighborhood search algorithms and applications. Comput. Oper. Res. 146(105903) (2022)

    Google Scholar 

  28. Maron, O., Moore, A.: The racing algorithm: model selection for lazy learners. Artif. Intell. Rev. 11(1), 193–225 (1997)

    Article  Google Scholar 

  29. Mischek, F., Musliu, N.: Reinforcement learning for cross-domain hyper-heuristics. In: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence IJCAI-22, pp. 4793–4799 (2022)

    Google Scholar 

  30. Mosadegh, H., Ghomi, S., Süer, G.: 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)

    Article  MathSciNet  Google Scholar 

  31. Pisinger, D., Ropke, S.: Large neighborhood search. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 272, pp. 99–127. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-91086-4_4

  32. Rosati, R.M., Petris, M., Di Gaspero, L., Schaerf, A.: Multi-neighborhood simulated annealing for the sports timetabling competition ITC2021. J. Sched. 25(3), 301–319 (2022)

    Article  MathSciNet  Google Scholar 

  33. dos Santos, J., de Melo, J., Neto, A., Aloise, D.: Reactive search strategies using reinforcement learning, local search algorithms and variable neighborhood search. Expert Syst. Appl. 41(10), 4939–4949 (2014)

    Article  Google Scholar 

  34. Schneider, M., Hoos, H.: Quantifying homogeneity of instance sets for algorithm configuration. In: Hamadi, Y., Schoenauer, M. (eds.) Learning and Intelligent Optimization. LION 2012. LNCS, vol. 7219, pp. 190–204. Springer, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34413-8_14

  35. Shahmardan, A., Sajadieh, M.: Truck scheduling in a multi-door cross-docking center with partial unloading-reinforcement learning-based simulated annealing approaches. Comput. Ind. Eng. 139, 106134 (2020)

    Article  Google Scholar 

  36. Smith-Miles, K., Baatar, D., Wreford, B., Lewis, R.: Towards objective measures of algorithm performance across instance space. Comput. Oper. Res. 45, 12–24 (2014)

    Article  MathSciNet  Google Scholar 

  37. Song, H., Triguero, I., Özcan, E.: A review on the self and dual interactions between machine learning and optimisation. Progress Artif. Intell. 8(2), 143–165 (2019)

    Article  Google Scholar 

  38. Sutton, R., Barto, A.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (2018)

    Google Scholar 

  39. Talbi, E.G.: Machine learning into metaheuristics: a survey and taxonomy. ACM Comput. Surv. (CSUR) 54(6), 1–32 (2021)

    Article  Google Scholar 

  40. Toffolo, T.A., Christiaens, J., Van Malderen, S., Wauters, T., Vanden Berghe, G.: Stochastic local search with learning automaton for the swap-body vehicle routing problem. Comput. Oper. Res. 89, 68–81 (2018)

    Article  MathSciNet  Google Scholar 

  41. Van Bulck, D., Goossens, D.: The international timetabling competition on sports timetabling (ITC2021). Eur. J. Oper. Res. 308(3), 1249–1267 (2023)

    Article  Google Scholar 

Download references

Acknowledgments

This research has been funded by the Italian Ministry of University and Research under the action PRIN 2020, project “Models and algorithms for the optimization of integrated healthcare management”.

Author information

Authors and Affiliations

  1. DPIA, University of Udine, via delle Scienze 206, 33100, Udine, Italy

    Sara Ceschia, Luca Di Gaspero, Roberto Maria Rosati & Andrea Schaerf

Authors
  1. Sara Ceschia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luca Di Gaspero
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Roberto Maria Rosati
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andrea Schaerf
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Roberto Maria Rosati .

Editor information

Editors and Affiliations

  1. University of Catania, Catania, Catania, Italy

    Giuseppe Nicosia

  2. Newcastle University, Newcastle upon Tyne, UK

    Varun Ojha

  3. University of Oxford, Oxford, UK

    Emanuele La Malfa

  4. University of Cambridge, Cambridge, UK

    Gabriele La Malfa

  5. University of Florida, Gainesville, FL, USA

    Panos M. Pardalos

  6. Dana-Farber Cancer Institute, Boston, MA, USA

    Renato Umeton

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ceschia, S., Di Gaspero, L., Rosati, R.M., Schaerf, A. (2024). Reinforcement Learning for Multi-Neighborhood Local Search in Combinatorial Optimization. In: Nicosia, G., Ojha, V., La Malfa, E., La Malfa, G., Pardalos, P.M., Umeton, R. (eds) Machine Learning, Optimization, and Data Science. LOD 2023. Lecture Notes in Computer Science, vol 14506. Springer, Cham. https://doi.org/10.1007/978-3-031-53966-4_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-53966-4_16

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-53965-7

  • Online ISBN: 978-3-031-53966-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation