Foundations of Genetic Algorithms: 8th International Workshop, FOGA 2005, Aizu-Wakamatsu City, Japan, January 5 - 9 , 2005, Revised Selected Papers

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