Rawlins Foundations of Genetic Algorithms 1991 (FOGA 1)

1. Auflage 2014
ISBN: 978-0-08-050684-5
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band Volume 1, 348 Seiten, Web PDF

Reihe: Foundations of Genetic Algorithms

Foundations of Genetic Algorithms 1991 (FOGA 1) discusses the theoretical foundations of genetic algorithms (GA) and classifier systems. This book compiles research papers on selection and convergence, coding and representation, problem hardness, deception, classifier system design, variation and recombination, parallelization, and population divergence. Other topics include the non-uniform Walsh-schema transform; spurious correlations and premature convergence in genetic algorithms; and variable default hierarchy separation in a classifier system. The grammar-based genetic algorithm; conditions for implicit parallelism; and analysis of multi-point crossover are also elaborated. This text likewise covers the genetic algorithms for real parameter optimization and isomorphisms of genetic algorithms. This publication is a good reference for students and researchers interested in genetic algorithms.

Autoren/Hrsg.

Rawlins, Gregory J. E.

Inhaltsverzeichnis

1;Front Cover;1
2;Foundations of Genetic Algorithms;4
3;Copyright page;5
4;Table of Contents;6
5;Introduction;8
5.1;1 A Short Introduction to Genetic Algorithms;9
5.2;2 Definitions and Assumptions;10
5.3;3 Metrics;13
5.4;4 Search Algorithms;14
5.5;References;17
6;PART I: GENETIC ALGORITHM HARDNESS;18
6.1;Chapter 1. The Nonuniform Walsh-Schema Transform;20
6.1.1;Abstract;20
6.1.2;1 Introduction;20
6.1.3;2 Definition of the Nonuniform Walsh-Schema Transform;21
6.1.4;3 Relationship to the Hyperplane Transform;23
6.1.5;4 Conclusions;28
6.1.6;Acknowledgments;29
6.1.7;References;29
6.2;Chapter 2. Epistasis Variance: A Viewpoint on GA-Hardness;30
6.2.1;Abstract;30
6.2.2;1 Background;30
6.2.3;2 Notional epistasis in GAs;31
6.2.4;3 The basic elements of epistasis;32
6.2.5;4 Calculating epistasis: A few examples;35
6.2.6;5 Conclusions and future work;40
6.2.7;Acknowledgments;40
6.2.8;References;41
6.3;Chapter 3. Deceptiveness and GeneticAlgorithm Dynamics;43
6.3.1;Abstract;43
6.3.2;1 Introduction;43
6.3.3;2 Embedding, Representation and Deceptiveness;46
6.3.4;3 GAs as Dynamic Systems;51
6.3.5;4 Summary;54
6.3.6;References;54
7;PART 2: SELECTION AND CONVERGENCE;58
7.1;Chapter 4. An Extension To the Theory of Convergence and a Proof of the
Time Complexity of Genetic Algorithms;60
7.1.1;Abstract;60
7.1.2;1. Introduction and Background;60
7.1.3;2. The Solution of the Recurrence Relation By Inspection and
An Inductive Proof for Binary Genetic Algorithms;63
7.1.4;3. The Recurrence Relation for Convergence for Nonbinary
Genetic Algorithms;67
7.1.5;4. The Solution for the Time to Convergence tc for Binary and
Nonbinary Genetic Algorithms;70
7.1.6;5. Examples and Extensions;73
7.1.7;6. Conclusions;74
7.1.8;References;75
7.2;Chapter 5. A Comparative Analysis of Selection Schemes
Used in Genetic Algorithms;76
7.2.1;Abstract;76
7.2.2;1 Introduction;76
7.2.3;2 Selection: A Matter of Birth, Life, and Death;77
7.2.4;3 Proportionate Reproduction;78
7.2.5;4 Ranking Selection;83
7.2.6;5 Tournament Selection;85
7.2.7;6 Genitor;89
7.2.8;7 Selection Procedures Head to Head;92
7.2.9;8 Selection: What Should We Be Doing;94
7.2.10;9 Conclusions;97
7.2.11;Acknowledgments;98
7.2.12;References;98
7.3;Chapter 6. A Study of Reproduction in Generational and Steady-State
Genetic Algorithms;101
7.3.1;Abstract;101
7.3.2;1 INTRODUCTION;101
7.3.3;2 Ideal Reproductive Performance;102
7.3.4;3 Actual Behavior;103
7.3.5;4 Discussion;106
7.3.6;References;107
7.4;Chapter 7. Spurious Correlations and Premature Convergence
in Genetic Algorithms;109
7.4.1;Abstract;109
7.4.2;1 Introduction;110
7.4.3;2 Schema Sampling Theory and Sampling Error;110
7.4.4;3 Empirical Evidence;112
7.4.5;References;118
8;PART 3: CLASSIFIER SYSTEMS;120
8.1;Chapter 8. Representing Attribute-Based Concepts
in a Classifier System;122
8.1.1;Abstract;122
8.1.2;1 Introduction;122
8.1.3;2 Standard Binary Encodings;123
8.1.4;3 More Expressive Encodings;126
8.1.5;4 Discussion;132
8.1.6;Acknowledgement;133
8.1.7;References;133
8.2;Chapter 9. Quasimorphisms or Queasymorphisms?
Modeling Finite Automaton Environments;135
8.2.1;Abstract;135
8.2.2;1 Introduction;135
8.2.3;2 Row Stochastic Matrices1;138
8.2.4;3 State Values;140
8.2.5;4 The Bucket Brigade;142
8.2.6;5 Payoffs That Are Not Fixed;145
8.2.7;6 Model State Values;145
8.2.8;7 Some Homomorphic Images;145
8.2.9;8 Decomposition;147
8.2.10;9 The First Component as a Homomorphic Image;148
8.2.11;10 The First Component as a Model, Using Bucket
Brigade;150
8.2.12;11 The Equipayoff Homomorphism;152
8.2.13;12 Queasymorphic Images;153
8.2.14;13 Conclusion and Disclaimer;154
8.2.15;References;154
8.3;Chapter 10. Variable Default Hierarchy Separation
in a Classifier System;155
8.3.1;Abstract;155
8.3.2;1 Introduction;156
8.3.3;2 The Importance of Default Hierarchies in LCSs;156
8.3.4;3 Formal Definitions;157
8.3.5;4 Ideal Default-Exception Pairs and Fixed Separation;161
8.3.6;5 The Necessity Auction;164
8.3.7;6 Separate Priority Factors;167
8.3.8;7 General Default-Exception Pairs;168
8.3.9;8 Final Comments;173
8.3.10;Acknowledgments;174
8.3.11;References;174
9;PART 4: CODING AND REPRESENTATION;176
9.1;Chapter 11. Hierarchical Approach to Learning the Boolean
Multiplexer Function;178
9.1.1;ABSTRACT;178
9.1.2;1. Introduction and Overview;178
9.1.3;2. Background;178
9.1.4;3. Background on Genetic Programming Paradigm;179
9.1.5;4. Boolean 11-Multiplexer Function;182
9.1.6;5· Hierarchies and Default Hierarchies;194
9.1.7;6. Non-Randomness of Results;195
9.1.8;7. Conclusions;197
9.1.9;References;198
9.2;Chapter 12. A Grammar-Based Genetic Algorithm;200
9.2.1;ABSTRACT;200
9.2.2;1 Introduction;200
9.2.3;2 A Recapitulation of the Foundations of the GA;201
9.2.4;3 GA Limitations in Structured Domains;203
9.2.5;4 A Grammar-Based GA;205
9.2.6;5 Previous Approaches, Future Directions;209
9.2.7;References;210
9.3;Chapter 13. Genetic Algorithms for Real Parameter
Optimization;212
9.3.1;Abstract;212
9.3.2;1 Introduction;212
9.3.3;2 Background;213
9.3.4;3. Binary Coding and Gray Coding;213
9.3.5;4 Crossover;214
9.3.6;5 Mutation;216
9.3.7;6 Schemata;217
9.3.8;7 A Real-Coded Genetic Algorithm;218
9.3.9;8 Schemata Analysis for Real-AIlele Genetic Algorithms;220
9.3.10;9 Experimental Results;221
9.3.11;10 Conclusions;224
9.3.12;References;225
10;PART 5: FRAMEWORK ISSUES;226
10.1;Chapter 14. Fundamental Principles of
Deception in Genetic Search;228
10.1.1;Abstract;228
10.1.2;1 Background;228
10.1.3;2 Definitions;230
10.1.4;3 A Note On Convention;233
10.1.5;4 The Only Challenging Problems are Deceptive;233
10.1.6;5 Constructing a Fully Deceptive Function;236
10.1.7;6 The Deceptive Attractor Theorem;237
10.1.8;7 The Deceptive Attractor and Local Optima;239
10.1.9;8 The Deceptive Attractor Remapping Strategies;241
10.1.10;9 Deception and Linkage Problems;242
10.1.11;10 A Description of the Experiments;243
10.1.12;11 Summary of Experimental Results;245
10.1.13;12 Conclusions and Future Directions;246
10.1.14;References;247
10.2;Chapter 15. Isomorphisms Of Genetic Algorithms;249
10.2.1;Abstract;249
10.2.2;1 Introduction;249
10.2.3;2 Schemata;250
10.2.4;3 Operators And Corresponding Schemata;251
10.2.5;4 Duality;253
10.2.6;5 Conclusion;254
10.2.7;6 Appendix;255
10.2.8;Acknowledgements;257
10.2.9;References;257
10.3;Chapter 16. Conditions for Implicit Parallelism;259
10.3.1;Abstract;259
10.3.2;1 Introduction;259
10.3.3;2 Background;260
10.3.4;3 Implicit Parallelism in Admissible Genetic Algorithms;262
10.3.5;4 The K-Armed Bandit Paradox;265
10.3.6;5 Directions for Further Work;267
10.3.7;6 Summary;268
10.3.8;References;268
11;PART 6: VARIATION AND RECOMBINATION;270
11.1;Chapter 17. The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging
in Nontraditional Genetic Recombination;272
11.1.1;Abstract;272
11.1.2;1 Introduction;272
11.1.3;2 Elitist Selection;274
11.1.4;3 Uniform Crossover;276
11.1.5;4 Avoiding Incest;280
11.1.6;5 Restarts;281
11.1.7;6 Empirical Results;282
11.1.8;7 Deceptive Problems;284
11.1.9;8 Extending CHC to Permutation Problems;286
11.1.10;9 Conclusion;287
11.1.11;Acknowledgements;287
11.1.12;References;287
11.2;Chapter 18. Genetic Operators for Sequencing Problems;291
11.2.1;Abstract;291
11.2.2;1 Introduction;291
11.2.3;2 Statement of the Problem;292
11.2.4;3 Survey of Related Research;293
11.2.5;4 Formal Model of Sequences;295
11.2.6;5 The Precedence Matrix and Unary Reordering Operators;296
11.2.7;6 The Precedence Matrix and Binary Reordering Operators;297
11.2.8;7 Two New Operators;297
11.2.9;8 The Intersection Operator;298
11.2.10;9 The Union Operator;299
11.2.11;10 Architecture of the GENOA Testbed;300
11.2.12;11 Empirical Results;300
11.2.13;12 Conclusion;306
11.2.14;Acknowledgments;307
11.2.15;References;307
11.3;Chapter 19. An Analysis of Multi-Point Crossover;308
11.3.1;Abstract;308
11.3.2;1 Introduction;308
11.3.3;2 Traditional Analysis;309
11.3.4;3 Crossover Disruption for Higher Order Hyperplanes;312
11.3.5;4 Tighter Estimates on Disruption Probabilities;313
11.3.6;5 Analyzing Uniform Crossover;317
11.3.7;6· Disruption Always Bad?;319
11.3.8;7 Conclusions and Further Work;322
11.3.9;Acknowledgements;322
11.3.10;References;322
11.4;Chapter 20. Evolution in Time and Space - The Parallel Genetic Algorithm;323
11.4.1;Abstract;323
11.4.2;1 Introduction;323
11.4.3;2 Parallel search and optimization;324
11.4.4;3 Evolutionary algorithms and genetic algorithms;325
11.4.5;4 Diversification by a spatial population structure;328
11.4.6;5 The schema theorem revisited;330
11.4.7;6 Statistical analysis of the deceptive problems;332
11.4.8;7 The PGA and the deceptive problems;335
11.4.9;8 Iterated hill-climbing vs. the PGA;336
11.4.10;9 The traveling salesman problem;337
11.4.11;10 Performance evaluation for the TSP;338
11.4.12;11 Configuration space analysis of the TSP;340
11.4.13;12 Conclusion;342
11.4.14;References;343
12;Author Index;346
13;Key Word Index;348