Representations for Genetic and Evolutionary Algorithms

Dr. Franz Rothlauf

Springer, Heidelberg New York

1st ed. 2002. 2nd printing 2003,
289 p. 152 illus. Hardcover
ISBN: 3-540-00610-9

2nd edition 2006,
325 p. 99 illus., Hardcover
ISBN: 3-540-25059-X

 

About the book

In the field of genetic and evolutionary algorithms (GEAs), a large amount of theory and empirical study has been focused on operators and test problems, while problem representation has often been taken as given. This book breaks with this tradition and provides a comprehensive overview on the influence of problem representations on GEA performance.
The book summarizes existing knowledge regarding problem representations and describes how basic properties of representations, such as redundancy, scaling, or locality, influence the performance of GEAs and other heuristic optimization methods. Using the developed theory, representations can be analyzed and designed in a theory-guided matter. The theoretical concepts are used for solving integer optimization problems and network design problems more efficiently.
The book is written in an easy-readable style and is intended for researchers, practitioners, and students who want to learn about representations. The second edition extends the analysis of the basic properties of representations and introduces a new chapter on the analysis of direct representations.

Advance Praise for Representations for Genetic and Evolutionary Algorithms

" Franz's decomposition of the problem into issues of redundancy, scaling, and correlation is itself a contribution. [...] The analysis of redundancy and scaling are examples of applicable or facetwise modeling at its best. Franz gets a key issue on run duration and population size though bounding analyses, and thesse permit him to draw definite conclusions in fields where so many other researchers have simply waived their arms. [...] All this would be enough for me to recommend this book to GEA aficionados around the globe, but I hasten to add that the book ist remarkably well written and well organized. No doubt, this rhetorical cranftsmanship will help broaden the appeal of the book beyond the key genetic algorithmists and computational evolutionaries. In short, I recommend this important book to anyone interested in a better quantitative and qualitative understanding of the representation problem. Buy this book, read it, and use its important methodological, theoretical, and practical lessons on a daily basis."

David E. Goldberg
University of Illinois at Urbana-Champaign

Reviews of the book

"...Overall, Representations for Genetic and Evolutionary Algorithms is both informative and enjoyable to read. A sound mathematical background is required to understand the theoretical models described in the book but the author does a good job to ensure that they are not daunting. The book is suitable for those with experience in GEA design and for the newcomer." Jon Rigelsford, The Industrial Robot 30(2), p. 194, Emerald, Bedford, 2003.

 

"...This book aims to present a theory of representations for genetic and evolutionary algorithms (GEA). Although it is not intended as an introduction to the area of GEAs, it is an excellent guide for those already familiar with the area. As with other search heuristics, using GEAs can sometimes feel more like an art than a science. This is largely due to a lack of practicable theory for successfully using GEAs. One is faced with a bewildering set of choices, such as selection strategy, choice of genetic operators, crossover and mutation rates. Those who have previously used GEAs will appreciate the effect that these parameters have on the quality of the solution identified... A large number of test problems are used to illustrate the theory, including those from the real world. Overall, the book is well written and is sensibly structured. It is a book for the specialist researcher. For nonspecialists, it is likely to prove too technical. Considerable space is given to show how representation theory may be applied to real problems. The two examples are well chosen and provide sufficient depth to test the theory. The binary representation of integers is an example that is both simple but challenging. The chapters on spanning trees will be of particular interest to those working with network problems." E. Thompson and David Smith, Journal of the Operational Research Society 54(1),
pp. 1112-1113, Palgrave, England, 2003.

 

"... As any book, the present one has advantages as well as disadvantages. I want to point to three advantages. Each chapter is started with a very informative introduction, wherein is explained what will be done next. This is accomplished by a short but comprehensive review of related literature. In general the reader has no problems to follow the ideas of the author and to understand the different steps toward a corresponding theory. Very helpful and informative is also the demonstration of the framework in various test and real-world problems. My critique is related to the design of the material, which could be improved. For instance, important terms should be introduced as a definition or at least written with bold letters. The same holds for described algorithms, which are mainly given without a name. Finally, some important terms are not explained in the text respectively not included in the index. The author remarks in the preface that “The book is designed for people who want to learn some theory about how representations in.uence GEA performance and for those who want to see how this theory can be applied. . . ” In my opinion the book achieves this purpose in an excellent way. However, who is not familiar to GEAs will have some problems to fully understand all specifics and details. For those it is recommended to read in advance one of the available textbooks on Genetic Algorithms or Evolutionary Optimization. To summarize, Rothlauf’s book is less suited for a first acquaintance with GEAs, but it is outstandingly suited to delve deeply into a special but highly interesting and important topic of GEAs." Peter Köchel, OR-Spektrum 26(1), pp. 147-148, Springer, Heidelberg, 2004.

 

About the author

Franz Rothlauf (M'98) received a Diploma in Electrical Engineering from the University of Erlangen, Germany, and a Ph.D. in Information Systems from the University of Bayreuth, Germany, in 1997, and 2001, respectively.

He is currently an Assistant Professor (Habilitant) at the Department of Information Systems, Mannheim Business School, Germany. He has published more than 40 technical papers in the context of evolutionary computation and co-edited several conference proceedings.

His main research interests are problem representations for heuristic search approaches especially evolutionary algorithms. For several years he was a visiting researcher at the Illinois Genetic Algorithm Laboratory (IlliGAL). He is a member of the Editorial Board of the journal Information Sciences and Evolutionary Computation Journal (ECJ).

He has been organizer of several workshops on representations issues, chair of EvoWorkshops in 2005 and 2006, co-organizer of the European workshop series on "Evolutionary Computation in Communications, Networks, and Connected Systems", topic chair for IEEE CEC 2005, and co-chair of the program commitee of the GA track at GECCO 2006.

Ordering

Order the book online from the publisher or amazon.de or amazon.com.

Table of Contents

0. Preface
1. Introduction
2. Representations for Genetic and Evolutionary Algorithms
3. Three Elements of a Theory of Genetic and Evolutionary Representations
3.1 Redundancy
3.2 Scaling
3.3 Locality
4. Time-Quality Framework for a Theory-Based Analysis and Design of Represenations
5. Analyses of Binary Respresentations of Integers
6. Analysis and Design of Representations for Trees
7. Analysis and Design of Search Operators for Trees
8. Performance of Genetic and Evolutionary Algorithms on Tree Problems
9. Summary and Conclusions
A. Optimal Communication Spanning Tree Test Instances

Detailed descriptions of OCST problems

You can download detailed descriptions of test instances for the optimal communication spanning tree problems from Berry, Murtagh, and McMahon "Applications of a genetic-based algorithm for optimal design of tree-structred communciation networks",1995, Palmer's PhD thesis about "An approach to a problem in network design using genetic algorithms", 1995, Raidl (personal communication), and Rothlauf here as zipped postscript and pdf. The description is part of the book Representations for genetic and evolutionary algorithms (Appendix A).

Other books which might be of interest: