Representations for Genetic and Evolutionary Algorithms

One of the major challenges for researchers in the field of management science, information systems, business informatics, and computer science is to develop methods and tools that help organizations, such as companies or public institutions, to fulfill their tasks efficiently. However, during the last decade, the dynamics and size of tasks organizations are faced with has changed. Firstly, production and service processes must be reorganized in shorter time intervals and adapted dynamically to the varying demands of markets and customers. Although there is continuous change, organizations must ensure that the efficiency of their processes remains high. Therefore, optimization techniques are necessary that help organizations to reorganize themselves, to increase the performance of their processes, and to stay efficient. Secondly, with increasing organization size the complexity of problems in the context of production or service processes also increases. As a result, standard, traditional, optimization techniques are often not able to solve these problems of increased complexity with justifiable effort in an acceptable time period. Therefore, to overcome these problems, and to develop systems that solve these complex problems, researchers proposed using genetic and evolutionary algorithms (GEAs). Using these nature-inspired search methods it is possible to overcome some limitations of traditional optimization methods, and to increase the number of solvable problems. The application of GEAs to many optimization problems in organizations often results in good performance and high quality solutions.

In this second chapter, we present an introduction into the field of representations for genetic and evolutionary algorithms. The chapter provides the basis and definitions which are essential for understanding the content of this work.

In this chapter, we study an often ignored aspect of heuristic optimization, namely the theory of representations for genetic and evolutionary algorithms. Although the importance of choosing proper representations for the performance of genetic and evolutionary algorithms is already recognized (Caruana and Schaffer 1988; Goldberg 1989c; Liepins and Vose 1990; Ronald et al. 1995; Radcliffe 1991a; Coli and Palazzari 1995b; Ronald 1997; Albuquerque et al. 2000; Kargupta 2000a; Schnier and Yao 2000; Hinterding 2000), we are still far from a complete theory of representations.

Over the last decades, researchers gained more and more knowledge about the principles of genetic and evolutionary algorithms (GEAs) and were able to formulate a theory describing the behavior of GEAs more precisely (Bäck et al. 1997; Vose 1999; Goldberg 2002; Reeves and Rowe 2003). The existing elements of GEA theory explain quite accurately the influence of many important GEA parameters, as well as selection, recombination, or mutation methods on the performance of GEAs. By using the existing GEA theory, straight forward design and the development of new, competent GAs (Goldberg et al. 1993; Harik and Goldberg 1996; Pelikan et al. 1999; Pelikan et al. 1999) became possible. However, concerning representations for GEAs, a framework which describes the influence of representations on the performance of GEAs is still missing, although it is well known that the used representation has a strong influence on GEA performance. Such a framework could help us to develop new representations in a more theory-guided manner and would be an important step towards a general theory of representations for GEAs.

In the previous chapter, we presented a framework which describes the effects of representations on the performance of GEAs. We illustrated the elements of the framework for problems where the phenotypes and genotypes are both bitstrings. The question is still open as to whether the framework also holds true for problems where the genotypes and phenotypes are different.

In the previous chapter, we illustrated that our framework modeling the influence of representations on the performance of GEAs not only works for binary phenotypes, but also for problems where the phenotypes are integers. However, it is possible to go one step further and to look at problems where the phenotypes and genotypes are completely different. One example for these types of problems are tree optimization problems. Trees are special types of graphs. Representations for trees must incorporate the additional restriction of a graph to be a tree. Therefore, if the genotypes are strings, there is a large semantic gap between tree structures (phenotypes) and strings (genotypes). In contrast to general network problems, where a representation simply has to indicate which links are used for the graph, no natural or intuitive “good” tree representations exist which are accessible for GEAs. As a result, researchers have proposed a variety of different tree representations with different properties. However, up till now no theory-based analysis exists about how GEA performance is influenced by the different types of tree representations.

When using GEAs for tree problems it is necessary to encode a solution (tree) such that evolutionary search operators like crossover or mutation can be applied. There are two different possibilities for doing this: indirect representations usually encode a tree (phenotype) as a list of strings (genotypes) and apply standard search operators to the genotypes. The phenotype is constructed by an appropriate genotype-phenotype mapping (representation). As seen in the previous chapter, there are many indirect representations for trees such as NetKeys, the LNB encoding, the CV encoding, or Prüfer numbers.

In the previous chapters, the presented theory about representations was used for the analysis and design of representations as well as search operators. The investigations into the properties of representations were based on theory and helped us to understand what happens when GEAs use a specific representation. However, in practice, GEA users are often less interested in theory about representations but want simple instruments for a quick and rough prediction of the expected performance of a representation. They have several representations at hand and want to know which representation they should choose for their problem. We do not want to leave them alone with their problems, but illustrate how they can advantageously use the proposed theory.

The purpose of this book is to understand the influence of representations on the performance of genetic and evolutionary algorithms. This chapter summarizes the work contained in this study and lists its major contributions.