建模和最优化的进化计算技术,Evolutionary Computation for Modeling and Optimization,Daniel Ashlock,2006 Springer,578页,全英文,共15章
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
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