Minisymposium Evolutionary Algorithms: Analysis of Evolutionary Algorithms for the Longest Common Subsequence

longest sequence of letters that can be found as subsequence in all
members of a given finite set of sequences. The problem is one of the
fundamental problems in computer science with the task of finding a
given pattern in a text as an important special case. It has
applications in bioinformatics, problem-specific algorithms and facts
about its complexity are known. Recently it was reported that
evolutionary algorithms perform well on this problem and that they are
even sometimes able to clearly outperform problem-specific algorithms.
These reports, however, are based on experiments, only. We discuss a
theoretical analysis of a large class of evolutionary algorithms that
encompasses evolutionary algorithms that are as different as steady
state GAs with uniform crossover and randomized hill-climbers. For all
these algorithms it is proved that even rather simple special cases of
the longest common subsequence problem can neither be solved to
optimality nor approximately solved up to an approximation factor
arbitrarily close to 2. This analysis demonstrates on the one hand the
analysis of evolutionary algorithms for a relevant combinatorial
optimization problem and on the other hand the importance of theoretical analyses.