Frontiers of Evolutionary Computation

Menon A.0792372212, 0306467623, 0792374606, 0792374665

Frontiers of Evolutionary Computation brings together eleven contributions by international leading researchers discussing what significant issues still remain unresolved in the field of Evolutionary Computation (EC). They explore such topics as the role of building blocks, the balancing of exploration with exploitation, the modeling of EC algorithms, the connection with optimization theory and the role of EC as a meta-heuristic method, to name a few. The articles feature a mixture of informal discussion interspersed with formal statements, thus providing the reader an opportunity to observe a wide range of EC problems from the investigative perspective of world-renowned researchers. These prominent researchers include:-Heinz Mühlenbein,-Kenneth De Jong,-Carlos Cotta and Pablo Moscato,-Lee Altenberg,-Gary A. Kochenberger, Fred Glover, Bahram Alidaee and Cesar Rego,-William G. Macready,-Christopher R. Stephens and Riccardo Poli,-Lothar M. Schmitt,-John R. Koza, Matthew J. Street and Martin A. Keane,-Vivek Balaraman,-Wolfgang Banzhaf and Julian Miller.Frontiers of Evolutionary Computation is ideal for researchers and students who want to follow the process of EC problem-solving and for those who want to consider what frontiers still await their exploration.

---

Table of contents :
Team DDU……Page 1
Contents……Page 6
List of Figures……Page 12
List of Tables……Page 14
Preface……Page 16
Contributing Authors……Page 18
1 Introduction……Page 26
2 Evolutionary computation and theories of evolution……Page 28
3 Darwin’s continental cycle conjecture……Page 30
4 The system view of evolution……Page 32
5 Von Neumann’s self-reproducing automata……Page 34
6 Turing’s intelligent machine……Page 36
7 What can be computed by an artificial neural network?……Page 38
8 Limits of computing and common sense……Page 39
9 A logical theory of adaptive systems……Page 41
10 The for creating artificial intelligence……Page 44
11.1 Von Neumann’s probabilistic logics……Page 45
11.2 The conditional probability computer……Page 46
11.3 Modern probabilistic logic……Page 47
12.1 The nonlinear voter model……Page 49
12.2 Stochastic analysis of one dimensional SCA……Page 51
13 Stochastic analysis of evolutionary algorithms……Page 52
13.2 Factorization of the distribution……Page 54
13.3 Holland’s schema analysis and the Boltzmann distribution……Page 56
15 Conclusion……Page 58
1 Introduction……Page 62
2 Historical Diversity……Page 63
3 The Challenge of Unification……Page 64
3.1.3 Parental Selection……Page 65
3.1.4 Reproduction and Inheritance……Page 66
3.3 Characteristics of Fitness Landscapes……Page 67
4.1 Representation and Morphogenesis……Page 69
4.4 Self-adapting Systems……Page 70
4.6 Inclusion of Lamarckian Properties……Page 71
5 Summary and Conclusions……Page 72
1 Introduction……Page 78
2 Challenge #1: Hard problems for the paradigm – Epistasis and Parameterized Complexity……Page 80
3 Challenge #2: Systematic design of provably good recombination operators……Page 83
4 Challenge #3: Using Modal Logic and Logic Programming methods to guide the search……Page 87
4.1 Example 1……Page 88
4.2 Example 2……Page 89
5 Challenge #4: Learning from other metaheuristics and other open challenges……Page 92
6 Conclusions……Page 94
4 Open Problems in the Spectral Analysis of Evolutionary Dynamics……Page 98
1 Optimal Evolutionary Dynamics for Optimization……Page 101
1.2 Spectral Conditions for Rapid First Hitting Times……Page 103
1.3 Rapid Mixing and Rapid First Hitting Times……Page 105
1.4 Some Analysis……Page 107
1.5 Transmission Matrices Minimizing……Page 110
2 Spectra for Finite Population Dynamics……Page 112
2.1 Wright-Fisher Model of Finite Populations……Page 113
2.2 Rapid First Hitting Time in a Finite Population……Page 115
3 Karlin’s Spectral Theorem for Genetic Operator Intensity……Page 117
3.1 Karlin’s Theorem illustrated with the Deceptive Trap Function……Page 118
3.2 Applications for an Extended Karlin Theorem……Page 120
3.3 Extending Karlin’s Theorem……Page 121
3.4 Discussion……Page 123
4 Conclusion……Page 124
5 Solving Combinatorial Optimization Problems via Reformulation and Adaptive Memory Metaheuristics……Page 128
1 Introduction……Page 129
2 Transformations……Page 130
3 Examples……Page 131
4.1 Tabu Search Overview……Page 133
5 Computational Experience……Page 134
6 Summary……Page 135
1 Introduction……Page 140
2 Foundations……Page 141
3 Connections……Page 145
4 Applications……Page 150
5 Conclusions……Page 152
7 EC Theory – “In Theory”……Page 154
8 Asymptotic Convergence of Scaled Genetic Algorithms……Page 182
1.1 Scalars and vectors……Page 187
1.2 Matrices and operator norms……Page 188
1.3 Stochastic matrices……Page 189
1.4 Creatures and populations……Page 192
2 The Genetic Operators……Page 193
2.1 Multiple-spot mutation……Page 194
2.2 Single-cutpoint regular crossover……Page 196
2.3 The fitness function and selection……Page 199
3.1 The drive towards uniform populations……Page 202
3.2 Weak ergodicity……Page 204
3.3 Strong ergodicity……Page 205
3.4 Convergence to global optima…….Page 207
3.5 The Vose-Liepins version of mutation-crossover……Page 211
4.1 Towards finite-length analysis on finite-state machines……Page 212
4.2 Estimates for finite-length genetic algorithms à la Catoni……Page 213
4.4 Further analogy with simulated annealing: parallelism and sparse mutation……Page 214
4.5 Analysis from inside-out and outside-in……Page 215
4.6 Non-monotone and self-adapting annealing sequences……Page 216
5 Appendix – Proof of some basic or technical results……Page 217
9 The Challenge of Producing Human-Competitive Results by Means of Genetic and Evolutionary Computation……Page 226
2 Definition of Human-Competitiveness……Page 227
3.1 Utility……Page 228
3.3 Complexity……Page 229
4 Human-Competitiveness as a Compass for Theoretical Work……Page 231
6 Promising Application Areas for Genetic and Evolutionary Computation……Page 232
7 Acknowledgements……Page 233
1 Introduction……Page 236
2 Case-Based Reasoning……Page 238
3 Case Memory as an Evolutionary System……Page 241
3.1.2 Environment……Page 242
3.1.3 Generate Solution……Page 243
3.3 Discussion……Page 244
4 Hybrid Systems……Page 249
4.1 Type A – CBR as a memory, EA as the optimizer……Page 250
4.2 Type B – EA as CBR System Parameter Optimizers……Page 251
4.3 Discussion……Page 252
5.1 Schemas……Page 254
5.2 A brief aside on levels of higher expertise……Page 256
5.3 Towards memory based reasoning……Page 257
5.3.1 C-Schemas as Building Blocks……Page 258
6 Conclusions……Page 262
11 The Challenge Of Complexity……Page 268
1 GP Basics and State of the Art……Page 270
2 The Situation in Biology……Page 273
3 Nature’s way to deal with complexity……Page 274
4 What we can learn from Nature?……Page 279
5 A possible scenario: Transfer into Genetic Programming……Page 281
6 Conclusion……Page 283
Author Index……Page 286
Index……Page 292