Skip to main content
main-content

Über dieses Buch

In the field of genetic and evolutionary algorithms (GEAs), much theory and empirical study has been heaped upon operators and test problems, but problem representation has often been taken as given. This monograph breaks with this tradition and studies a number of critical elements of a theory of representations for GEAs and applies them to the empirical study of various important idealized test functions and problems of commercial import. The book considers basic concepts of representations, such as redundancy, scaling and locality and describes how GEAs'performance is influenced. Using the developed theory representations can be analyzed and designed in a theory-guided manner. The theoretical concepts are used as examples for efficiently solving integer optimization problems and network design problems. The results show that proper representations are crucial for GEAs'success.

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract
One of the major duties of researchers in the field of management science, information systems, business informatics, and computer science is to develop methods and tools that should help organizations, such as companies or public institutions, to fulfill their jobs efficiently. However, during the last decade, the dynamics and size of the problems 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 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 the 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.
Franz Rothlauf

2. Representations for Genetic and Evolutionary Algorithms

Abstract
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.
Franz Rothlauf

3. Three Elements of a Theory of Genetic and Evolutionary Representations

Abstract
In this chapter, we study an often ignored aspect of genetic 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 (GEAs) is already recognized (Caruana & Schaffer, 1988; Goldberg, 1989c; Liepins & Vose, 1990; Ronald et al., 1995; Coli & Palazzari, 1995b; Ronald, 1997; Albuquerque et al., 2000; Kargupta, 2000a; Schnier & Yao, 2000; Hinterding, 2000), we are still far from a complete theory of representations.
Franz Rothlauf

4. Time-Quality Framework for a Theory-Based Analysis and Design of Representations

Abstract
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 (Goldberg, 1989c; Bäck, Fogel, & Michalewicz, 1997). 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, Deb, Kargupta, &Harik, 1993; Hank & Goldberg, 1996; Pelikan, Goldberg, & Cantú-Paz, 1999; Pelikan, Goldberg, & Lobo, 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.
Franz Rothlauf

5. Analysis of Binary Representations of Integers

Abstract
In the previous chapter we presented a framework which describes the effects of representations on the performance of GEAs. We verified 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 use different types of representations. This question can be answered by examining problems where the genotypes are still binary but the phenotypes are integers. Integer optimization problems are common in many real-world applications. Although the most natural way for representing integer problems is to use an integer representation, previous work has shown that by using representations with lower cardinality of the alphabet (for example binary representations) the possible number of schemata can be increased in comparison to integer strings (Goldberg, 1990b).
Franz Rothlauf

6. Analysis of Tree Representations

Abstract
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 the genotypes use completely different types of representations. One example for these type of problems are tree optimization problems. Trees are a special type of graph. Representations for trees must incorporate the additional restriction of a graph to be a tree. Therefore, if the genotypes are still binary strings, there is a large semantic gap between tree structures and bitstrings. 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.
Franz Rothlauf

7. Design of Tree Representations

Abstract
In the previous chapters, we have gained new insights into the theory of representations. As a result, we are able to predict, using the framework presented in chapter 4, the influence of redundant, exponentially scaled, or low locality representations on GEA performance. However, the presented framework can not only be used to analyze the performance of existing representations, but also to develop representations in a theory-guided manner.
Franz Rothlauf

8. Performance of Genetic and Evolutionary Algorithms on Tree Problems

Abstract
In the previous chapters, the presented theory about representations was mainly used for analysis and design of representations. 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 fast 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.
Franz Rothlauf

9. Summary, Conclusions and Future Work

Abstract
The purpose of this work was to understand the influence of representations on the performance of genetic and evolutionary algorithms. This chapter summarizes the work contained in this study, lists its major contributions, and points to some directions of further research.
Franz Rothlauf

A. Optimal Communication Spanning Tree Test Instances

Abstract
Searching the literature for standard test problems for the optimal communication spanning tree (OCST) problem reveals that many researchers use their private test problems which are mostly not published. As a result, the comparison of different search algorithms or representations is a difficult and time consuming task. It is not possible to check quickly if a new search method is better than the existing ones. Furthermore, applicants hesitate to use new and efficient search methods or representations if they can not be tested on a variety of different test problems and solve these problems well and reliably. Therefore, the building up of a collection of test instances for the OCST problem is necessary.
Franz Rothlauf

Backmatter

Weitere Informationen