Foundations of Genetic Algorithms 1991 (FOGA 1) (eBook)

Front Cover 1
Foundations of Genetic Algorithms 4
Copyright page 5
Table of Contents 6
Introduction 8
1 A Short Introduction to Genetic Algorithms 9
2 Definitions and Assumptions 10
3 Metrics 13
4 Search Algorithms 14
References 17
PART I: GENETIC ALGORITHM HARDNESS 18
Chapter 1. The Nonuniform Walsh-Schema Transform 20
Abstract 20
1 Introduction 20
2 Definition of the Nonuniform Walsh-Schema Transform 21
3 Relationship to the Hyperplane Transform 23
4 Conclusions 28
Acknowledgments 29
References 29
Chapter 2. Epistasis Variance: A Viewpoint on GA-Hardness 30
Abstract 30
1 Background 30
2 Notional epistasis in GAs 31
3 The basic elements of epistasis 32
4 Calculating epistasis: A few examples 35
5 Conclusions and future work 40
Acknowledgments 40
References 41
Chapter 3. Deceptiveness and GeneticAlgorithm Dynamics 43
Abstract 43
1 Introduction 43
2 Embedding, Representation and Deceptiveness 46
3 GAs as Dynamic Systems 51
4 Summary 54
References 54
PART 2: SELECTION AND CONVERGENCE 58
Chapter 4. An Extension To the Theory of Convergence and a Proof of the 
60 
Abstract 60
1. Introduction and Background 60
2. The Solution of the Recurrence Relation By Inspection and 
63 
3. The Recurrence Relation for Convergence for Nonbinary 
67 
4. The Solution for the Time to Convergence tc for Binary and 
70 
5. Examples and Extensions 73
6. Conclusions 74
References 75
Chapter 5. A Comparative Analysis of Selection Schemes 
76 
Abstract 76
1 Introduction 76
2 Selection: A Matter of Birth, Life, and Death 77
3 Proportionate Reproduction 78
4 Ranking Selection 83
5 Tournament Selection 85
6 Genitor 89
7 Selection Procedures Head to Head 92
8 Selection: What Should We Be Doing 94
9 Conclusions 97
Acknowledgments 98
References 98
Chapter 6. A Study of Reproduction in Generational and Steady-State 
101 
Abstract 101
1 INTRODUCTION 101
2 Ideal Reproductive Performance 102
3 Actual Behavior 103
4 Discussion 106
References 107
Chapter 7. Spurious Correlations and Premature Convergence 
109 
Abstract 109
1 Introduction 110
2 Schema Sampling Theory and Sampling Error 110
3 Empirical Evidence 112
References 118
PART 3: CLASSIFIER SYSTEMS 120
Chapter 8. Representing Attribute-Based Concepts 
122 
Abstract 122
1 Introduction 122
2 Standard Binary Encodings 123
3 More Expressive Encodings 126
4 Discussion 132
Acknowledgement 133
References 133
Chapter 9. Quasimorphisms or Queasymorphisms? 
135 
Abstract 135
1 Introduction 135
2 Row Stochastic Matrices1 138
3 State Values 140
4 The Bucket Brigade 142
5 Payoffs That Are Not Fixed 145
6 Model State Values 145
7 Some Homomorphic Images 145
8 Decomposition 147
9 The First Component as a Homomorphic Image 148
10 The First Component as a Model, Using Bucket 
150 
11 The Equipayoff Homomorphism 152
12 Queasymorphic Images 153
13 Conclusion and Disclaimer 154
References 154
Chapter 10. Variable Default Hierarchy Separation 
155 
Abstract 155
1 Introduction 156
2 The Importance of Default Hierarchies in LCSs 156
3 Formal Definitions 157
4 Ideal Default-Exception Pairs and Fixed Separation 161
5 The Necessity Auction 164
6 Separate Priority Factors 167
7 General Default-Exception Pairs 168
8 Final Comments 173
Acknowledgments 174
References 174
PART 4: CODING AND REPRESENTATION 176
Chapter 11. Hierarchical Approach to Learning the Boolean 
178 
ABSTRACT 178
1. Introduction and Overview 178
2. Background 178
3. Background on Genetic Programming Paradigm 179
4. Boolean 11-Multiplexer Function 182
5· Hierarchies and Default Hierarchies 194
6. Non-Randomness of Results 195
7. Conclusions 197
References 198
Chapter 12. A Grammar-Based Genetic Algorithm 200
ABSTRACT 200
1 Introduction 200
2 A Recapitulation of the Foundations of the GA 201
3 GA Limitations in Structured Domains 203
4 A Grammar-Based GA 205
5 Previous Approaches, Future Directions 209
References 210
Chapter 13. Genetic Algorithms for Real Parameter 
212 
Abstract 212
1 Introduction 212
2 Background 213
3. Binary Coding and Gray Coding 213
4 Crossover 214
5 Mutation 216
6 Schemata 217
7 A Real-Coded Genetic Algorithm 218
8 Schemata Analysis for Real-AIlele Genetic Algorithms 220
9 Experimental Results 221
10 Conclusions 224
References 225
PART 5: FRAMEWORK ISSUES 226
Chapter 14. Fundamental Principles of 
228 
Abstract 228
1 Background 228
2 Definitions 230
3 A Note On Convention 233
4 The Only Challenging Problems are Deceptive 233
5 Constructing a Fully Deceptive Function 236
6 The Deceptive Attractor Theorem 237
7 The Deceptive Attractor and Local Optima 239
8 The Deceptive Attractor Remapping Strategies 241
9 Deception and Linkage Problems 242
10 A Description of the Experiments 243
11 Summary of Experimental Results 245
12 Conclusions and Future Directions 246
References 247
Chapter 15. Isomorphisms Of Genetic Algorithms 249
Abstract 249
1 Introduction 249
2 Schemata 250
3 Operators And Corresponding Schemata 251
4 Duality 253
5 Conclusion 254
6 Appendix 255
Acknowledgements 257
References 257
Chapter 16. Conditions for Implicit Parallelism 259
Abstract 259
1 Introduction 259
2 Background 260
3 Implicit Parallelism in Admissible Genetic Algorithms 262
4 The K-Armed Bandit Paradox 265
5 Directions for Further Work 267
6 Summary 268
References 268
PART 6: VARIATION AND RECOMBINATION 270
Chapter 17. The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging 
272 
Abstract 272
1 Introduction 272
2 Elitist Selection 274
3 Uniform Crossover 276
4 Avoiding Incest 280
5 Restarts 281
6 Empirical Results 282
7 Deceptive Problems 284
8 Extending CHC to Permutation Problems 286
9 Conclusion 287
Acknowledgements 287
References 287
Chapter 18. Genetic Operators for Sequencing Problems 291
Abstract 291
1 Introduction 291
2 Statement of the Problem 292
3 Survey of Related Research 293
4 Formal Model of Sequences 295
5 The Precedence Matrix and Unary Reordering Operators 296
6 The Precedence Matrix and Binary Reordering Operators 297
7 Two New Operators 297
8 The Intersection Operator 298
9 The Union Operator 299
10 Architecture of the GENOA Testbed 300
11 Empirical Results 300
12 Conclusion 306
Acknowledgments 307
References 307
Chapter 19. An Analysis of Multi-Point Crossover 308
Abstract 308
1 Introduction 308
2 Traditional Analysis 309
3 Crossover Disruption for Higher Order Hyperplanes 312
4 Tighter Estimates on Disruption Probabilities 313
5 Analyzing Uniform Crossover 317
6· Disruption Always Bad? 319
7 Conclusions and Further Work 322
Acknowledgements 322
References 322
Chapter 20. Evolution in Time and Space - The Parallel Genetic Algorithm 323
Abstract 323
1 Introduction 323
2 Parallel search and optimization 324
3 Evolutionary algorithms and genetic algorithms 325
4 Diversification by a spatial population structure 328
5 The schema theorem revisited 330
6 Statistical analysis of the deceptive problems 332
7 The PGA and the deceptive problems 335
8 Iterated hill-climbing vs. the PGA 336
9 The traveling salesman problem 337
10 Performance evaluation for the TSP 338
11 Configuration space analysis of the TSP 340
12 Conclusion 342
References 343
Author Index 346
Key Word Index 348