Mayerhofer, J., Kirchweger, M., Huber, M., & Raidl, G. (2022). A Beam Search for the Shortest Common Supersequence Problem Guided by an Approximate Expected Length Calculation. In Evolutionary Computation in Combinatorial Optimization (pp. 127–142). Springer Nature Switzerland AG. https://doi.org/10.34726/3442
Beam Search; Shortest Common Supersequence Problem
en
Abstract:
The shortest common supersequence problem (SCSP) is a well-known NP-hard problem with many applications, in particular in data compression, computational molecular biology, and text editing. It aims at finding for a given set of input strings a shortest string such that every string from the set is a subsequence of the computed string. Due to its NP-hardness, many approaches have been proposed to tackle the SCSP heuristically. The currently best-performing one is based on beam search (BS). In this paper, we present a novel heuristic (AEL) for guiding a BS, which approximates the expected length of an SCSP of random strings, and embed the proposed heuristic into a multilevel probabilistic beam search (MPBS). To overcome the arising scalability issue of the guidance heuristic, a cut-off approach is presented that reduces large instances to smaller ones. The proposed approaches are tested on two established sets of benchmark instances. MPBS guided by AEL outperforms the so far leading method on average on a set of real instances. For many instances new best solutions could be obtained.
en
Project title:
Doktoratskolleg "Vienna Graduate School on Computational Optimization": W1260-N35 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
