×

zbMATH — the first resource for mathematics

Analysis of evolutionary algorithms for the longest common subsequence problem. (English) Zbl 1184.68604
Summary: In the longest common subsequence problem, the task is to find the longest sequence of letters that can be found as a 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. Motivated by reports about good performance of evolutionary algorithms for some instances of this problem a theoretical analysis of a generic evolutionary algorithm is performed. The general algorithmic framework encompasses EAs 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 be solved up to an approximation factor arbitrarily close to 2.
MSC:
68W05 Nonnumerical algorithms
68T05 Learning and adaptive systems in artificial intelligence
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bergroth, L., Hakonen, H., Raita, T.: (2002): A survey of longest common subsequence algorithms. In: Proceedings of the Seventh International Symposium on String Processing Information Retrieval (SPIRE 2000), pp. 39–48 (2000)
[2] Beyer, H.-G., Schwefel, H.-P., Wegener, I.: How to analyze evolutionary algorithms. Theor. Comput. Sci. 287(1), 101–130 (2002) · Zbl 1061.90119
[3] Briest, P., Brockhoff, D., Degener, B., Englert, M., Gunia, C., Heering, O., Jansen, T., Leifhelm, M., Plociennik, K., Röglin, H., Schweer, A., Sudholt, D., Tannenbaum, S., Wegener, I.: Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization. In: Proceedings of the 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII), pp. 21–30 (2004)
[4] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001) · Zbl 1047.68161
[5] DeJong, K.: Evolutionary Computation: A Unified Approach. MIT Press, Cambridge (2006)
[6] Giel, O., Wegener, I.: Maximum cardinality matchings on trees by randomized local search. In: Proceedings of the 8th Annual Genetic and Evolutionary Computation Conference (GECCO 2006), pp. 539–546 (2006)
[7] Hagerup, T., Rüb, C.: A guided tour of Chernoff bounds. Inf. Process. Lett. 33(6), 305–308 (1990) · Zbl 0702.60021
[8] Hinkemeyer, B., Julstrom, B.A.: A genetic algorithm for the longest common subsequence problem. In: Proceedings of the 8th Annual Genetic and Evolutionary Computation Conference (GECCO 2006), pp. 609–610 (2006)
[9] Jansen, T., Wegener, I.: On the choice of the mutation probability for the (1+1) EA. In: Proceedings of the 6th International Conference on Parallel Problem Solving From Nature (PPSN VI), pp. 89–98 (2000)
[10] Jansen, T., Wiegand, R.P.: Bridging the gap between theory and practice. In: Proceedings of the 8th International Conference on Parallel Problem Solving From Nature (PPSN VIII), pp. 61–71 (2004)
[11] Julstrom, B.A., Hinkemeyer, B.: Starting from scratch: Growing longest common subsequences with evolution. In: Proceedings of the 9th International Conference on Parallel Problem Solving From Nature (PPSN IX), pp. 930–938 (2006)
[12] Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995) · Zbl 0849.68039
[13] Mühlenbein, H.: How evolutionary algorithms really work: Mutation and hillclimbing. In: Proceedings of the 2nd International Conference on Parallel Problem Solving from Nature (PPSN II), pp. 15–26 (1992)
[14] Neumann, F.: Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. Comput. Oper. Res. 35(9), 2750–2759 (2008) · Zbl 1144.90502
[15] Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Nat. Comput. 5(3), 305–319 (2006) · Zbl 1173.90535
[16] Scharnow, J., Tinnefeld, K., Wegener, I.: The analysis of evolutionary algorithms on sorting and shortest paths problems. J. Math. Model. Algorithms 3, 349–366 (2004) · Zbl 1073.68080
[17] Storch, T.: How randomized search heuristics find maximum cliques in planar graphs. In: Proceedings of the 8th AnnualGenetic and Evolutionary Computation Conference (GECCO 2006), pp. 567–574 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.