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 Elsevier B.V. All rights reserved.

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 [10.1016/j.orl.2013.09.002].

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

CASTELLI, MAURO
;
BERETTA, STEFANO
Secondo
;
VANNESCHI, LEONARDO
Ultimo
2013

Abstract

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 Elsevier B.V. All rights reserved.
Articolo in rivista - Articolo scientifico
Estimation of distribution algorithms; Genetic algorithms; Heuristics; Repetition free longest common subsequence; Management Science and Operations Research; Applied Mathematics; Industrial and Manufacturing Engineering; Software
English
644
649
6
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 [10.1016/j.orl.2013.09.002].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/59888
Citazioni
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 8
Social impact