Representations for Genetic and Evolutionary Algorithms

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.