Genetic algorithms, principles and perspectives: a guide to GA theory

Colin R. Reeves, Jonathan E. Rowe1402072406, 9781402072406, 9780306480508

Genetic Algorithms (GAs) have become a highly effective tool for solving hard optimization problems. As their popularity has increased, the number of GA applications has grown in more than equal measure. Genetic Algorithm theory, however, has not kept pace with the growing use and application of GAs. Most book-length treatments of GAs provide only a cursory discussion of theory and this discussion primarily focuses on the traditional view, which depends heavily on the concept of a “schema”. Genetic Algorithms: Principles and Perspectives: A Guide to GA Theory is a survey of some important theoretical contributions, many of which have been proposed and developed in the Foundations of Genetic Algorithms series of workshops. However, this theoretical work is still rather fragmented, and the authors believe that it is the right time to provide the field with a systematic presentation of the current state of theory in the form of a set of theoretical perspectives. The authors do this in the interest of providing students and researchers with a balanced foundational survey of some recent research on GAs. The scope of the book includes chapter-length discussions of Basic Principles, Schema Theory, “No Free Lunch”, GAs and Markov Processes, Dynamical Systems Model, Statistical Mechanics Approximations, Predicting GA Performance, Landscapes and Test Problems. The authors have worked hard to make the book as accessible as possible for students and researchers. An undergraduate-level mathematical understanding of linear algebra and stochastic processes is assumed. For those readers who have not encountered GAs before, a comprehensive survey of GA concepts is provided and the variety of ways in which GAs can be implemented is outlined. Exercises are provided at the ends of the chapters with the express purpose of aiding understanding of the concepts discussed and to whet the reader’s appetite for pursuing theoretical research in GAs.

---

Table of contents :
Front cover……Page 1
Series……Page 2
Title page……Page 3
Date-line eBook……Page 4
Contents……Page 5
Preface……Page 9
About the Authors……Page 11
1.1 Historical Background……Page 13
1.2 Optimization……Page 16
1.3 Why GAs? Why Theory?……Page 21
1.4 Bibliographic Notes……Page 29
2.2 Representation……Page 31
2.3 The Elements of a Genetic Algorithm……Page 37
2.4 Illustrative Example……Page 61
2.5 Practical Considerations……Page 63
2.6 Special Cases……Page 67
2.7 Summary……Page 71
2.8 Bibliographic Notes……Page 72
3.1 Schemata……Page 77
3.2 The Schema Theorem……Page 80
3.3 Critiques of Schema-Based Theory……Page 86
3.4 Surveying the Wreckage……Page 90
3.5 Exact Models……Page 96
3.6 Walsh Transforms and deception……Page 98
3.7 Conclusion……Page 102
3.8 Bibliographic Notes……Page 103
4.1 Introduction……Page 107
4.2 The Theorem……Page 108
4.3 Developments……Page 115
4.4 Revisiting Algorithms……Page 118
4.5 Conclusions……Page 120
4.6 Bibliographic Notes……Page 121
5.1 Introduction……Page 123
5.2 Limiting Distribution of the Simple GA……Page 130
5.3 Elitism and Convergence……Page 134
5.4 Annealing the Mutation Rate……Page 139
5.5 Calculating with Markov Chains……Page 142
5.6 Bibliographic Notes……Page 150
6.1 Population Dynamics……Page 153
6.2 Selection……Page 157
6.3 Mutation……Page 163
6.4 Crossover……Page 170
6.5 Representational Symmetry……Page 175
6.6 Bibliographic Notes……Page 181
7.1 Approximating GA Dynamics……Page 185
7.2 Generating Functions……Page 188
7.3 Selection……Page 191
7.4 Mutation……Page 195
7.5 Finite Population Effects……Page 202
7.6 Crossover……Page 204
7.7 Bibliographic Notes……Page 209
8.1 Introduction……Page 213
8.2 Epistasis Variance……Page 214
8.3 Davidor’s Methodology……Page 215
8.4 An Experimental Design Approach……Page 216
8.5 Walsh representation……Page 219
8.6 Other related measures……Page 227
8.7 Reference classes……Page 233
8.8 General Discussion……Page 235
8.9 Bibliographic Notes……Page 240
9.1 Introduction……Page 243
9.2 Mathematical Characterization……Page 249
9.3 Onemax Landscapes……Page 258
9.4 Long Path Landscapes……Page 265
9.5 Local Optima and Schemata……Page 268
9.6 Path Tracing GAs……Page 271
9.7 Bibliographic Notes……Page 273
10.1 The Demise of the Schema Theorem……Page 277
10.2 Exact Models and Approximations……Page 280
10.3 Landscapes, Operators and Free Lunches……Page 285
10.4 The Impact of Theory on Practice……Page 286
10.5 Future research directions……Page 290
10.6 The Design of Efficient Algorithms……Page 297
A.1 Unitation……Page 299
A.4 Royal Road……Page 300
A.6 Deceptive functions……Page 302
A.7 Long paths……Page 303
A.9 $l,theta$ functions……Page 304
Bibliography……Page 307
Index……Page 339
Back cover……Page 345