A Comparison of Evolutionary Approaches to the Shortest Common Supersequence Problem
|
C. Cotta Computational Intelligence and Bioinspired Systems, J. Cabestany, A. Prieto, F. Sandoval (eds.), Lecture Notes in Computer Science 3512, pp. 50-58, Springer-Verlag Berlin, 2005 © Springer-Verlag Berlin Heidelberg 2005. All rights reserved. |
|
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. | |
|
 |
|
Download BibTEX entry | |
|
 |
|
Download PDF version (178K) | |
[Back to publications page].