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

被引：10
|
作者：
Castelli, Mauro [1 ]
Beretta, Stefano [2 ,3 ]
Vanneschi, Leonardo [1 ,2 ]
机构：
[1] Univ Nova Lisboa, ISEGI, P-1070312 Lisbon, Portugal
[2] Univ Milano Bicocca, DISCo, I-20126 Milan, Italy
[3] CNR, Inst Biomed Technol, I-20090 Segrate, Italy
来源：
OPERATIONS RESEARCH LETTERS | 2013年 / 41卷 / 06期
关键词：
Repetition free longest common subsequence; Heuristics; Genetic algorithms; Estimation of distribution algorithms; COMPLEXITY;
D O I：
10.1016/j.orl.2013.09.002
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
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. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：644 / 649
页数：6
相关论文
共 50 条
  • [1] A genetic algorithm for the longest common subsequence problem
    Hinkemeyer, Brenda
    Julstrorn, Bryant A.
    GECCO 2006: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2, 2006, : 609 - +
  • [2] On the parameterized complexity of the repetition free longest common subsequence problem
    Blin, Guillaume
    Bonizzoni, Paola
    Dondi, Riccardo
    Sikora, Florian
    INFORMATION PROCESSING LETTERS, 2012, 112 (07) : 272 - 276
  • [3] Repetition-free longest common subsequence
    Adi, Said S.
    Braga, Marilia D. V.
    Fernandes, Cristina G.
    Ferreira, Carlos E.
    Martinez, Fabio Viduani
    Sagot, Marie-France
    Stefanes, Marco A.
    Tjandraatmadja, Christian
    Wakabayashi, Yoshiko
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (12) : 1315 - 1324
  • [4] A comprehensive comparison of metaheuristics for the repetition-free longest common subsequence problem
    Christian Blum
    Maria J. Blesa
    Journal of Heuristics, 2018, 24 : 551 - 579
  • [5] A comprehensive comparison of metaheuristics for the repetition-free longest common subsequence problem
    Blum, Christian
    Blesa, Maria J.
    JOURNAL OF HEURISTICS, 2018, 24 (03) : 551 - 579
  • [6] Beam-ACO for the Repetition-Free Longest Common Subsequence Problem
    Blum, Christian
    Blesa, Maria J.
    Calvo, Borja
    ARTIFICIAL EVOLUTION, EA 2013, 2014, 8752 : 79 - 90
  • [7] A HYBRID ALGORITHM FOR THE LONGEST COMMON TRANSPOSITION-INVARIANT SUBSEQUENCE PROBLEM
    Deorowicz, Sebastian
    Grabowski, Szymon
    COMPUTING AND INFORMATICS, 2009, 28 (05) : 729 - 744
  • [8] A new algorithm for the longest common subsequence problem
    Xiang, Xuyu
    Zhang, Dafang
    Qin, Jiaohua
    CIS WORKSHOPS 2007: INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND SECURITY WORKSHOPS, 2007, : 112 - 115
  • [9] A Hybrid Metaheuristic for the Longest Common Subsequence Problem
    Lozano, Manuel
    Blum, Christian
    HYBRID METAHEURISTICS, 2010, 6373 : 1 - +
  • [10] An improved algorithm for the longest common subsequence problem
    Mousavi, Sayyed Rasoul
    Tabataba, Farzaneh
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (03) : 512 - 520
12345