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 Problem Representation ................................. 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 Exact GP 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 among Genetic Drift, Migration, and
Self-Adaptive Selection Pressure ....................... 86
6 Analysis of Population Dynamics ............................. 89
6.1 Parent Analysis ........................................ 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
viii Genetic Algorithms and Genetic Programming
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 Parallel GA ............... 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 ....................... 226
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
|
