Genetics-based Machine Learning

Tim Kovacs

Department of Computer Science
University of Bristol

This is the author's final version (dated April 2009) of a chapter which appeared in Springer Verlag's Handbook of Natural Computing in 2012. The published version is available from www.springerlink.com. By default please cite the published version:

• Tim Kovacs. Genetics-based Machine Learning. In Grzegorz Rozenberg, Thomas Bäck, and Joost Kok, editors, Handbook of Natural Computing: Theory, Experiments, and Applications, pages 937-986. Springer Verlag, 2012.

Differences

In the author's final version (i.e. what you are reading now), section 3.5 Learning Classifier Systems has a new subsubsection 3.5.2 Representation and several other subsubsections from the published version were moved into the new one. This version also has a more detailed table of contents than the published version.

Abstract:

This is a survey of the field of Genetics-based Machine Learning (GBML): the application of evolutionary algorithms to machine learning. We assume readers are familiar with evolutionary algorithms and their application to optimisation problems, but not necessarily with machine learning. We briefly outline the scope of machine learning, introduce the more specific area of supervised learning, contrast it with optimisation and present arguments for and against GBML. Next we introduce a framework for GBML which includes ways of classifying GBML algorithms and a discussion of the interaction between learning and evolution. We then review the following areas with emphasis on their evolutionary aspects: GBML for sub-problems of learning, genetic programming, evolving ensembles, evolving neural networks, learning classifier systems, and genetic fuzzy systems.

Detailed Contents

• 1. Introduction
  • 1.1 Machine Learning
    • Inductive Generalisation
    • 1-Max: a Typical Optimisation Problem
    • Classification of Mushrooms: a Typical Learning Problem
    • Terminology in Supervised Learning
    • Comparison of Supervised Learning and Optimisation
    • Issues in Supervised Learning
  • 1.2 Arguments For and Against GBML
  
  
• 2. A Framework for GBML
  • 2.1 Classifying GBML Systems by Role
  • 2.2 Classifying GBML Systems Algorithmically
    • Pittsburgh and Michigan Compared
    • Iterative Rule Learning
    • Genetic Cooperative-Competitive Learning
  • 2.3 The Interaction of Learning and Evolution
    • Memetic Learning
    • Darwinian and Lamarckian Evolution
    • The Baldwin Effect
    • Evaluating Evolutionary Search by Evaluating Accuracy
  • 2.4 Other GBML Models
    • Online Evolutionary Computation
    • Steady State EAs
    • Co-evolving Learners and Problems
  
  
• 3. GBML Areas
  • 3.1 GBML for Sub-problems of Learning
    • Evolutionary Feature Selection
    • Evolutionary Feature Construction
    • Other Sub-problems of Learning
  • 3.2 Genetic Programming
    • 3.2.1 GP Trees
      • GP Trees for Classification
      • GP Trees for Regression
    • 3.2.2 Decision Trees
      • Evolving First-order Trees
      • Oblique (Linear) Trees
      • Evolving Individual Nodes in Decision Trees
    • 3.2.3 Extensions to GP
      • Ensemble Methods and GP
      • GP Hyperheuristics
    • 3.2.4 Conclusions
      • Lack of Test Sets in GP
      • Reading
  • 3.3 Evolving Ensembles
    • 3.3.1 Evolutionary Ensembles
      • Classifier Creation and Adaptation
      • Evolutionary Selection of Members
    • 3.3.2 Conclusions
      • Reading
  • 3.4 Evolving Neural Networks
    • Representations
    • Credit Assignment
    • Adapting Weights
    • Evolving AND Learning Weights
    • Evolving Architectures
    • Evolving Learning Rules
    • 3.4.1 Ensembles of NNs
      • Single-objective Ensembles
      • Multi-objective Ensembles
    • 3.4.2 Yao's Framework for Evolving NNs
    • 3.4.3 Conclusions
      • Reading
  • 3.5 Learning Classifier Systems
    • 3.5.1 Production Systems and Rule(Set) Parameters
    • 3.5.2 Representation
      • Representing Conditions and Actions
      • Evolutionary Selection of Representations
      • Optimisation of Population Representation: Macroclassifiers
    • 3.5.3 Rule Discovery
      • Windowing in Pittsburgh LCS
      • Michigan Rule Discovery
      • Niche GAs
      • EDAs instead of GAs
      • Subsumption Deletion
      • Michigan Evolutionary Dynamics
      • Condensation
      • Tuning Evolutionary Search
      • Non-evolutionary Rule Discovery
      • Non-evolutionary LCS
    • 3.5.4 LCS Credit Assignment
      • Strength and Accuracy in Michigan LCS
      • Prediction Updates
      • Evolutionary Selection of Prediction Functions
      • Theoretical Results
      • Hierarchies and Ensembles of LCS
    • 3.5.5 Conclusions
      • Reading
  • 3.6 Genetic Fuzzy Systems
    • 3.6.1 Evolution of FRBSs
      • Genetic Tuning
      • Genetic Learning
    • 3.6.2 Genetic Neuro-fuzzy Systems
    • 3.6.3 Conclusions
      • Reading
  
  
• 4. Conclusions

• Acknowledgements
• Glossary
• Bibliography
• About this document ...