Coevolving solutions to the shortest common superstring problem.
The shortest common superstring (SCS) problem, known to be NP-Complete, seeks the shortest string that contains all strings from a given set. In this paper we compare four approaches for finding solutions to the SCS problem: a standard genetic algorithm, a novel cooperative-coevolutionary algorithm, a benchmark greedy algorithm, and a parallel coevolutionary-greedy approach. We show the coevolutionary approach produces the best results, and discuss directions for future research.
Zaritsky
Assaf
A
Department of Computer Science, Ben-Gurion University, P.O. Box 653, Beer-Sheva 84105, Israel. assafza@cs.bgu.ac.il
Sipper
Moshe
M
D000465:Algorithms; D000818:Animals; D005075:Biological Evolution; D003198:Computer Simulation; D017124:Conserved Sequence; D006801:Humans; D008957:Models, Genetic; D009716:Numerical Analysis, Computer-Assisted; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology