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

FOGA (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
322 Seiten
Elsevier Science (Verlag)
978-0-08-094832-4 (ISBN)

Infos

Foundations of Genetic Algorithms, Volume 2 provides insight of theoretical work in genetic algorithms. This book provides a general understanding of a canonical genetic algorithm. Organized into six parts encompassing 19 chapters, this volume begins with an overview of genetic algorithms in the broader adaptive systems context. This text then reviews some results in mathematical genetics that use probability distributions to characterize the effects of recombination on multiple loci in the absence of selection. Other chapters examine the static building block hypothesis (SBBH), which is the underlying assumption used to define deception. This book discusses as well the effect of noise on the quality of convergence of genetic algorithms. The final chapter deals with the primary goal in machine learning and artificial intelligence, which is to dynamically and automatically decompose problems into simpler problems to facilitate their solution. This book is a valuable resource for theorists and genetic algorithm researchers.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 28.6.2014
• Sprache: englisch
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Naturwissenschaften ► Biologie ► Genetik / Molekularbiologie
• ISBN-10: 0-08-094832-4 / 0080948324
• ISBN-13: 978-0-08-094832-4 / 9780080948324