Since the early 1990s, genetic programming (GP)-a discipline whose goal is to enable the automatic generation of computer programs-has emerged as one of the most promising paradigms for fast, productive software development. GP combines biological metaphors gleaned from Darwin's theory of evolution with computer-science approaches drawn from the field of machine learning to create programs that are capable of adapting or recreating themselves for open-ended tasks. This unique introduction to GP provides a detailed overview of the subject and its antecedents, with extensive references to the published and online literature. In addition to explaining the fundamental theory and important algorithms, the text includes practical discussions covering a wealth of potential applications and real-world implementation techniques. Software professionals needing to understand and apply GP concepts will find this book an invaluable practical and theoretical guide.
Author(s): Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, Frank D. Francone
Series: The Morgan Kaufmann Series in Artificial Intelligence
Edition: 1st
Publisher: Morgan Kaufmann
Year: 1997
Language: English
Commentary: no pp.1,62-6,366
Pages: 490
Cover......Page 1
Title page......Page 3
Date-line......Page 4
Dedication......Page 5
Foreword by John R. Koza......Page 7
Contents......Page 11
Preface......Page 15
Acknowledgments......Page 19
I Prerequisites of Genetic Programming......Page 21
1 Genetic Programming as Machine Learning......Page 23
1.1 Motivation......Page 24
1.2 A Brief History of Machine Learning......Page 27
1.3 Machine Learning as a Process......Page 29
1.5.1 What Is the Problem Representation?......Page 32
1.5.2 Boolean Representations......Page 34
1.5.3 Threshold Representations......Page 37
1.5.4 Case-Based Representations......Page 39
1.5.5 Tree Representations......Page 40
1.5.6 Genetic Representations......Page 41
1.6.1 Generality/Specificity Operators......Page 43
1.6.3 Genetic Programming Operators......Page 44
1.7.1 Blind Search......Page 45
1.7.2 Hill Climbing......Page 46
1.7.3 Beam Search......Page 47
1.8 Learning......Page 48
1.9 Conclusion......Page 49
2 Genetic Programming and Biology......Page 53
2.2 Test Tube Evolution - A Study in Minimalist Evolution......Page 55
2.3 The Genetic Code - DNA as a Computer Program......Page 59
2.3.1 The DNA Alphabet......Page 60
2.3.2 Codons and Amino Acid Synthesis......Page 61
2.3.3 Polypeptide, Protein, and RNA Synthesis......Page 62
2.3.4 Genes and Alleles......Page 63
2.4 Genomes, Phenomes, and Ontogeny......Page 65
2.5.1 Stability in the Transmission of Genetic Material......Page 68
2.5.2 Genetic Variability......Page 69
2.5.3 Homologous Recombination......Page 70
2.6 Species and Sex......Page 73
3 Computer Science and Mathematical Basics......Page 77
3.1 The Importance of Randomness in Evolutionary Learning......Page 78
3.2.1 Combinatorics and the Search Space......Page 80
3.2.2 Random Numbers......Page 81
3.2.3 Probability......Page 83
3.3.1 The Turing Machine, Turing Completeness, and Universal Computation......Page 87
3.3.2 The Halting Problem......Page 89
3.3.3 Complexity......Page 90
3.4.1 Von Neumann Machines......Page 92
3.4.2 Evolvable Hardware......Page 95
3.5.1 Machine Language and Assembler Language......Page 96
3.5.2 Higher Languages......Page 97
3.5.3 Data Structures......Page 99
3.5.4 Manual versus Genetic Programming......Page 102
4 Genetic Programming as Evolutionary Computation......Page 107
4.1 The Dawn of Genetic Programming — Setting the Stage......Page 108
4.2 Evolutionary Algorithms: The General View......Page 111
4.3.1 Genetic Algorithms......Page 115
4.3.2 Evolutionary Strategies......Page 118
4.3.3 Evolutionary Programming......Page 120
4.3.4 Tree-Based GP......Page 121
4.4 Summary of Evolutionary Algorithms......Page 122
II Genetic Programming Fundamentals......Page 125
5 Basic Concepts — The Foundation......Page 127
5.1.1 The Terminal Set......Page 129
5.1.2 The Function Set......Page 130
5.1.3 Choosing the Function and Terminal Set......Page 131
5.2 Executable Program Structures......Page 132
5.2.1 Tree Structure Execution and Memory......Page 133
5.2.2 Linear Structure Execution and Memory......Page 134
5.2.3 Graph Structure Execution and Memory......Page 136
5.2.4 Structure as Convention......Page 137
5.3.1 Initializing Tree Structures......Page 138
5.3.2 The Ramped Half-and-Half Method......Page 139
5.3.3 Initializing GP Linear Structures......Page 140
5.4.1 Crossover......Page 142
5.4.2 Mutation......Page 145
5.5.1 The Fitness Function......Page 146
5.5.2 The Selection Algorithm......Page 149
5.6 The Basic GP Algorithm......Page 153
5.7 An Example Run......Page 155
6 Crossover - The Center of the Storm......Page 163
6.1 The Theoretical Basis for the Building Block Hypothesis in GP......Page 165
6.2.1 Crossover as a Disruptive Force......Page 168
6.2.2 Reproduction and Crossover......Page 170
6.3.1 The Effect of Crossover on the Fitness of Offspring......Page 171
6.3.2 The Relative Merits of Program Induction via Crossover versus Hill Climbing or Annealing......Page 173
6.3.3 Conclusions about Crossover as Macromutation......Page 175
6.4 Improving Crossover - The Argument from Biology......Page 176
6.5.1 Brood Recombination......Page 178
6.5.2 "Intelligent" Crossover......Page 181
6.5.3 Context-Sensitive Crossover......Page 182
6.5.4 Explicit Multiple Gene Systems......Page 183
6.5.5 Explicitly Defined Introns......Page 184
6.5.6 Modeling Other Forms of Genetic Exchange......Page 185
6.6 Improving Crossover - A Proposal......Page 186
6.7 Improving Crossover - The Tradeoffs......Page 189
6.8 Conclusion......Page 190
7 Genetic Programming and Emergent Order......Page 195
7.1 Introduction......Page 196
7.2 Evolution of Structure and Variable Length Genomes......Page 197
7.3 Iteration, Selection, and Variable Length Program Structures......Page 199
7.4.2 Finding Solutions of the Correct Length......Page 200
7.5 The Emergence of Introns, Junk DNA, and Bloat......Page 201
7.5.1 What Can We Learn from Biological Introns?......Page 203
7.6 Introns in GP Defined......Page 205
7.7 Why GP Introns Emerge......Page 207
7.8 Effective Fitness and Crossover......Page 208
7.9 Effective Fitness and Other Operators......Page 210
7.10 Why Introns Grow Exponentially......Page 211
7.11 The Effects of Introns......Page 214
7.11.1 Problems Caused by Introns......Page 215
7.11.2 Possible Beneficial Effects of Introns......Page 217
7.12.1 Reduction of Destructive Effects......Page 219
7.12.3 Changing the Fitness Function......Page 220
8 Analysis - Improving Genetic Programming with Statistics......Page 223
8.1.2 Basic Tools for Genetic Programming......Page 225
8.2 Offline Preprocessing and Analysis......Page 229
8.2.2 Feature Extraction......Page 230
8.2.3 Analysis of Input Data......Page 234
8.3.1 Measurement of Processing Effort......Page 236
8.3.2 Trait Mining......Page 238
8.4.2 Measurement of Online Data......Page 239
8.4.3 Survey of Available Online Tools......Page 240
8.5 Generalization and Induction......Page 249
8.5.1 An Example of Overfitting and Poor Generalization......Page 250
8.5.2 Dealing with Generalization Issues......Page 253
8.6 Conclusion......Page 255
III Advanced Topics in Genetic Programming......Page 257
9 Different Varieties of Genetic Programming......Page 259
9.1 GP with Tree Genomes......Page 260
9.2 GP with Linear Genomes......Page 263
9.2.1 Evolutionary Program Induction with Introns......Page 268
9.2.2 Developmental Genetic Programming......Page 270
9.2.3 An Example: Evolution in C......Page 274
9.2.4 Machine Language......Page 277
9.2.5 An Example: Evolution in Machine Language......Page 282
9.3.1 PADO......Page 285
9.3.2 Cellular Encoding......Page 286
9.4.1 STROGANOFF......Page 287
9.4.2 GP Using Context-Free Grammars......Page 290
9.4.3 Genetic Programming of L-Systems......Page 293
10 Advanced Genetic Programming......Page 297
10.1.2 Parallelization......Page 299
10.1.5 Stochastic Sampling......Page 300
10.2 Improving the Evolvability of Programs......Page 302
10.2.1 Modularization......Page 303
10.2.2 Automatically Defined Functions......Page 304
10.2.3 Encapsulation......Page 308
10.2.4 Module Acquisition......Page 309
10.2.5 Adaptive Representation......Page 310
10.2.6 Automatically Defined Macros......Page 311
10.2.7 Modules and Crossover......Page 312
10.2.8 Loops and Recursion......Page 313
10.2.9 Memory Manipulation......Page 314
10.2.10 Strongly Typed Genetic Programming......Page 318
10.3.1 Ontogeny......Page 319
10.3.2 Adaptive Parsimony Pressure......Page 322
10.3.4 Co-Evolution......Page 323
10.3.5 Hybrid Approaches......Page 325
11 Implementation — Making Genetic Programming Work......Page 329
11.1 Why Is GP so Computationally Intensive?......Page 330
11.1.1 Why Does GP Use so Much CPU Time?......Page 331
11.1.2 Why Does GP Use so Much Main Memory?......Page 332
11.2 Computer Representation of Individuals......Page 334
11.3.1 Lists and Symbolic Expressions......Page 336
11.3.2 The "How to" of LISP Implementations......Page 337
11.3.3 The Disadvantages of LISP S-Expressions......Page 338
11.4 Some Necessary Data Structures......Page 339
11.4.1 Arrays......Page 340
11.4.2 Linked Lists......Page 341
11.4.3 Stacks......Page 344
11.5.1 Postfix Expressions with a Stack......Page 345
11.5.2 Prefix Expressions with Recursive Evaluation......Page 347
11.5.3 A Graph Implementation of GP......Page 348
11.6.1 Evolving Machine Code with AIMGP......Page 350
11.6.2 The Structure of Machine Code Functions......Page 353
11.7 A Guide to Parameter Choices......Page 354
12 Applications of Genetic Programming......Page 359
12.2 Applications from A to Z......Page 360
12.3.1 Biochemistry Data Mining......Page 361
12.3.2 Sequence Problems......Page 367
12.3.3 Image Classification in Geoscience and Remote Sensing......Page 371
12.4.1 Cellular Encoding of Artificial Neural Networks......Page 374
12.4.2 Development and Evolution of Hardware Behaviors......Page 377
12.4.3 Intrusion Detection......Page 378
12.4.4 Autoparallelization......Page 379
12.4.5 Confidence of Text Classification......Page 380
12.4.6 Image Classification with the PADO System......Page 382
12.5.1 Online Control of Real Robot......Page 383
12.5.2 Spacecraft Attitude Maneuvers......Page 388
12.5.3 Hexapodal Robot......Page 390
12.5.4 Design of Electrical Circuits......Page 391
12.5.5 Articulated Figure Motion Animation......Page 393
12.6 Summary......Page 396
13 Summary and Perspectives......Page 399
13.1 Summary......Page 400
13.2 The Future of Genetic Programming......Page 401
13.3 Conclusion......Page 403
A.1 Books on Genetic Programming......Page 405
A.3 Books on Evolutionary Algorithms......Page 406
A.4 Selected Journals......Page 407
B.3 GP Bibliographies......Page 409
B.6 Mailing Lists......Page 410
C.1 Public Domain GP Systems......Page 413
C.4 C++ Implementation Issues......Page 414
D.2 Related Conferences and Workshops......Page 415
Bibliography......Page 419
Person Index......Page 465
Subject Index......Page 471
