Abstract
The Shortest Common Supersequence problem is a hard combinatorial optimization problem with numerous practical applications. Several evolutionary approaches are proposed for this problem, considering the utilization of penalty functions, GRASP-based decoders, or repairing mechanisms. An empirical comparison is conducted, using an extensive benchmark comprising problem instances of different size and structure. The empirical results indicate that there is no single best approach, and that the size of the alphabet, and the structure of strings are crucial factors for determining performance. Nevertheless, the repair-based EA seems to provide the best performance tradeoff.
Chapter PDF
Similar content being viewed by others
References
Foulser, D., Li, M., Yang, Q.: Theory and algorithms for plan merging. Artificial Intelligence 57, 143–181 (1992)
Timkovsky, V.: Complexity of common subsequence and supersequence problems and related problems. Cybernetics 25, 565–580 (1990)
Hallet, M.: An integrated complexity analysis of problems from computational biology. PhD thesis, University of Victoria (1996)
Bodlaender, H., Downey, R., Fellows, M., Wareham, H.: The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147, 31–54 (1994)
Middendorf, M.: More on the complexity of common superstring and supersequence problems. Theoretical Computer Science 125, 205–228 (1994)
Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences 67, 757–771 (2003)
Fraser, C.: Subsequences and Supersequences. PhD thesis, University of Glasgow, Department of Computer Science (1995)
Branke, J., Middendorf, M., Schneider, F.: Improved heuristics and a genetic algorithm for finding short supersequences. OR-Spektrum 20, 39–45 (1998)
Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1998)
Cotta, C., Troya, J.: A hybrid genetic algorithm for the 0-1 multiple knapsack problem. In: Smith, G., Steele, N., Albrecht, R. (eds.) Artificial Neural Nets and Genetic Algorithms, Wien New York, pp. 251–255. Springer, Heidelberg (1998)
Feo, T., Resende, M.: Greedy randomized adaptive search procedures. Journal of Global Optimization 6, 109–133 (1995)
Prais, M., Ribeiro, C.C.: Parameter variation in GRASP procedures. Investigación Operativa 9, 1–20 (2000)
Prais, M., Ribeiro, C.: Reactive GRASP: an application to a matrix decomposition problem in TDMA traffic assignment. INFORMS Journal on Computing 12, 164–176 (2000)
Cotta, C., Fernández, A.J.: A hybrid GRASP – evolutionary algorithm approach to golomb ruler search. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 481–490. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cotta, C. (2005). A Comparison of Evolutionary Approaches to the Shortest Common Supersequence Problem. In: Cabestany, J., Prieto, A., Sandoval, F. (eds) Computational Intelligence and Bioinspired Systems. IWANN 2005. Lecture Notes in Computer Science, vol 3512. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494669_7
Download citation
DOI: https://doi.org/10.1007/11494669_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26208-4
Online ISBN: 978-3-540-32106-4
eBook Packages: Computer ScienceComputer Science (R0)