TY - JOUR
T1 - A hybrid genetic algorithm for the repetition free longest common subsequence problem
AU - Castelli, Mauro
AU - Beretta, Stefano
AU - Vanneschi, Leonardo
N1 - Castelli, M., Beretta, S., & Vanneschi, L. (2013). A hybrid genetic algorithm for the repetition free longest common subsequence problem. Operations Research Letters, 41(6), 644-649. https://doi.org/10.1016/j.orl.2013.09.002
PY - 2013/10/1
Y1 - 2013/10/1
N2 - 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.
AB - 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.
KW - Estimation of distribution algorithms
KW - Genetic algorithms
KW - Heuristics
KW - Repetition free longest common subsequence
UR - http://www.scopus.com/inward/record.url?scp=84884601178&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2013.09.002
DO - 10.1016/j.orl.2013.09.002
M3 - Article
AN - SCOPUS:84884601178
VL - 41
SP - 644
EP - 649
JO - Operations Research Letters
JF - Operations Research Letters
SN - 0167-6377
IS - 6
ER -