A hybrid genetic algorithm for the repetition free longest common subsequence problem

作者：Castelli Mauro^*; Beretta Stefano; Vanneschi Leonardo

来源：Operations Research Letters, 2013, 41(6): 644-649.

DOI：10.1016/j.orl.2013.09.002

• Repetition free longest common subsequence
• Heuristics
• Genetic algorithms
• Estimation of distribution algorithms

Computing the longest common subsequence of two sequences is one of the most studied algorithmic problems. In this work we focus on a particular variant of the problem, called repetition free longest common subsequence (RF-LCS), which has been proved to be NP-hard. We propose a hybrid genetic algorithm, which combines standard genetic algorithms and estimation of distribution algorithms, to solve this problem. An experimental comparison with some well-known approximation algorithms shows the suitability of the proposed technique.

• 出版日期2013-11