An ACO algorithm for the shortest common supersequence problem
René Michel, Martin Middendorf · 1999
Introduction In this chapter we describe how to apply the ACO meta-heuristic to a well known string problem, namely the Shortest Common Supersequence (SCS) problem. The algorithmic solution of string problems is an important and intensively investigated area of computer science. One reason for this is that many objects or processes in nature can be described in an abstract way by a string of characters. An important example is the genetic information of living creatures which is stored basically in large DNA molecules. These molecules are long sequences formed by four dierent elements called nucleotides. Hence DNA molecules can be viewed as a string over a four symbol alphabet. Another example comes from mechanical engineering. In this context a product is represented by the series of operations applied to it during the construction process. An important string problem in these areas is to nd for a given set of strings a string that can serve as a good representative for th