Genetic Algorithms and Genetic Programming - Modern Concepts and Practical Applications

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