Genetic Algorithms and Genetic Programming Modern Concepts and Practical Applications

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

Michael Affenzeller, Stefan Wagner, Stephan Winkler, Andreas Beham