Paper Info
Title
Efficient stochastic local search algorithm for solving the shortest common supersequence problem
Abstract
The Shortest Common Supersequence (SCS) problem is a well-known hard combinatorial optimization problem that formalizes many real world problems. Recently, an application of the iterative optimization method called Prototype Optimization with Evolved Improvement Steps (POEMS) to the SCS problem has been proposed. The POEMS seeks the best variation of the current solution in each iteration. The variations, considered as structured hypermutations, are evolved by means of an evolutionary algorithm. This approach has been shown to work very well on synthetic as well as real biological data. However, the approach exhibited rather low scalability which is caused by very time demanding evaluation function. This paper proposes a new time efficient evaluation procedure and a new moving-window strategy for constructing and refining the supersequence. These two enhancements significantly improve an efficiency of the approach. Series of experiments with the modified POEMS method have been carried out. Results presented in this paper show that the method is competitive with current state-of-the-art algorithms for solving the SCS problem. Moreover, there is a potential for further improvement as discussed in the conclusions.
Year
DOI
Venue
2010
10.1145/1830483.1830529
GECCO
Keywords
Field
DocType
modified poems method,new time,new moving-window strategy,iterative optimization method,shortest common supersequence problem,evaluation function,scs problem,current state-of-the-art algorithm,real world problem,efficient stochastic local search,current solution,efficient evaluation procedure,evolutionary algorithms,evolutionary algorithm,biological data,combinatorial optimization,shortest common supersequence
Biological data,Evolutionary algorithm,Computer science,Artificial intelligence,Optimization problem,Mathematical optimization,Shortest common supersequence,Algorithm,Evaluation function,Combinatorial optimization,Local search (optimization),Machine learning,Scalability
Conference
Citations 
PageRank 
References 
7
0.62
13
Authors
1
Name
Order
Citations
PageRank
Jiří Kubalík1556.42