Evolutionary-based iterative local search algorithm for the shortest common supersequence problem
Jiřı́ Kubalı́k · 2011
The Shortest Common Supersequence (SCS) problem is a well-known hard combinatorial optimization problem with applications in many areas. This paper presents two extensions of recently proposed evolutionary-based iterative local search algorithm called POEMS for solving the SCS problem. Both extensions improve scalability of the algorithm. The first one improves the efficiency of the evaluation procedure and the second one further improves optimization capabilities of the algorithm by intensifying the search towards short supersequence already during the process of constructing the valid supersequence. A moderate size benchmark was used for the proof-of-concept experiments while two very large biological benchmarks were used to demonstrate the capability of the proposed approach. The proposed algorithm performs very well on all of the benchmarks. Moreover, it produces significantly better solutions than the baseline Deposition and Reduction algorithm on the two challenging large benchmarks.