You are here

Evolutionary Computation for Modeling and Optimization

Daniel Ashlock
Publisher: 
Springer Verlag
Publication Date: 
2006
Number of Pages: 
571
Format: 
Hardcover
Price: 
79.95
ISBN: 
0-387-22196-4
Category: 
Textbook
We do not plan to review this book.

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