DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication
Otros (Other)
A neural network based guidance for a BRKGA: an application to the longest common square subsequence problem
24th European Conference, EvoCOP 2024 Held as Part of EvoStar 2024 Aberystwyth, UK, April 3–5, 2024, Proceedings, Thomas Stützle, Markus Wagner, editors, In this work we apply machine learning to better guide a biased random key genetic algorithm (Brkga) for the longest common square subsequence (LCSqS) problem. The problem is a variant of the well-known longest common subsequence (LCS) problem in which valid solutions are square strings. A string is square if it can be expressed as the concatenation of a string with itself. The original Brkga is based on a reduction of the LCSqS problem to the LCS problem by cutting each input string into two parts. Our work consists in enhancing the search process of Brkga for good cut points by using a machine learning approach, which is trained to produce promising cut points for the input strings of a problem instance. In this study, we show the benefits of this approach by comparing the enhanced Brkga with the original Brkga, using two benchmark sets from the literature. We show that the results of the enhanced Brkga significantly improve over the original results, especially when tackling instances with non-uniformly generated input strings., Jaume Reixach and Christian Blum are supported by grants TED2021-129319B-I00
and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033. G¨unter
R. Raidl is supported by the Vienna Graduate School on Computational Optimization
(VGSCO), Austrian Science Foundation, project no. W1260-N35. Marko Djukanovi´c
is supported by the project entitled “Development of artificial intelligence models and
algorithms for solving difficult combinatorial optimization problems” funded by the
Ministry of Scientific and Technological Development and the Higher Education of the
Republic of Srpska., Peer reviewed