Table of Contents
List of Tables . . . . . . . . . . . . . . . . . . . . . . . xi
List of Figures . . . . . . . . . . . . . . . . . . . . . . xv
List of Algorithms . . . . . . . . . . . . . . . . . . . . . xxiii
Introduction . . . . . . . . . . . . . . . . . . . . . . . . xxv
1 Simulating Evolution: Basics about Genetic Algorithms . . . . 1
1.1 The Evolution of Evolutionary Computation . . . . . . . . . 1
1.2 The Basics of Genetic Algorithms . . . . . . . . . . . . . 2
1.3 Biological Terminology . . . . . . . . . . . . . . . . . . 3
1.4 Genetic Operators . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Models for Parent Selection . . . . . . . . . . . . . . . 6
1.4.2 Recombination (Crossover) . . . . . . . . . . . . . . . . 7
1.4.3 Mutation . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.4 Replacement Schemes . . . . . . . . . . . . . . . . . . . 9
1.5 ProblemRepresentation . . . . . . . . . . . . . . . . . . . 10
1.5.1 Binary Representation . . . . . . . . . . . . . . . . . . 11
1.5.2 Adjacency Representation . . . . . . . . . . . . . . . . 12
1.5.3 Path Representation . . . . . . . . . . . . . . . . . . . 13
1.5.4 Other Representations for Combinatorial Optimization
Problems . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.5 Problem Representations for Real-Valued Encoding . . . . 14
1.6 GA Theory: Schemata and Building Blocks . . . . . . . . . . 14
1.7 Parallel Genetic Algorithms . . . . . . . . . . . . . . . . 17
1.7.1 Global Parallelization . . . . . . . . . . . . . . . . . 18
1.7.2 Coarse-Grained Parallel GAs . . . . . . . . . . . . . . . 19
1.7.3 Fine-Grained Parallel GAs . . . . . . . . . . . . . . . . 20
1.7.4 Migration . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8 The Interplay of Genetic Operators . . . . . . . . . . . . 22
1.9 Bibliographic Remarks . . . . . . . . . . . . . . . . . . . 23
2 Evolving Programs: Genetic Programming . . . . . . . . . . . 25
2.1 Introduction: Main Ideas and Historical Background . . . . 26
2.2 Chromosome Representation . . . . . . . . . . . . . . . . . 28
2.2.1 Hierarchical Labeled Structure Trees . . . . . . . . . . 28
2.2.2 Automatically Defined Functions and Modular Genetic
Programming . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.3 Other Representations . . . . . . . . . . . . . . . . . . 36
2.3 Basic Steps of the GP-Based Problem Solving Process . . . . 37
2.3.1 Preparatory Steps . . . . . . . . . . . . . . . . . . . . 37
2.3.2 Initialization . . . . . . . . . . . . . . . . . . . . . 39
2.3.3 Breeding Populations of Programs . . . . . . . . . . . . 39
2.3.4 Process Termination and Results Designation . . . . . . . 41
2.4 Typical Applications of Genetic Programming . . . . . . . . 43
2.4.1 Automated Learning of Multiplexer Functions . . . . . . . 43
2.4.2 The Artificial Ant . . . . . . . . . . . . . . . . . . . 44
2.4.3 Symbolic Regression . . . . . . . . . . . . . . . . . . . 46
2.4.4 Other GP Applications . . . . . . . . . . . . . . . . . . 49
2.5 GP Schema Theories . . . . . . . . . . . . . . . . . . . . 50
2.5.1 Program Component GP Schemata . . . . . . . . . . . . . . 51
2.5.2 Rooted Tree GP Schema Theories . . . . . . . . . . . . . 52
2.5.3 ExactGP Schema Theory . . . . . . . . . . . . . . . . . . 54
2.5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.6 Current GP Challenges and Research Areas . . . . . . . . . 59
2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 62
2.8 Bibliographic Remarks . . . . . . . . . . . . . . . . . . . 62
3 Problems and Success Factors . . . . . . . . . . . . . . . . 65
3.1 What Makes GAs and GP Unique Among Intelligent Optimization
Methods? . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2 Stagnation and Premature Convergence . . . . . . . . . . . 66
4 Preservation of Relevant Building Blocks . . . . . . . . . . 69
4.1 What Can Extended Selection Concepts Do to Avoid Premature
Convergence? . . . . . . . . . . . . . . . . . . . . . . . 69
4.2 Offspring Selection (OS) . . . . . . . . . . . . . . . . . 70
4.3 The Relevant Alleles Preserving Genetic Algorithm (RAPGA) . 73
4.4 Consequences Arising out of Offspring Selection and RAPGA . 76
5 SASEGASA - More Than the Sum of All Parts . . . . . . . . . . 79
5.1 The Interplay of Distributed Search and Systematic Recovery
of Essential Genetic Information . . . . . . . . . . . . . 80
5.2 Migration Revisited . . . . . . . . . . . . . . . . . . . . 81
5.3 SASEGASA: A Novel and Self-Adaptive Parallel Genetic
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3.1 The Core Algorithm . . . . . . . . . . . . . . . . . . . 83
5.4 Interactions between Genetic Drift, Migration, and
Self-Adaptive Selection Pressure . . . . . . . . . . . . . 86
6 Analysis of Population Dynamics . . . . . . . . . . . . . . . 89
6.1 ParentAnalysis . . . . . . . . . . . . . . . . . . . . . . 89
6.2 Genetic Diversity . . . . . . . . . . . . . . . . . . . . . 90
6.2.1 In Single-Population GAs . . . . . . . . . . . . . . . . 90
6.2.2 In Multi-Population GAs . . . . . . . . . . . . . . . . . 91
6.2.3 Application Examples . . . . . . . . . . . . . . . . . . 92
7 Characteristics of Offspring Selection and the RAPGA . . . . 97
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 97
7.2 Building Block Analysis for Standard GAs . . . . . . . . . 98
7.3 Building Block Analysis for GAs Using Offspring Selection . 103
7.4 Building Block Analysis for the Relevant Alleles
Preserving GA (RAPGA) . . . . . . . . . . . . . . . . . . . 113
8 Combinatorial Optimization: Route Planning . . . . . . . . . 121
8.1 The Traveling Salesman Problem . . . . . . . . . . . . . . 121
8.1.1 Problem Statement and Solution Methodology . . . . . . . 122
8.1.2 Review of Approximation Algorithms and Heuristics . . . . 125
8.1.3 Multiple Traveling Salesman Problems . . . . . . . . . . 130
8.1.4 Genetic Algorithm Approaches . . . . . . . . . . . . . . 130
8.2 The Capacitated Vehicle Routing Problem . . . . . . . . . . 139
8.2.1 Problem Statement and Solution Methodology . . . . . . . 140
8.2.2 Genetic Algorithm Approaches . . . . . . . . . . . . . . 147
9 Evolutionary System Identification . . . . . . . . . . . . . 157
9.1 Data Based Modeling and System Identification . . . . . . . 157
9.1.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . 157
9.1.2 An Example . . . . . . . . . . . . . . . . . . . . . . . 159
9.1.3 The Basic Steps in System Identification . . . . . . . . 166
9.1.4 Data-Based Modeling Using Genetic Programming . . . . . . 169
9.2 GP-Based System Identification in HeuristicLab . . . . . . 170
9.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 170
9.2.2 Problem Representation . . . . . . . . . . . . . . . . . 171
9.2.3 The Functions and Terminals Basis . . . . . . . . . . . . 173
9.2.4 Solution Representation . . . . . . . . . . . . . . . . . 178
9.2.5 Solution Evaluation . . . . . . . . . . . . . . . . . . . 182
9.3 Local Adaption Embedded in Global Optimization . . . . . . 188
9.3.1 Parameter Optimization . . . . . . . . . . . . . . . . . 189
9.3.2 Pruning . . . . . . . . . . . . . . . . . . . . . . . . . 192
9.4 Similarity Measures for Solution Candidates . . . . . . . . 197
9.4.1 Evaluation-Based Similarity Measures . . . . . . . . . . 199
9.4.2 Structural Similarity Measures . . . . . . . . . . . . . 201
10 Applications of Genetic Algorithms: Combinatorial
Optimization . . . . . . . . . . . . . . . . . . . . . . . . 207
10.1 The Traveling Salesman Problem . . . . . . . . . . . . . . 208
10.1.1 Performance Increase of Results of Different Crossover
Operators by Means of Offspring Selection . . . . . . . 208
10.1.2 Scalability of Global Solution Quality by SASEGASA . . 210
10.1.3 Comparison of the SASEGASA to the Island-Model Coarse-
Grained ParallelGA . . . . . . . . . . . . . . . . . . . 214
10.1.4 Genetic Diversity Analysis for the Different GA Types . 217
10.2 Capacitated Vehicle Routing . . . . . . . . . . . . . . . 221
10.2.1 Results Achieved Using Standard Genetic Algorithms . . . 222
10.2.2 Results Achieved Using Genetic Algorithms with
Offspring Selection . . . . . . . . . . . . . . . . . . 227
11 Data-Based Modeling With Genetic Programming . . . . . . . . 235
11.1 Time Series Analysis . . . . . . . . . . . . . . . . . . . 235
11.1.1 Time Series Specific Evaluation . . . . . . . . . . . . 236
11.1.2 Application Example: Design of Virtual Sensors for
Emissions of Diesel Engines . . . . . . . . . . . . . . 237
11.2 Classification . . . . . . . . . . . . . . . . . . . . . . 251
11.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 251
11.2.2 Real-Valued Classification with Genetic Programming . . 251
11.2.3 Analyzing Classifiers . . . . . . . . . . . . . . . . . 252
11.2.4 Classification Specific Evaluation in GP . . . . . . . . 258
11.2.5 Application Example: Medical Data Analysis . . . . . . . 263
11.3 Genetic Propagation . . . . . . . . . . . . . . . . . . . 285
11.3.1 Test Setup . . . . . . . . . . . . . . . . . . . . . . . 285
11.3.2 Test Results . . . . . . . . . . . . . . . . . . . . . . 286
11.3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . 288
11.3.4 Additional Tests Using Random Parent Selection . . . . . 289
11.4 Single Population Diversity Analysis . . . . . . . . . . . 292
11.4.1 GP Test Strategies . . . . . . . . . . . . . . . . . . . 292
11.4.2 Test Results . . . . . . . . . . . . . . . . . . . . . . 293
11.4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . 297
11.5 Multi-Population Diversity Analysis . . . . . . . . . . . 300
11.5.1 GP Test Strategies . . . . . . . . . . . . . . . . . . . 300
11.5.2 Test Results . . . . . . . . . . . . . . . . . . . . . . 301
11.5.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . 303
11.6 Code Bloat, Pruning, and Population Diversity . . . . . . 306
11.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 306
11.6.2 Test Strategies . . . . . . . . . . . . . . . . . . . . 307
11.6.3 Test Results . . . . . . . . . . . . . . . . . . . . . . 309
11.6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . 318
Conclusion and Outlook . . . . . . . . . . . . . . . . . . . . 321
Symbols and Abbreviations . . . . . . . . . . . . . . . . . . . 325
References . . . . . . . . . . . . . . . . . . . . . . . . . . 327
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359