Uma matheurística Construct, Merge, Solve & Adapt para o problema da cadeia de caracteres mais próxima

Abstract

The Closest String Problem (CSP) is a combinatorial optimization problem that seeks to determine a string that best approximates a set of strings with the same length. The CSP is part of a set of optimization problems involving string comparison, with applications in Molecular Biology. This work proposes a Self-Adaptive Construct, Merge, Solve & Adapt (Adapt-CMSA) algorithm using mechanisms from Tabu Search metaheuristic to solve the CSP. CMSA is a matheuristic that explores the problem characteristics to generate a reduced sub-instance of the original problem instance, subsequently employing an exact solver for its resolution. The self-adaptive version of CMSA enhances the algorithm with mechanisms for automatic adaptation of its parameters, making it less sensitive to its configuration across different instances. Experimental results on artificial and real instances demonstrate that the proposed approach significantly outperforms recent heuristic methods proposed in the literature. The optimal value is found in the majority of instances, and the average gap is considerably reduced. Additionally, statistical analyses are conducted to assess the importance of the algorithm’s components in its good performance.