Foundations of Genetic Algorithms 1993 (FOGA 2) (eBook)

Front Cover 1
Foundations of Genetic Algorithms 2 4
Copyright Page 5
Table of Contents 8
Dedication 6
FOGA–92: THE PROGRAM COMMITTEE 7
Introduction 10
PART I: FOUNDATION ISSUES REVISITED 14
Chapter 1. Genetic Algorithms Are NOT Function Optimizers 16
Abstract 16
1 INTRODUCTION 16
2 WHAT IS A GENETIC ALGORITHM? 17
3 BEHAVIOR EXHIBITED BY GAs 19
4 ANALYSIS OF GA BEHAVIOR 23
5 GAs AS FUNCTION OPTIMIZERS 23
6 SOME FUNDAMENTAL MISCONCEPTIONS 26
7 SUMMARY AND CONCLUSIONS 27
REFERENCES 28
Chapter 2. Generation Gaps Revisited 30
Abstract 30
1 INTRODUCTION 30
2 BACKGROUND 31
3 GENERATION GAP ANALYSIS 32
4 WHAT ABOUT REAL GAs? 36
5 CONCLUSIONS AND FURTHER WORK 37
References 38
PART 2: MODELING GENETIC ALGORITHMS 40
Chapter 3. Recombination Distributions for Genetic Algorithms 42
Abstract 42
1 Introduction 42
2 The Theory of Recombination Distributions 43
3 Recombination Distributions for Crossover Operators 46
4 Quantifying Bias in Crossover Operators 50
5 Discussion 56
Acknowledgements 56
References 56
Chapter 4. An Executable Model of a Simple Genetic Algorithm 58
Abstract 58
1 Introduction 58
2 A Generalized Form Based on Equation Generators 60
3 The Vose and Liepins Models 65
4 Implementation Complexity and Preliminary Results 67
5 Other Operators and Computational Behavior 68
6 Discussion 74
A cknowledgements 74
References 75
Chapter 5. Modeling Simple Genetic Algorithms 76
Abstract 76
1 Introduction 76
2 The Infinite Population Model 78
3 The Finite Population Model 79
4 The GA-surface 79
5 The Fixed Point Graph 82
6 Asymptotic Approximation 83
7 Conclusion 85
Acknowledgements 85
References 86
PART 3: DECEPTION AND THE BUILDING BLOCK HYPOTHESIS 88
Chapter 6. Deception Considered Harmful 90
Abstract 90
1 INTRODUCTION 90
2 THE STATIC BUILDING BLOCK HYPOTHESIS 92
3 COLLATERAL CONVERGENCE 95
4 LARGE VARIANCE WITHIN SCHEMAS 99
5 AUGMENTED GAs FOR DECEPTIVE PROBLEMS 100
6 SUMMARY 102
Acknowledgements 104
REFERENCES 104
Chapter 7. Analyzing Deception in Trap Functions 108
Abstract 108
1 Introduction 108
2 Trap functions 109
3 Deception analysis 110
4 Critical z for deception 114
5 Limiting values of r 115
6 The density of trap-function deception 119
7 Conclusions 122
Acknowledgments 122
References 122
Chapter 8. Relative Building-Block Fitness and the Building-Block Hypothesis 124
Abstract 124
1 INTRODUCTION 125
2 STEPPING STONES IN THE CROSSOVER LANDSCAPE 126
3 ROYAL ROAD EXPERIMENTS 129
4 DISCUSSION 135
5 EXPERIMENTS WITH HILL-CLIMBING 135
6 CONCLUSIONS AND FUTURE DIRECTIONS 137
Acknowledgments 139
References 140
PART 4: CONVERGENCE AND GENETIC DIVERSITY 142
Chapter 9. Accounting for Noise in the Sizing of Populations 144
Abstract 144
1 Introduction 144
2 Population Sizing in the Presence of Noise 145
3 Testing the Population-sizing Equation 148
4 Extensions 154
5 Conclusions 156
Acknowledgments 156
References 156
Chapter 10. Syntactic Analysis of Convergence in Genetic Algorithms 158
Abstract 158
1 INTRODUCTION 158
2 GENETIC ALGORITHMS AND HAMMING DISTANCE 159
3 CROSSOVER AND AVERAGE HAMMING DISTANCE 160
4 SELECTION AND AVERAGE HAMMING DISTANCE 161
5 PREDICTING TIME TO CONVERGENCE 164
6 RESULTS 166
7 CONCLUSIONS 166
References 167
Chapter 11. Population Diversity in an Immune System Model: Implications for Genetic Search 170
Abstract 170
1 Introduction 171
2 GA Simulations of the Immune System 172
3 Emergent Fitness Sharing in the Immune System Model 175
4 Conclusions 180
5 Acknowledgements 181
References 181
Chapter 12. Remapping Hyperspace During Genetic Search: Canonical Delta Folding 184
Abstract 184
1 Introduction 184
2 Background 185
3 Canonical Delta Folding 190
4 Additional Adaptive Mechanisms in Delta Folding 199
5 Discussion 201
Acknowledgements 202
References 202
PART 5: GENETIC OPERATORS AND THEIR ANALYSIS 204
Chapter 13. Real-Coded Genetic Algorithms and Interval-Schemata 206
Abstract 206
1 INTRODUCTION 206
2 INTERVAL-SCHEMATA AND CROSSOVER 207
3 FAILURE MODES OF AN IPGA 210
4 EMPIRICAL COMPARISONS 212
5 CROSSOVER VERSUS MUTATION 219
6 CONCLUSION 220
References 220
Chapter 14. Genetic Set Recombination 222
Abstract 222
1 Introduction 222
2 Forma Analysis: Summary and Definitions 223
3 Sets and Multiset Recombination 227
4 Recombining Fixed-Size Sets 227
5 Recombination of Fixed-Size Multisets 231
6 Recombining Variable-Size Multisets 235
7 Assorting Non-Separable Formae 236
8 Summary 238
References 238
Chapter 15. Crossover or Mutation? 240
Abstract 240
1 INTRODUCTION 240
2 DISRUPTION THEORY 241
3 CONSTRUCTION THEORY 246
4 SUMMARY AND DISCUSSION 249
Acknowledgements 251
References 252
Appendix 254
Chapter 16. Simulated Crossover in Genetic Algorithms 258
Abstract 258
1 INTRODUCTION 258
2 BIT-BASED SIMULATED CROSSOVER (BSC) 259
3 RECOMBINATION AND SIMULATED CROSSOVER 260
4 REPRODUCTION OF SCHEMATA 261
5 Simulating Simulated Crossover 262
6 EMPIRICAL STUDIES 262
7 THE ROLE OF A POPULATION 270
8 SUMMARY 273
Acknowledgments 273
References 273
PART 6: MACHINE LEARNING 276
Chapter 17. Learning Boolean Functions with Genetic Algorithms: A PAC Analysis 278
Abstract 278
1 INTRODUCTION 278
2 CONCEPTS, REPRESENTATIONS, PAC LEARNING 279
3 THE GENETIC PAC LEARNER 284
4 SUMMARY AND DISCUSSION 294
Acknowledgements 295
References 295
Chapter 18. Is the Genetic Algonthm a Cooperative Learner? 298
Abstract 298
1 INTRODUCTION 299
2 OVERVIEW OF THE PROBLEM 300
3 AN EMPIRICAL LOOK AT THE PROBLEM 307
4 EXAMINING SOME GA OPTIMIZATION PROBLEMS 308
5 CONCLUSIONS 315
Acknowledgments 315
References 315
Chapter 19. Hierarchical Automatic Function Definition in Genetic Programming 318
Abstract 318
1 INTRODUCTION AND OVERVIEW 319
2 LEARNING THE EVEN-PARITY-FUNCTION WITH GENETIC PROGRAMMING 320
3 AUTOMATIC FUNCTION DEFINITION 324
4 HIERARCHICAL AUTOMATIC FUNCTION DEFINITION 331
5 BOOLEAN 11-MULTIPLEXER 337
6 CONCLUSIONS 338
Author Index 340
Key Word Index 342