Representations for Genetic and Evolutionary Algorithms

ISBN-13: 9783642880964 / Angielski / Miękka / 2012 / 290 str.

Franz Rothlauf; D. E. Goldberg

Opis

In the field of genetic and evolutionary algorithms (GEAs), much theory and empirical study has been heaped upon operators and test problems, but problem representation has often been taken as given. This monograph breaks with this tradition and studies a number of critical elements of a theory of representations for GEAs and applies them to the empirical study of various important idealized test functions and problems of commercial import. The book considers basic concepts of representations, such as redundancy, scaling and locality and describes how GEAs'performance is influenced. Using the developed theory representations can be analyzed and designed in a theory-guided manner. The theoretical concepts are used as examples for efficiently solving integer optimization problems and network design problems. The results show that proper representations are crucial for GEAs'success.

Spis treści

1. Introduction.- 1.1 Purpose.- 1.2 Organization.- 2. Representations for Genetic and Evolutionary Algorithms.- 2.1 Genetic Representations.- 2.1.1 Genotypes and Phenotypes.- 2.1.2 Decomposition of the Fitness Function.- 2.1.3 Types of Representations.- 2.2 Genetic and Evolutionary Algorithms.- 2.2.1 Principles.- 2.2.2 Functionality.- 2.2.3 Schema Theorem and Building Block Hypothesis.- 2.3 Problem Difficulty.- 2.3.1 Reasons for Problem Difficulty.- 2.3.2 Measurements of Problem Difficulty.- 2.4 Existing Recommendations for the Design of Efficient Representations for Genetic and Evolutionary Algorithms.- 2.4.1 Goldberg’s Meaningful Building Blocks and Minimal Alphabets.- 2.4.2 Palmer’s Tree Encoding Issues.- 2.4.3 Ronald’s Representational Redundancy.- 3. Three Elements of a Theory of Genetic and Evolutionary Representations.- 3.1 Redundancy.- 3.1.1 Definitions and Background.- 3.1.2 Decomposing Redundancy.- 3.1.3 Population Sizing.- 3.1.4 Run Duration and Overall Problem Complexity.- 3.1.5 Empirical Results.- 3.1.6 Conclusions, Restrictions and Further Research.- 3.2 Building Block-Scaling.- 3.2.1 Background.- 3.2.2 Domino Model without Genetic Drift.- 3.2.3 Population Sizing for Domino Model and Genetic Drift.- 3.2.4 Empirical Results.- 3.2.5 Conclusions.- 3.3 Distance Distortion.- 3.3.1 Influence of Representations on Problem Difficulty.- 3.3.2 Locality and Distance Distortion.- 3.3.3 Modifying BB-Complexity for the One-Max Problem.- 3.3.4 Empirical Results.- 3.3.5 Conclusions.- 3.4 Summary and Conclusions.- 4. Time-Quality Framework for a Theory-Based Analysis and Design of Representations.- 4.1 Solution Quality and Time to Convergence.- 4.2 Elements of the Framework.- 4.2.1 Redundancy.- 4.2.2 Scaling.- 4.2.3 Distance Distortion.- 4.3 The Framework.- 4.3.1 Uniformly Scaled Representations.- 4.3.2 Exponentially Scaled Representations.- 4.4 Implications for the Design of Representations.- 4.4.1 Uniformly Redundant Representations Are Robust.- 4.4.2 Exponentially Scaled Representations Are Fast, but Inaccurate.- 4.4.3 BB-Modifying Representations Are Difficult to Predict.- 4.5 Summary and Conclusions.- 5. Analysis of Binary Representations of Integers.- 5.1 Two Integer Optimization Problems.- 5.2 Binary String Representations.- 5.3 A Theoretical Comparison.- 5.3.1 Redundancy and the Unary Encoding.- 5.3.2 Scaling, Modification of Problem Difficulty, and the Binary Encoding.- 5.3.3 Modification of Problem Difficulty and the Gray Encoding.- 5.4 Empirical Results.- 5.5 Conclusions.- 6. Analysis of Tree Representations.- 6.1 The Tree Design Problem.- 6.1.1 Definition.- 6.1.2 Metrics and Distances.- 6.1.3 Tree Structures.- 6.1.4 Schema Analysis for Graphs.- 6.1.5 Scalable Test Problems for Graphs.- 6.1.6 Tree Encoding Issues.- 6.2 Prüfer Numbers.- 6.2.1 Historical Review.- 6.2.2 Construction.- 6.2.3 Properties.- 6.2.4 The Low Locality of the Prüfer Number Encoding.- 6.2.5 Summary and Conclusions.- 6.3 The Link and Node Biased Encoding.- 6.3.1 Introduction.- 6.3.2 Motivation and Functionality.- 6.3.3 Biased Initial Populations and Non-Uniformly Redundant Encodings.- 6.3.4 The Node-Biased Encoding.- 6.3.5 The Link-and-Node-Biased Encoding.- 6.3.6 Empirical Results.- 6.3.7 Conclusions.- 6.4 The Characteristic Vector Encoding.- 6.4.1 Encoding Trees with the Characteristic Vector.- 6.4.2 Repairing Invalid Solutions.- 6.4.3 Bias and Stealth Mutation.- 6.4.4 Summary.- 6.5 Conclusions.- 7. Design of Tree Representations.- 7.1 Network Random Keys (NetKeys).- 7.1.1 Motivation.- 7.1.2 Functionality.- 7.1.3 Advantages.- 7.1.4 Bias.- 7.1.5 Population Sizing and Run Duration for the One-Max Tree Problem.- 7.1.6 Conclusions.- 7.2 A Direct Tree Representation (NetDir).- 7.2.1 Historical Review.- 7.2.2 Properties of Direct Representations.- 7.2.3 Operators for NetDir.- 7.2.4 Summary.- 8. Performance of Genetic and Evolutionary Algorithms on Tree Problems.- 8.1 GEA Performance on Scalable Test Tree Problems.- 8.1.1 Analysis of Representations.- 8.1.2 One-Max Tree Problem.- 8.1.3 Deceptive Tree Problem.- 8.2 GEA Performance on the Optimal Communication Spanning Tree Problem.- 8.2.1 Problem Definition.- 8.2.2 Theoretical Predictions.- 8.2.3 Palmer’s Test Instances.- 8.2.4 Raidl’s Test Instances.- 8.2.5 Test Instances from Berry, Murtagh, and McMahon (1995).- 8.2.6 Selected Real-World Test Instances.- 8.3 Summary.- 9. Summary, Conclusions and Future Work.- 9.1 Summary.- 9.2 Conclusions.- 9.3 Future Work.- A. Optimal Communication Spanning Tree Test Instances.- A.1 Palmer’s Test Instances.- A.2 Raidl’s Test Instances.- A.3 Berry’s Test Instances.- A.4 Real World Problems.- References.- List of Symbols.- List of Acronyms.