Affenzeller M., Winkler S., Wagner S., Beham A. Genetic Algorithms and Genetic Programming. Modern Concepts and Practical Applications

CRC Press, 2009, -377 p.Essentially, this book is about algorithmic developments in the context of genetic algorithms (GAs) and genetic programming (GP); we also describe their applications to significant combinatorial optimization problems as well as structure identification using HeuristicLab as a platform for algorithm development. The main issue of the theoretical considerations is to obtain a better understanding of the basic workflow of GAs and GP, in order to estab- lish new bionic, problem independent theoretical concepts and to substantially increase the achievable solution quality.The book is structured into a theoretical and an empirical part. The aim of the theoretical part is to describe the important and characteristic properties of the basic genetic algorithm as well as the main characteristics of the algorithmic extensions introduced here. The empirical part of the book elaborates two case studies: On the one hand, the traveling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP) are used as representatives for GAs applied to combinatorial optimization problems. On the other hand, GP-based nonlinear structure identification applied to time series and classification problems is analyzed to highlight the properties of the algorithmic measures in the field of genetic programming. The borderlines between theory and practice become indistinct in some parts as it is also necessary to describe theoretical properties on the basis of practical examples in the first part of the book. For this purpose we go back to some small-dimensioned TSP instances that are perfectly suited for theoretical GA considerations.Research concerning the self-adaptive interplay between selection and the applied solution manipulation operators (crossover and mutation) is the basis for the algorithmic developments presented in this book. The ultimate goal in this context is to avoid the disappearance of relevant building blocks and to support the combination of those alleles from the gene pool that carry solution properties of highly fit individuals. As we show in comparative test series, in conventional GAs and GP this relevant genetic information is likely to get lost quite early in the standard variants of these algorithms and can only be reintroduced into the population’s gene pool by mutation. This dependence on mutation can be drastically reduced by new generic selection principles based upon either self-adaptive selection pressure steering (offspring selection, OS) or self-adaptive population size adjustment as proposed in the relevant alleles preserving genetic algorithm (RAPGA). Both algorithmic extensions certify the survival of essential genetic information by supporting the survival of rel- evant alleles rather than the survival of above average chromosomes. This is achieved by defining the survival probability of a new child chromosome depending on the child’s fitness in comparison to the fitness values of its own parents. With these measures it becomes possible to channel the relevant alleles, which are initially scattered in the entire population, to single chromosomes at the end of the genetic search process.The SASEGASA algorithm is a special coarse-grained parallel GA; the acronym SASEGASA hereby stands for Self-Adaptive Segregative Genetic Algorithm including aspects of Simulated Annealing. SASEGASA combines offspring selection with enhanced parallelization concepts in order to avoid premature convergence, one of the major problems with GAs. As we will show for the TSP, it becomes possible to scale the robustness and particularly the achievable solution quality by the number of subpopulations.Due to the high focus on sexual recombination, evolution strategies (ES) are not considered explicitly in this book. Nevertheless, many of the theoretical considerations are heavily inspired by evolution strategies, especially the aspect of selection after reproduction and (self-)adaptive selection pressure steering. Aside from other variants of evolutionary computation, further inspirations are borrowed from fields, as for example, population genetics. The implementation of bionic ideas for algorithmic developments is quite pragmatic and ignores debates on principles that are discussed in natural sciences. Of course, we are always aware of the fact that artificial evolution as per- formed in an evolutionary algorithm is situated on a high level of abstraction compared to the biological role model in any case.The problem-oriented part of the book is dedicated to the application of the algorithmic concepts described in this book to benchmark as well as real world problems. Concretely, we examine the traveling salesman problem and the capacitated vehicle routing problem (which is thematically related to the TSP), but more in step with actual practice, as representatives of combinatorial optimization problems.Time series and classification analysis are used as application areas of data- based structure identification with genetic programming working with formula trees representing mathematical models. As a matter of principle, we use standard problem representations and the appropriate problem-specific genetic operators known from GA and GP theory for the experiments shown in these chapters. The focus is set on the comparison of results achievable with standard GA and GP implementations to the results achieved using the ex- tended algorithmic concepts described in this book. These enhanced concepts do not depend on a concrete problem representation and its operators; their influences on population dynamics in GA and GP populations are analyzed, too.Simulating Evolution: Basics about Genetic Algorithms
Evolving Programs: Genetic Programming
Problems and Success Factors
Preservation of Relevant Building Blocks
SASEGASA – More than the Sum of All Parts
Analysis of Population Dynamics
Characteristics of Offspring Selection and the RAPGA
Combinatorial Optimization: Route Planning
Evolutionary System Identification
Applications of Genetic Algorithms: Combinatorial Optimization
Data-Based Modeling with Genetic Programming
Conclusion and Outlook