Foundations of Genetic Algorithms 1993 (FOGA 2)

Book description

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.

Table of contents

  1. Front Cover
  2. Foundations of Genetic Algorithms 2
  3. Copyright Page
  4. Table of Contents
  5. Dedication
  6. FOGA–92: THE PROGRAM COMMITTEE
  7. Introduction
  8. PART I: FOUNDATION ISSUES REVISITED
    1. Chapter 1. Genetic Algorithms Are NOT Function Optimizers
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 WHAT IS A GENETIC ALGORITHM?
      4. 3 BEHAVIOR EXHIBITED BY GAs
      5. 4 ANALYSIS OF GA BEHAVIOR
      6. 5 GAs AS FUNCTION OPTIMIZERS
      7. 6 SOME FUNDAMENTAL MISCONCEPTIONS
      8. 7 SUMMARY AND CONCLUSIONS
      9. REFERENCES
    2. Chapter 2. Generation Gaps Revisited
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 BACKGROUND
      4. 3 GENERATION GAP ANALYSIS
      5. 4 WHAT ABOUT REAL GAs?
      6. 5 CONCLUSIONS AND FURTHER WORK
      7. References
  9. PART 2: MODELING GENETIC ALGORITHMS
    1. Chapter 3. Recombination Distributions for Genetic Algorithms
      1. Abstract
      2. 1 Introduction
      3. 2 The Theory of Recombination Distributions
      4. 3 Recombination Distributions for Crossover Operators
      5. 4 Quantifying Bias in Crossover Operators (1/2)
      6. 4 Quantifying Bias in Crossover Operators (2/2)
      7. 5 Discussion
      8. Acknowledgements
      9. References
    2. Chapter 4. An Executable Model of a Simple Genetic Algorithm
      1. Abstract
      2. 1 Introduction
      3. 2 A Generalized Form Based on Equation Generators
      4. 3 The Vose and Liepins Models
      5. 4 Implementation Complexity and Preliminary Results
      6. 5 Other Operators and Computational Behavior (1/2)
      7. 5 Other Operators and Computational Behavior (2/2)
      8. 6 Discussion
      9. A cknowledgements
      10. References
    3. Chapter 5. Modeling Simple Genetic Algorithms
      1. Abstract
      2. 1 Introduction
      3. 2 The Infinite Population Model
      4. 3 The Finite Population Model
      5. 4 The GA-surface
      6. 5 The Fixed Point Graph
      7. 6 Asymptotic Approximation
      8. 7 Conclusion
      9. Acknowledgements
      10. References
  10. PART 3: DECEPTION AND THE BUILDING BLOCK HYPOTHESIS
    1. Chapter 6. Deception Considered Harmful
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 THE STATIC BUILDING BLOCK HYPOTHESIS
      4. 3 COLLATERAL CONVERGENCE
      5. 4 LARGE VARIANCE WITHIN SCHEMAS
      6. 5 AUGMENTED GAs FOR DECEPTIVE PROBLEMS
      7. 6 SUMMARY
      8. Acknowledgements
      9. REFERENCES
    2. Chapter 7. Analyzing Deception in Trap Functions
      1. Abstract
      2. 1 Introduction
      3. 2 Trap functions
      4. 3 Deception analysis
      5. 4 Critical z for deception
      6. 5 Limiting values of r
      7. 6 The density of trap-function deception
      8. 7 Conclusions
      9. Acknowledgments
      10. References
    3. Chapter 8. Relative Building-Block Fitness and the Building-Block Hypothesis
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 STEPPING STONES IN THE CROSSOVER LANDSCAPE
      4. 3 ROYAL ROAD EXPERIMENTS (1/2)
      5. 3 ROYAL ROAD EXPERIMENTS (2/2)
      6. 4 DISCUSSION
      7. 5 EXPERIMENTS WITH HILL-CLIMBING
      8. 6 CONCLUSIONS AND FUTURE DIRECTIONS
      9. Acknowledgments
      10. References
  11. PART 4: CONVERGENCE AND GENETIC DIVERSITY
    1. Chapter 9. Accounting for Noise in the Sizing of Populations
      1. Abstract
      2. 1 Introduction
      3. 2 Population Sizing in the Presence of Noise
      4. 3 Testing the Population-sizing Equation (1/2)
      5. 3 Testing the Population-sizing Equation (2/2)
      6. 4 Extensions
      7. 5 Conclusions
      8. Acknowledgments
      9. References
    2. Chapter 10. Syntactic Analysis of Convergence in Genetic Algorithms
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 GENETIC ALGORITHMS AND HAMMING DISTANCE
      4. 3 CROSSOVER AND AVERAGE HAMMING DISTANCE
      5. 4 SELECTION AND AVERAGE HAMMING DISTANCE
      6. 5 PREDICTING TIME TO CONVERGENCE
      7. 6 RESULTS
      8. 7 CONCLUSIONS
      9. References
    3. Chapter 11. Population Diversity in an Immune System Model: Implications for Genetic Search
      1. Abstract
      2. 1 Introduction
      3. 2 GA Simulations of the Immune System
      4. 3 Emergent Fitness Sharing in the Immune System Model
      5. 4 Conclusions
      6. 5 Acknowledgements
      7. References
    4. Chapter 12. Remapping Hyperspace During Genetic Search: Canonical Delta Folding
      1. Abstract
      2. 1 Introduction
      3. 2 Background
      4. 3 Canonical Delta Folding (1/2)
      5. 3 Canonical Delta Folding (2/2)
      6. 4 Additional Adaptive Mechanisms in Delta Folding
      7. 5 Discussion
      8. Acknowledgements
      9. References
  12. PART 5: GENETIC OPERATORS AND THEIR ANALYSIS
    1. Chapter 13. Real-Coded Genetic Algorithms and Interval-Schemata
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 INTERVAL-SCHEMATA AND CROSSOVER
      4. 3 FAILURE MODES OF AN IPGA
      5. 4 EMPIRICAL COMPARISONS (1/2)
      6. 4 EMPIRICAL COMPARISONS (2/2)
      7. 5 CROSSOVER VERSUS MUTATION
      8. 6 CONCLUSION
      9. References
    2. Chapter 14. Genetic Set Recombination
      1. Abstract
      2. 1 Introduction
      3. 2 Forma Analysis: Summary and Definitions
      4. 3 Sets and Multiset Recombination
      5. 4 Recombining Fixed-Size Sets
      6. 5 Recombination of Fixed-Size Multisets
      7. 6 Recombining Variable-Size Multisets
      8. 7 Assorting Non-Separable Formae
      9. 8 Summary
      10. References
    3. Chapter 15. Crossover or Mutation?
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 DISRUPTION THEORY
      4. 3 CONSTRUCTION THEORY
      5. 4 SUMMARY AND DISCUSSION
      6. Acknowledgements
      7. References
      8. Appendix
    4. Chapter 16. Simulated Crossover in Genetic Algorithms
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 BIT-BASED SIMULATED CROSSOVER (BSC)
      4. 3 RECOMBINATION AND SIMULATED CROSSOVER
      5. 4 REPRODUCTION OF SCHEMATA
      6. 5 Simulating Simulated Crossover
      7. 6 EMPIRICAL STUDIES
      8. 7 THE ROLE OF A POPULATION
      9. 8 SUMMARY
      10. Acknowledgments
      11. References
  13. PART 6: MACHINE LEARNING
    1. Chapter 17. Learning Boolean Functions with Genetic Algorithms: A PAC Analysis
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 CONCEPTS, REPRESENTATIONS, PAC LEARNING
      4. 3 THE GENETIC PAC LEARNER (1/2)
      5. 3 THE GENETIC PAC LEARNER (2/2)
      6. 4 SUMMARY AND DISCUSSION
      7. Acknowledgements
      8. References
    2. Chapter 18. Is the Genetic Algonthm a Cooperative Learner?
      1. Abstract
      2. 1 INTRODUCTION
      3. 2 OVERVIEW OF THE PROBLEM (1/2)
      4. 2 OVERVIEW OF THE PROBLEM (2/2)
      5. 3 AN EMPIRICAL LOOK AT THE PROBLEM
      6. 4 EXAMINING SOME GA OPTIMIZATION PROBLEMS (1/2)
      7. 4 EXAMINING SOME GA OPTIMIZATION PROBLEMS (2/2)
      8. 5 CONCLUSIONS
      9. Acknowledgments
      10. References
    3. Chapter 19. Hierarchical Automatic Function Definition in Genetic Programming
      1. Abstract
      2. 1 INTRODUCTION AND OVERVIEW
      3. 2 LEARNING THE EVEN-PARITY-FUNCTION WITH GENETIC PROGRAMMING
      4. 3 AUTOMATIC FUNCTION DEFINITION (1/2)
      5. 3 AUTOMATIC FUNCTION DEFINITION (2/2)
      6. 4 HIERARCHICAL AUTOMATIC FUNCTION DEFINITION (1/2)
      7. 4 HIERARCHICAL AUTOMATIC FUNCTION DEFINITION (2/2)
      8. 5 BOOLEAN 11-MULTIPLEXER
      9. 6 CONCLUSIONS
  14. Author Index
  15. Key Word Index

Product information

  • Title: Foundations of Genetic Algorithms 1993 (FOGA 2)
  • Author(s): FOGA
  • Release date: June 2014
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080948324