1st Edition

Genetic Algorithms and Genetic Programming Modern Concepts and Practical Applications

    400 Pages 138 B/W Illustrations
    by Chapman & Hall

    394 Pages 138 B/W Illustrations
    by Chapman & Hall

    Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications discusses algorithmic developments in the context of genetic algorithms (GAs) and genetic programming (GP). It applies the algorithms to significant combinatorial optimization problems and describes structure identification using HeuristicLab as a platform for algorithm development.

    The book focuses on both theoretical and empirical aspects. The theoretical sections explore the important and characteristic properties of the basic GA as well as main characteristics of the selected algorithmic extensions developed by the authors. In the empirical parts of the text, the authors apply GAs to two combinatorial optimization problems: the traveling salesman and capacitated vehicle routing problems. To highlight the properties of the algorithmic measures in the field of GP, they analyze GP-based nonlinear structure identification applied to time series and classification problems.

    Written by core members of the HeuristicLab team, this book provides a better understanding of the basic workflow of GAs and GP, encouraging readers to establish new bionic, problem-independent theoretical concepts. By comparing the results of standard GA and GP implementation with several algorithmic extensions, it also shows how to substantially increase achievable solution quality.

    Introduction

    Simulating Evolution: Basics about Genetic Algorithms

    The Evolution of Evolutionary Computation

    The Basics of Genetic Algorithms (GAs)

    Biological Terminology

    Genetic Operators

    Problem Representation

    GA Theory: Schemata and Building Blocks

    Parallel Genetic Algorithms

    The Interplay of Genetic Operators

    Bibliographic Remarks

    Evolving Programs: Genetic Programming

    Introduction: Main Ideas and Historical Background

    Chromosome Representation

    Basic Steps of the Genetic Programming (GP)-Based Problem Solving Process

    Typical Applications of GP

    GP Schema Theories

    Current GP Challenges and Research Areas

    Conclusion

    Bibliographic Remarks

    Problems and Success Factors

    What Makes GAs and GP Unique Among Intelligent Optimization Methods?

    Stagnation and Premature Convergence

    Preservation of Relevant Building Blocks

    What Can Extended Selection Concepts Do to Avoid Premature Convergence?

    Offspring Selection (OS)

    The Relevant Alleles Preserving Genetic Algorithm (RAPGA)

    Consequences Arising out of Offspring Selection and RAPGA

    SASEGASA—More Than the Sum of All Parts

    The Interplay of Distributed Search and Systematic Recovery of Essential Genetic Information

    Migration Revisited

    SASEGASA: A Novel and Self-Adaptive Parallel Genetic Algorithm

    Interactions between Genetic Drift, Migration, and Self-Adaptive Selection Pressure

    Analysis of Population Dynamics

    Parent Analysis

    Genetic Diversity

    Characteristics of Offspring Selection and the RAPGA

    Introduction

    Building Block Analysis for Standard GAs

    Building Block Analysis for GAs Using Offspring Selection

    Building Block Analysis for the RAPGA

    Combinatorial Optimization: Route Planning

    The Traveling Salesman Problem

    The Capacitated Vehicle Routing Problem

    Evolutionary System Identification

    Data-Based Modeling and System Identification

    GP-Based System Identification in HeuristicLab

    Local Adaption Embedded in Global Optimization

    Similarity Measures for Solution Candidates

    Applications of Genetic Algorithms: Combinatorial Optimization

    The Traveling Salesman Problem

    Capacitated Vehicle Routing

    Data-Based Modeling with Genetic Programming

    Time Series Analysis

    Classification

    Genetic Propagation

    Single Population Diversity Analysis

    Multi-Population Diversity Analysis

    Code Bloat, Pruning, and Population Diversity

    Conclusion and Outlook

    Symbols and Abbreviations

    References

    Index

    Biography

    Michael Affenzeller, Stefan Wagner, Stephan Winkler, Andreas Beham