Improved heuristics and a genetic algorithm for finding short supersequences

被引：24

作者：

Branke J. ^{[1
]}

Middendorf M. ^{[1
]}

Schneider F. ^{[1
]}

机构：

[1] Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe

来源：

Operations-Research-Spektrum | 1998年 / 20卷 / 1期

关键词：

Genetic algorithms; Heuristics; Supersequences;

D O I：

10.1007/BF01545528

中图分类号：

学科分类号：

摘要：

In this paper several heuristics and a genetic algorithm (GA) are described for the Shortest Common Supersequence (SCS) problem, an NP-complete problem with applications in production planning, mechanical engineering and data compression. While our heuristics show the same worst case behaviour as the classical Majority Merge heuristic (MM) they outperform MM on nearly all our test instances. We furthermore present a genetic algorithm based on a slightly modified version of one of the new heuristics. The resulting GA/heuristic hybrid yields significantly better results than any of the heuristics alone, though the running time is much higher. © Springer-Verlag 1998.

引用

页码：39 / 45

页数：6

共 11 条

[1]

Branke, J., Kohlmorgen, U., Schmeck, H., Veith, H., Steuerung einer Heuristik zur Losgrößenplanung unter Kapazitätsrestriktionen mit Hilfe eine parallelen genetischen Algorithmus (1995) Tagungsband Zum Workshop Evolutionäre Algorithmen in Management Anwendungen., pp. 21-31. , Kühl J, Nissen V (Hrsg) Universität Göttingen, Institut für Wirtschaftsinformatik

[2]

Foulser, D.E., Yang, Q., Li, M., Theory and algorithms for plan merging (1992) Artificial Intelligence, 57, pp. 143-181

[3]

Fraser, C.B., Irving, R., Approximation algorithms for the shortest common supersequence (1995) Nordic Journal on Computing, 2, pp. 303-325

[4]

Fraser, C.B., (1995) Subsequences and Supersequences., , PhD thesis, University of Glasgow, Department of Computer Science

[5]

Haase, K., Kohlmorgen, U., Parallel genetic algorithm for the capacitated lot-sizing problem (1996) Operations Research Proceedings., pp. 370-375. , Kleinschmidt et al. (eds) Springer, Berlin Heidelberg New York

[6]

Jiang, T., Li, M., On the approximation of shortest common supersequences and longest common subsequences (1995) SIAM J Comput, 24, pp. 1122-1139

[7]

Maier, D., The complexity of some problems on subsequences and supersequences (1978) J ACM, 25, pp. 322-336

[8]

Middendorf, M., More on the complexity of common superstring and supersequence problems (1994) Theoret Comput Sci, 125, pp. 205-228

[9]

Räihä, K.-J., Ukkonen, E., The shortest common supersequence problem over binary alphabet is NP-complete (1981) Theoret Comput Sci, 16, pp. 187-198

[10]

Ross, P., (1994) About PGA V2.7., , University of Edinburgh

← 1 2 →