Abstract
This work leverages reinforcement learning for designing a new variant of Construct, Merge, Solve and Adapt (CMSA), a rather new hybrid metaheuristic for combinatorial optimization. We demonstrate a twofold improvement over the standard CMSA. Firstly, the new variant simplifies CMSA by eliminating the need for a greedy function to probabilistically generate solutions. Additionally, it performs better, as we demonstrate in the context of the Minimum Dominating Set (MDS) problem.
The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033.
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
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)
Blum, C., Pinacho, P., López-Ibáñez, M., Lozano, J.A.: Construct, merge, solve & adapt a new general algorithm for combinatorial optimization. Comput. Oper. Res. 68, 75–88 (2016)
Erdös, P., Rényi, A.: On random graphs I. Publ. Math. Debrecen 6(290–297), 18 (1959)
Johnson, D.S., Garey, M.R.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman (1979)
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)
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (2018)
Woolson, R.F.: Wilcoxon signed-rank test. Wiley Encycl. Clin. Trials 1–3 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Reixach, J., Blum, C. (2024). Extending CMSA with Reinforcement Learning: Application to Minimum Dominating Set. In: Sevaux, M., Olteanu, AL., Pardo, E.G., Sifaleras, A., Makboul, S. (eds) Metaheuristics. MIC 2024. Lecture Notes in Computer Science, vol 14754. Springer, Cham. https://doi.org/10.1007/978-3-031-62922-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-031-62922-8_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-62921-1
Online ISBN: 978-3-031-62922-8
eBook Packages: Computer ScienceComputer Science (R0)