Contents
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VII
1 An Overview of Evolutionary Computation . . . . . . . . . . . . . . . . 1
1.1 Examples of Evolutionary Computation . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Predators Running Backward . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Wood-Burning Stoves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Hyperspectral Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.4 A Little Biology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Evolutionary Computation in Detail . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.1 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.2 Evolution and Coevolution . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2.3 A Simple Type of Evolutionary Computation . . . . . . . . . 22
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.3 Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2 Designing Simple Evolutionary Algorithms . . . . . . . . . . . . . . . . 33
2.1 Models of Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2 Types of Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.4 Population Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.5 A Nontrivial String Evolver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.6 A Polymodal String Evolver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.7 The Many Lives of Roulette Selection . . . . . . . . . . . . . . . . . . . . . . 60
XVI Evolutionary Computation for Modeling and Optimization
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3 Optimizing Real-Valued Functions . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.1 The Basic Real Function Optimizer . . . . . . . . . . . . . . . . . . . . . . . . 69
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.2 Fitness Landscapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.3 Niche Specialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.4 Path Length: An Extended Example . . . . . . . . . . . . . . . . . . . . . . . 88
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.5 Optimizing a Discrete-Valued Function: Crossing Numbers. . . . 92
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4 Sunburn: Coevolving Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.1 Definition of the Sunburn Model . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.2 Implementing Sunburn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.3 Discussion and Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.4 Other Ways of Getting Burned . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5 Small Neural Nets : Symbots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.1 Basic Symbot Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.2 Symbot Bodies and Worlds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.3 Symbots with Neurons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.4 Pack Symbots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6 Evolving Finite State Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.1 Finite State Predictors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.2 Prisoner’s Dilemma I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.2.1 Prisoner’s Dilemma Modeling the Real World . . . . . . . . . 153
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.3 Other Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Contents XVII
7 Ordered Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.1 Evolving Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.2 The Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.3 Packing Things . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
7.4 Costas Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
8 Plus-One-Recall-Store . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
8.1 Overview of Genetic Programming. . . . . . . . . . . . . . . . . . . . . . . . . 209
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
8.2 The PORS Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
8.3 Seeding Populations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
8.4 Applying Advanced Techniques to PORS . . . . . . . . . . . . . . . . . . . 226
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
9 Fitting to Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
9.1 Classical Least Squares Fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
9.2 Simple Evolutionary Fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
9.3 Symbolic Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
9.4 Automatically Defined Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 253
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
9.5 Working in Several Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
9.6 Introns and Bloat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
10 Tartarus: Discrete Robotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
10.1 The Tartarus Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
10.2 Tartarus with Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . 272
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
10.3 Adding Memory to the GP language . . . . . . . . . . . . . . . . . . . . . . . 279
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
10.4 Tartarus with GP Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Genetic Operations on GP automata . . . . . . . . . . . . . . . . . . . . . . . 284
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
10.5 Allocation of Fitness Trials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
XVIII Evolutionary Computation for Modeling and Optimization
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
11 Evolving Logic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
11.1 Artificial Neural Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
11.2 Evolving Logic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
11.3 Selecting the Net Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
11.4 GP Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
12 ISAc List: Alternative Genetic Programming . . . . . . . . . . . . . . 319
12.1 ISAc Lists: Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
Done?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
Generating ISAc Lists, Variation Operators . . . . . . . . . . . . . . . . . 323
Data Vectors and External Objects . . . . . . . . . . . . . . . . . . . . . . . . 323
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
12.2 Tartarus Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
12.3 More Virtual Robotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
12.4 Return of the String Evolver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
13 Graph-Based Evolutionary Algorithms. . . . . . . . . . . . . . . . . . . . . 349
13.1 Basic Definitions and Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
13.2 Simple Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
13.3 More Complex Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
13.4 Genetic Programming on Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 372
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
14 Cellular Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
14.1 Shape Evolution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
14.2 Cellular Encoding of Finite State Automata . . . . . . . . . . . . . . . . 389
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
14.3 Cellular Encoding of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
14.4 Context Free Grammar Genetic Programming. . . . . . . . . . . . . . . 413
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
Contents XIX
15 Application to Bioinformatics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
15.1 Alignment of Transposon Insertion Sequences . . . . . . . . . . . . . . . 425
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
15.2 PCR Primer Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
15.3 DNA Bar Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
15.4 Visualizing DNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
15.5 Evolvable Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
A Example Experiment Report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
B Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
B.1 Basic Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
B.1.1 Choosing Things and Binomial Probability . . . . . . . . . . . 522
B.1.2 Choosing Things to Count . . . . . . . . . . . . . . . . . . . . . . . . . . 523
B.1.3 Two Useful Confidence Intervals . . . . . . . . . . . . . . . . . . . . . 527
B.2 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
C A Review of Calculus and Vectors . . . . . . . . . . . . . . . . . . . . . . . . . 537
C.1 Derivatives in One Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
C.2 Multivariate Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
C.3 Lamarckian Mutation with Gradients . . . . . . . . . . . . . . . . . . . . . . 542
C.4 The Method of Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
D Combinatorial Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
D.1 Terminology and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
D.2 Coloring Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
D.3 Distances in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
D.4 Traveling Salesman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
D.5 Drawings of Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559