Foundations of Genetic Algorithms 1995 (FOGA 3) (eBook)

Front Cover 1
Foundations of Genetic Algorithms 3 4
Copyright Page 5
Table of Contents 8
FOGA–94 THE PROGRAM COMMITTEE 6
Introduction 10
References 12
PART 1: 
14 
Chapter 1. An Experimental Design Perspective on Genetic Algorithms 16
1 INTRODUCTION 16
2 DAVIDOR'S EPISTASIS METHODOLOGY 18
3 AN EXPERIMENTAL DESIGN APPROACH 19
4 THE INFLUENCE OF CODING 22
5 WALSH TRANSFORMS AND DECEPTION 25
6 CROSSOVER NON-LINEARITY RATIOS 28
7 CONCLUSIONS 29
References 30
Chapter 2. 
32 
1 INTRODUCTION 32
2 GENETIC ALGORITHM ANALYSIS USING PRICE'S 
34 
3 RECOMBINATION AND THE RE-EMERGENCE OF 
42 
4 ADAPTIVE LANDSCAPE ANALYSIS 45
5 CONCLUSIONS 52
APPENDIX: 
53 
Chapter 3. 
60 
1 Motivation 60
2 A Review of Forma Analysis 62
3 Representation-independent Recombination 65
4 Representation-independent Mutation and Hill-climbing 66
5 Formae and Performance Prediction 69
6 Representations for the TSP 70
7 Experiments and Results 74
8 Discussion and Conclusions 80
References 80
Chapter 4. 
82 
1 INTRODUCTION 82
2 SCHEMA DEFINITION AND RELATED CONCEPTS 83
3 A GP SCHEMA THEOREM 88
4 BUILDING BLOCK DEFINITION and BUILDING BLOCK 
91 
5 CONCLUSION AND FUTURE WORK 95
References 96
PART 2: 
98 
Chapter 5. 
100 
1 SIMPLIFIED EVOLUTIONARY ALGORITHMS 101
2 CONVERGENCE VELOCITY 102
3 A DISCRETE OBJECTIVE FUNCTION 104
4 A CONTINUOUS OBJECTIVE FUNCTION 106
5 ASYMPTOTICS AND SUCH 109
6 CONCLUSIONS 110
References 110
Chapter 6. 
112 
1 INTRODUCTION 112
2 BASICS 114
3 THE SPECTRUM OF dQ 116
4 STABILITY IN THE SIMPLEX 117
5 APPLICATIONS 120
6 CONCLUSION 121
References 122
Chapter 7. 
124 
1 INTRODUCTION 125
2 MEASURING GA PERFORMANCE AND HARDNESS 126
3 MARKOV MODELS OF SIMPLE GAs 126
4 Visualizing Markov Models 129
5 GAFO THEORY 131
6 WAITING TIME ANALYSIS 138
7 Summary and Discussion 144
References 145
Chapter 8. 
148 
1 INTRODUCTION 148
2 PREDICTIVE MODELS OF POPULATION FITNESS 150
3 FITNESS DISTRIBUTIONS OF GENETIC OPERATORS 151
4 PREDICTIVE MODEL BASED ON LINEAR FITNESS 
163 
5 SCALING 166
6 APPLYING THE MODEL 166
7 SUMMARY 168
REFERENCES 170
Chapter 9. 
172 
1 INTRODUCTION 172
2 EXACT MODELS FOR SGAs 173
3 EXACT MODELS FOR PERMUTATIONS 174
4 AN EXAMINATION OF SPECIFIC PROBLEMS 185
5 CONCLUSIONS 192
References 192
Chapter 10. 
194 
1 INTRODUCTION 194
2 FITNESS SHARING 195
3 MODELLING FRAMEWORK 196
4 GENETIC DRIFT UNDER SHARING 199
5 POPULATION SIZE: SELECTION ONLY ALL CLASSES
212 
6 POPULATION SIZE: SELECTION ONLY DESIRABLE AND
221 
7 POPULATION SIZE SELECTION PLUS CROSSOVER
8 EXTENSIONS 227
9 CONCLUSION 230
References 230
Appendix 231
Chapter 11. 
234 
1 INTRODUCTION 234
2 GENETIC ALGORITHMS USING A MONOTONIC 
235 
3 GENETIC ALGORITHMS USING PROPORTIONAL 
238 
4 SENSITIVITY OF A PSGA TO THE CONVEXITY OF THEUSED FITNESS FUNCTION 242
5 COMPARING THE SENSITIVITIES OF PSGA -S 246
6 CONCLUSIONS 248
References 249
PART 3: 
250 
Chapter 12. 
252 
1 INTRODUCTION 253
2 PRELIMINARIES: LANDSCAPES AND OPTIMA 253
3 MINIMUM MODALITY CAN BE HARD 254
4 MAXIMUM MODALITY CAN BE EASY 258
5 INTERMEDIATE MODALITY: LOCAL OPTIMA AND 
261 
6 CONCLUSIONS 276
References 276
Chapter 13. 
280 
1. Introduction 280
2. Greedy Recombination Operator Re(n) for Genetic Programming 282
4. Experiments 294
5. Discussion 303
Chapter 14. 
308 
1 INTRODUCTION 308
2 PRODUCTIVE RECOMBINATION 309
3 SPURIOUS CORRELATIONS 312
4 RECOMBINATIVE BIAS'S FAILURE MODES 314
5 SELF-ADJUSTING RECOMBINATION OPERATORS 319
6 CONCLUSION 320
References 321
Chapter 15. 
324 
1 Introduction 324
2 Definitions 325
3 Examples 328
4 Fitness Transformations 331
5 Repair and Maturation 336
6 Time Complexity Issues 337
7 Evolutionary Bias 338
8 Conclusions 339
References 340
Author Index 342
Key Word Index 344