Title:
|
A hybrid metaheuristic for the longest common subsequence problem
|
Author:
|
Lozano, Manuel; Blum, Christian
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
Abstract:
|
The longest common subsequence problem is a classical string problem. It has applications, for example, in pattern recognition and bioinformatics. This contribution proposes an integrative hybrid
metaheuristic for this problem. More specifically, we propose a variable
neighborhood search that applies an iterated greedy algorithm in the improvement phase and generates the starting solutions by invoking either beam search or a greedy randomized procedure. The main motivation of
this work is the lack of fast neighborhood search methods for the tackled problem. The benefits of the proposal in comparison to the state of the art are experimentally shown. |
Abstract:
|
Peer Reviewed |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat -Longest common subsequence problem -LCS -Problema de la subseqüencia comuna mes llarga |
Rights:
|
|
Document type:
|
Article - Published version Article |
Share:
|
|