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