title: A hyper-heuristic for the Longest Common Subsequence problem.
abstract: The Longest Common Subsequence Problem is the problem of finding a longest string that is a subsequence of every member of a given set of strings. It has applications in FPGA circuit minimization, data compression, and bioinformatics, among others. The problem is NP-hard in its general form, which implies that no exact polynomial-time algorithm currently exists for the problem. Consequently, inexact algorithms have been proposed to obtain good, but not necessarily optimal, solutions in an affordable time. In this paper, a hyper-heuristic algorithm incorporated within a constructive beam search is proposed for the problem. The proposed hyper-heuristic is based on two basic heuristic functions, one of which is new in this paper, and determines dynamically which one to use for a given problem instance. The proposed algorithm is compared with state-of-the-art algorithms on simulated and real biological sequences. Extensive experimental reveals that the proposed hyper-heuristic is superior to the state-of-the-art methods with respect to the solution quality and the running-time.
authors.affiliation: Department of Electrical and Computer Engineering, Isfahan University of Technology, Isfahan 84156, Iran. f.tabataba@ec.iut.ac.ir
authors.forename: Farzaneh Sadat
authors.initials: FS
authors.lastname: Tabataba
authors.forename: Sayyed Rasoul
authors.initials: SR
authors.lastname: Mousavi