2010 | OriginalPaper | Buchkapitel
A Hybrid Metaheuristic for the Longest Common Subsequence Problem
verfasst von : Manuel Lozano, Christian Blum
Erschienen in: Hybrid Metaheuristics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.