This book constitutes the refereed proceedings of the 8th workshop on the foundations of genetic algorithms, FOGA 2005, held in Aizu-Wakamatsu City, Japan, in January 2005.
The 16 revised full papers presented provide an outstanding source of reference for the field of theoretical evolutionary computation including evolution strategies, evolutionary programming, and genetic programming, as well as the continuing growth in interactions with other fields such as mathematics, physics, and biology.
Author(s): Alden H. Wright, Michael D. Vose, Kenneth A. De Jong, Lothar M. Schmitt
Series: Lecture ... Computer Science and General Issues
Edition: 1
Publisher: Springer
Year: 2005
Language: English
Pages: 325
front-matter.pdf......Page 1
Title......Page 3
Preface......Page 5
Organization......Page 7
Table of Contents......Page 9
1 Introduction......Page 11
2 Binary Decision Diagrams......Page 13
3 A Genetic Algorithm for the Variable Ordering Problem......Page 16
4 Alternating Crossover......Page 18
5 Fitness Calculation via an Optimized Visiting Order......Page 20
6 Experimental Results......Page 23
7 Conclusion......Page 27
References......Page 28
1 Introduction......Page 31
2.1 Quad Search......Page 32
2.2 Observations on the Search Behavior of Quad Search......Page 35
2.3 Simple Binary Search for Real Valued Encodings......Page 36
3 Quasi-basins, Encodings and Locality......Page 37
4 Locality and Neighborhoods......Page 38
4.1 The Matrix M$^x$......Page 39
4.2 The Matrix ${\mathcal M}^x$......Page 40
4.3 Gray Codes and Quasi-basins......Page 41
5 Binary Codes and Quasi-basins......Page 43
6 Discussion......Page 44
7 Conclusions......Page 45
References......Page 46
1 Introduction......Page 47
2 Algorithms and Analytical Framework......Page 49
3 Limitations for Direct Transfers of Results......Page 51
4 Looking for Classes of Functions that Allow for a Transfer of Results......Page 58
5 Conclusions......Page 65
References......Page 66
1 Introduction......Page 68
3 How Does an Evolutionary Algorithm Work?......Page 69
4 Special Evolutionary Algorithms......Page 71
5 Summary of Previous Work......Page 74
6 Complexity of Deciding if a Given Search System Is Genetic......Page 78
References......Page 83
1 Introduction......Page 85
2 Indirect Induction of Search Distributions......Page 87
3 Estimation-of-Distribution......Page 89
4 Indirect Estimation-of-Distribution via Compression......Page 90
5 Compression EAs......Page 94
5.1 A L-System Compression GA......Page 95
6 Discussion......Page 101
References......Page 103
1 Introduction......Page 105
2 The Multiobjective Optimization Problem......Page 106
3.1 Evolutionary Algorithms......Page 107
3.2 The Simulated Annealing Algorithm......Page 108
3.3 Artificial Immune System......Page 110
4 Markov Chain Theory......Page 111
5 Main Results......Page 113
5.1 Convergence of Simulated Annealing......Page 114
5.2 Convergence of Evolutionary Algorithms......Page 116
5.3 Convergence of an Artificial Immune System Algorithm......Page 118
6 Conclusions and Future Work......Page 119
References......Page 120
1 Introduction......Page 122
2.2 Algorithms Analyzed......Page 124
3 Basic Definitions......Page 125
4 Algorithm......Page 127
5.1 Leading Ones Trailing Zeros......Page 129
5.2 Quadratic Function......Page 131
6.1 Linear Functions......Page 132
6.2 Knapsack Problem......Page 134
7 Analysis of REMO on Knapsack Problem......Page 136
References......Page 139
1 Introduction......Page 142
2 Coupon Collection and Tournament Selection......Page 145
3 Iterated Coupon Collector Problem......Page 147
4 Running Evolutionary Algorithms Efficiently......Page 151
5 Backward-Chaining Evolutionary Algorithms......Page 153
6 Experimental Results......Page 156
7 Discussion......Page 161
References......Page 164
1 Introduction......Page 166
2 General Framework......Page 167
3 Nonlinear Genetic Programming (GP) with Homologous Crossover......Page 169
4 The Statement of the Schema-Based Version of Geiringer's Theorem for Non-linear GP Under Homologous Crossover......Page 174
5 How Do We Obtain Theorem 32 from Theorem 6?......Page 178
References......Page 184
1 Introduction......Page 186
2 Conceptual Overview......Page 187
3 Differentiable Coarse Graining......Page 188
4 Proportional Selection + Mutation......Page 191
5 Binary Tournament Selection......Page 195
6 Ranking Selection......Page 197
7 Nonlinear Coarse Graining......Page 198
8 Conclusion......Page 200
References......Page 201
1 Introduction......Page 202
2 An Introduction to Genetic Dynamics......Page 203
3.1 Explicit Solutions......Page 206
3.2 Formal Solutions......Page 207
4 Perturbation Theory......Page 208
5.1 Perturbative Construction of Eigenvalues and Eigenvectors......Page 209
5.2 Diagrammatic Perturbative Construction of PI......Page 211
6.1 The Exact Solution......Page 217
6.2 Diagrammatic Perturbation Theory......Page 220
7 Perturbation Theory and the Renormalization Group......Page 221
8 Conclusions......Page 223
References......Page 224
1 Introduction......Page 225
2.1 Weighted Multirecombination Evolution Strategies......Page 227
2.2 The Sphere Model......Page 228
3.1 Determining the Quality Gain......Page 231
3.2 Optimal Parameter Settings......Page 233
4 Noise......Page 235
5 Cumulative Step Length Adaptation......Page 239
6 Summary and Conclusions......Page 244
References......Page 246
1 Introduction......Page 248
2 Evolution Criteria and Steady State......Page 249
3 How to Calculate the Final Fitness Error......Page 251
3.1 The Biquadratic Case......Page 252
3.2 $L_1$-Norm Case......Page 258
4 Conclusions and Outlook......Page 263
5.1 Final Fitness Error of Function $F_2(y)= - um^N_{i=1} |y_i|$......Page 265
References......Page 268
1 Introduction......Page 270
The Algorithm......Page 272
The Function Scenario......Page 273
2 Preliminaries......Page 275
3 Gain in a Single Step......Page 276
4 Multi-step Behavior......Page 280
5 Conclusion......Page 284
A Proof of Lemma 2......Page 285
B Proof of Lemma 4......Page 287
C Proof of Lemma 5......Page 289
References......Page 290
1 Introduction......Page 292
2 Background......Page 293
3.1 Algorithm......Page 294
3.2 Example......Page 296
4.1 Simplification......Page 297
4.2 Sub-population Sizing......Page 299
4.3 Overall Population Sizing......Page 300
4.4 Overall Complexity......Page 301
5 Experiments: Population Size, String Length and Success Ratio......Page 302
6.1 Population Sizing of Simple GAs......Page 305
6.3 Population Sizing of EDAs......Page 306
6.4 Discussions......Page 307
References......Page 308
1 Introduction......Page 310
2.1 Definition......Page 311
2.2 Properties of a Critical Value......Page 313
3.1 A Monomial Having Deception About a Variable......Page 317
3.2 The Deceptive Degree of a Function......Page 319
3.4 Applications of the Deceptive Degree......Page 320
4 Goldberg's Minimal Deceptive Problem (MDP)......Page 321
6 Summary......Page 322
References......Page 323
back-matter.pdf......Page 325
