Foreword
Preface
Acknowledgements
Contents
Contributors
1 Characterizing the Effects of Random Subsampling on Lexicase Selection
1.1 Introduction
1.2 Lexicase Selection
1.2.1 Applying Subsampling to Lexicase Selection
1.2.1.1 Down-Sampled Lexicase
1.2.1.2 Cohort Lexicase
1.3 Methods
1.3.1 Evolutionary System
1.3.2 Program Synthesis Problems
1.3.3 Experimental Design
1.3.3.1 Does Subsampling Improve Lexicase Selection's Problem-Solving Success Given a Fixed Computation Budget?
1.3.3.2 Does Subsampling Improve Lexicase Selection's Problem-Solving Success Because it Facilitates Deeper Searches?
1.3.3.3 Does Random Subsampling Reduce the Computational Effort Required to Solve Problems with Lexicase Selection?
1.3.3.4 Does Subsampling Degrade Lexicase Selection's Diversity Maintenance?
1.3.3.5 Does Subsampling Reduce Lexicase Selection's Capacity to Maintain specialists?
1.3.4 Statistical Analyses
1.4 Results and Discussion
1.4.1 Subsampling Improves Lexicase Selection's Problem-Solving Success
1.4.2 Deeper Evolutionary Searches Contribute to Subsampling's Success
1.4.3 Subsampling Reduces Computational Effort
1.4.4 Subsampling Does Not Systematically Decrease Phenotypic Diversity in Lexicase Selection
1.4.5 Cohort Lexicase Enables More Phylogenetic Diversity Than Down-Sampled Lexicase
1.4.6 Subsampling Degrades Specialist Maintenance
1.5 Conclusion
References
2 It Is Time for New Perspectives on How to Fight Bloat in GP
2.1 Introduction
2.2 The Bloat Phenomenon
2.3 Load-Balancing and Parallel GP
2.3.1 Structural Complexity of GP Individuals
2.4 Methodology
2.4.1 Implementation
2.4.1.1 Software Tool
2.4.2 Experiments
2.5 Results
2.5.1 Parallel Model
2.5.2 Sequential Execution
2.6 Conclusions
References
3 Explorations of the Semantic Learning Machine Neuroevolution Algorithm: Dynamic Training Data Use, Ensemble Construction Methods, and Deep LearningPerspectives
3.1 Introduction
3.2 Neuroevolution Overview
3.3 Semantic Learning Machine
3.3.1 Algorithm
3.3.2 Previous Comparisons with Other Neuroevolution Methods
3.4 Experimental Methodology
3.4.1 Datasets and Parameter Tuning
3.4.2 SLM Variants
3.4.3 MLP Variants
3.5 Results and Analysis
3.5.1 SLM
3.5.2 MLP
3.5.3 Generalization and Ensemble Analysis
3.6 Toward the Deep Semantic Learning Machine
References
4 Can Genetic Programming Perform Explainable Machine Learning for Bioinformatics?
4.1 Introduction
4.2 Methods
4.2.1 Metabolomics Data for Osteoarthritis
4.2.2 Linear Genetic Programming Algorithm
4.2.3 TrainingUsingtheFullandtheFocusedFeatureSets
4.2.4 Feature Synergy Analysis
4.3 Results and Discussion
4.3.1 Best Genetic Programs Evolved on the Full Feature Set
4.3.2 Identification of Important Features
4.3.3 Best Genetic Programs Evolved on the Focused Feature Subset
4.4 Conclusion
References
5 Symbolic Regression by Exhaustive Search: Reducing the Search Space Using Syntactical Constraints and Efficient Semantic Structure Deduplication
5.1 Introduction
5.1.1 Motivation
5.1.2 Prior Work
5.1.3 Organization of This Chapter
5.2 Definition of the Search Space
5.2.1 Grammar for Mathematical Expressions
5.2.2 Expression Hashing
5.3 Exploring the Search Space
5.3.1 Symbolic Regression as Graph Search Problem
5.3.2 Guiding the Search
5.4 Steering the Search
5.4.1 Quality Estimation
5.4.2 Priority Calculation
5.5 Experiments
5.5.1 Results
5.6 Discussion
5.6.1 Limitations
5.7 Outlook
References
6 Temporal Memory Sharing in Visual Reinforcement Learning
6.1 Introduction
6.2 Background
6.2.1 Temporal Memory
6.2.2 Heterogeneous Policies and Modularity
6.3 Evolving Heterogeneous Tangled Program Graphs
6.3.1 Programs and Shared Temporal Memory
6.3.2 Cooperative Decision-Making with Teams of Programs
6.3.3 Compositional Evolution of Tangled ProgramGraphs
6.4 Empirical Study
6.4.1 Problem Environments
6.4.2 Ball Catching: Training Performance
6.4.3 Ball Catching: Solution Analysis
6.4.4 Atari Breakout
6.5 Conclusions and Future Work
References
7 The Evolution of Representations in Genetic Programming Trees
7.1 Introduction
7.2 Material and Methods
7.2.1 Representations and the Neuro-Correlate R
7.2.2 Smearedness of Representations
7.2.3 Active Categorical Perception Task
7.2.4 Number Discrimination Task
7.2.5 The Perception-Action Loop for Stateful Machines
7.2.6 Markov GP Brains Using CGP Nodes
7.2.7 Genetic Encoding of GP Brains in a Tree-LikeFashion
7.2.8 GP-Forest Brain
7.2.9 GP-Vector Brain
7.2.10 Evolutionary Process
7.2.11 Augmenting with R
7.3 Results
7.3.1 GP Trees Evolve to Have Representations
7.3.2 Does Augmentation Using R Improve the Performance of a GA?
7.3.3 Smeared Representations
7.4 Discussion
7.5 Conclusions
References
8 How Competitive Is Genetic Programming in Business Data Science Applications?
8.1 Introduction
8.2 Business Needs for Data Science
8.2.1 Business Forecasting
8.2.2 Effective Operation
8.2.3 Growth Opportunities
8.2.4 Multi-Objective Optimization and DecisionMaking
8.3 Data Science Competitive Landscape
8.3.1 Defining Key Competitors for Data Science Applications
8.3.2 Comparison on Business Needs Satisfaction
8.3.3 How Popular Is GP in the Data ScienceCommunity?
8.4 Current State-of-the-Art of Genetic Programming as Business Application Method
8.4.1 Competitive Advantages of GP
8.4.2 Key Weaknesses of GP
8.4.3 Successful Genetic Programming Applications
8.4.3.1 Examples of GP Applications
8.4.3.2 GP Applications with High Value Creation
8.4.3.3 Robust Inferential Sensors
8.4.3.4 Nonlinear Business Forecasting
8.5 How to Increase Competitive Impact of Genetic Programming in Data Science Applications?
8.5.1 Develop a Successful Marketing Strategy
8.5.1.1 Data Science Marketing
8.5.1.2 Marketing to Statistical Community
8.5.1.3 Marketing to Machine Learning Community
8.5.1.4 Marketing to Business Community
8.5.2 Broaden Application Areas
8.5.3 Improved Professional Development Tools
8.5.4 Increase GP Visibility and Teaching in Data Science Classes
8.6 Conclusions
References
9 Using Modularity Metrics as Design Features to Guide Evolution in Genetic Programming
9.1 Introduction
9.2 Modularity in Genetic Programming
9.3 Modularity Metrics
9.3.1 Module
9.3.2 Design Principles for Modularity Metrics
9.3.3 Reuse and Repetition
9.3.4 Reuse and Repetition from Execution Trace
9.4 Using Modularity Metrics to Guide Evolution
9.4.1 Using Design Features During Parent Selection
9.4.2 Using Design Features During Variation
9.5 Experiments and Results
9.5.1 Extracting Modules from Push Programs
9.5.2 Autosimplification
9.5.3 Experimental Set-up and Results
9.6 Conclusions and Future Work
References
10 Evolutionary Computation and AI Safety
10.1 Introduction
10.2 Background
10.2.1 AI Safety
10.2.2 EC and the Real World
10.2.2.1 Supervised Learning
10.2.2.2 Reinforcement Learning
10.3 EC and Concrete AI Safety Problems
10.3.1 Avoiding Negative Side Effects
10.3.2 Reward Hacking
10.3.3 Scalable Oversight
10.3.4 Safe Exploration
10.3.5 Robustness to Distributional Drift
10.4 Discussion
10.5 Conclusion
References
11 Genetic Programming Symbolic Regression: What Is the Prior on the Prediction?
11.1 Introduction
11.2 Motivation
11.2.1 Distribution Mismatch, Problem Difficulty, and Performance
11.2.2 Algorithm Configuration
11.2.3 Understanding the Behaviour of Search Operators
11.3 Previous Work on GP Biases
11.4 Methodology, Experiments, and Results
11.4.1 Reasoning from First Principles
11.4.2 Setup
11.4.3 Initialisation Prior
11.4.4 GPSR Prior
11.4.5 Effect of Tree Depth on Initialisation Prior
11.4.6 Effect of Problem Dimension on Initialisation Prior
11.4.7 Effect of X Range on Initialisation Prior
11.4.8 Comparing the y and Distributions AcrossProblems
11.5 Applications
11.5.1 Algorithm Behaviour and Performance
11.5.2 Algorithm Configuration
11.5.3 Understanding GSGP Mutation
11.6 Conclusions
11.6.1 Limitations and Future Work
Appendix A: Table of Distribution Statistics
References
12 Hands-on Artificial Evolution Through Brain Programming
12.1 Introduction
12.2 Evolution of Visual Attention Programs
12.2.1 Evolution of Visual Recognition Programs
12.3 Problem Statement
12.4 Classification of Digitized Art
12.5 Experiments
12.5.1 Beyond Random Search in Genetic Programming
12.5.2 Ideas for a New Kind of Evolutionary Learning
12.5.3 Running the Algorithm with Fewer Images
12.5.4 Running the Algorithm with 100 Images
12.5.5 Ensemble Techniques and Genetic Programming
12.6 Conclusions
References
13 Comparison of Linear Genome Representations for Software Synthesis
13.1 Introduction
13.2 Linear Genomes: Plush vs. Plushy
13.2.1 Random Genome Generation
13.2.2 Genetic Operators
13.3 Impact on Search Performance
13.3.1 Benchmarks
13.3.2 Benchmark Results
13.4 Genome and Program Structure
13.4.1 Sizes
13.4.2 Presence of ``Closing'' Genes
13.5 Other Considerations
13.5.1 Hyperparameter Fitting
13.5.2 Applicable Search Methods
13.5.3 Automatic Simplification
13.5.4 Serialization
13.5.5 New Epigenetic Markers for Plush
13.6 Conclusion
References
14 Enhanced Optimization with Composite Objectives and Novelty Pulsation
14.1 Introduction
14.2 Background and Related Work
14.2.1 Single-Objective Optimization
14.2.2 Multi-Objective Optimization
14.2.3 Novelty Search
14.2.4 Exploration Versus Exploitation
14.2.5 Sorting Networks
14.2.6 Stock Trading
14.3 Methods
14.3.1 Representation
14.3.2 Single-Objective Approach
14.3.3 Multi-Objective Approach
14.3.4 Composite Multi-Objective Approach
14.3.5 Novelty Selection Method
14.3.6 Novelty Pulsation Method
14.4 Experiment
14.4.1 Experimental Setup
14.4.2 Sorting Networks Results
14.4.3 Stock Trading Results
14.5 Discussion and Future Work
14.6 Conclusion
Appendix
References
15 New Pathways in Coevolutionary Computation
15.1 Coevolutionary Computation
15.2 OMNIREP
15.3 SAFE
15.4 Concluding Remarks
References
16 2019 Evolutionary Algorithms Review
16.1 Preface
16.2 Introduction
16.2.1 Applications
16.3 Fundamentals of Digital Evolution
16.3.1 Population
16.3.2 Population Entities
16.3.3 Generation
16.3.4 Representation and the Grammar
16.3.5 Fitness
16.3.6 Selection
16.3.7 Multi-Objective
16.3.8 Constraints
16.3.9 Exploitative-Exploratory Search
16.3.10 Execution Environment, Modularity and SystemScale
16.3.11 Code Bloat and Clean-Up
16.3.12 Non-convergence, or Early Local Optima
16.3.13 Other Useful Terms
16.4 Traditional Techniques
16.4.1 Evolutionary Strategy, ES
16.4.2 Genetic Algorithms, GA
16.4.3 Genetic Programming, GP
16.4.4 Genetic Improvement, GI
16.4.5 Grammatical Evolution, GE
16.4.6 Linear Genetic Programming, LGP
16.4.7 Cartesian Genetic Programming, CGP
16.4.8 Differential Evolution, DE
16.4.9 Gene Expression Programming, GEP
16.5 Specialized Techniques and Concepts
16.5.1 Auto-Constructive Evolution
16.5.2 Neuroevolution, or Deep Neuroevolution
16.5.3 Self-Replicating Neural Networks
16.5.4 Markov Brains
16.5.5 PushGP
16.5.6 Simulated Annealing
16.5.7 Tangled Program Graph, TPG
16.5.8 Tabu Search
16.5.9 Animal Inspired Algorithms
16.6 Problem-Domain Mapping
16.6.1 Specific Problem-Domain Mappings
16.6.1.1 Variable and Parameter Optimization
16.6.1.2 Symbolic and Polynomial Regression
16.6.1.3 Automated Code Production
16.6.1.4 Regular Expression
16.6.1.5 Circuit Design
16.6.1.6 Code Improvement and Optimization
16.6.1.7 Simulator Testing
16.6.1.8 Walking Robot
16.6.1.9 Automated Machine Learning
16.6.2 Unusual and Interesting Problem-DomainMappings
16.6.2.1 Configuring Neuromorphic Computers
16.6.2.2 Forecasting Financial Markets
16.6.2.3 Predicting Future City Landscapes
16.6.2.4 Designing an Optimized Floor Plan
16.6.2.5 Antenna Design
16.6.2.6 Defect Identification of Electron Microscopy Images
16.7 Challenges
16.8 Predictions
16.9 Final Discussion and Conclusion
16.10 Feedback
References
17 Evolving a Dota 2 Hero Bot with a Probabilistic Shared Memory Model
17.1 Introduction
17.2 The Dota 2 1-on-1 Mid-lane Task
17.3 Related Work
17.3.1 Memory in Neural Networks
17.3.2 Memory in Genetic Programming
17.4 Tangled Program Graphs
17.5 Indexed Memory for TPG
17.6 Dota 2 Game Engine Interface
17.6.1 Developing the Dota 2 Interface
17.6.2 Defining State Space
17.6.3 Defining the Shadow Fiend Action Space
17.6.4 Fitness Function
17.7 Results
17.7.1 TPG Set Up
17.7.2 Training Performance
17.7.3 Assessing Champion TPG Agents Post Training
17.7.4 Characterization of Memory Behaviour
17.8 Conclusion
References
18 Modelling Genetic Programming as a Simple Sampling Algorithm
18.1 Introduction
18.2 Rationale for Modelling Simple Schemata
18.3 Modelling GP
18.3.1 Change in Schema Prevalence Due to Selection
18.3.2 Change in Schema Prevalence Due to Operators
18.4 Empirical Data Supporting the Model
18.5 Ways to Improve GP
18.6 Related Work
18.7 Conclusion
References
19 An Evolutionary System for Better Automatic Software Repair
19.1 Introduction
19.2 Background and Motivation
19.2.1 Related Work
19.2.2 Motivating Examples
19.3 Overview of ARJA-e
19.4 Shaping the Search Space
19.4.1 Exploiting the Statement-Level Redundancy Assumption
19.4.2 Exploiting Repair Templates
19.4.3 Initialization of Operation Types
19.5 Multi-Objective Evolution of Patches
19.5.1 Patch Representation
19.5.2 Finer-Grained Fitness Function
19.5.3 Genetic Operators
19.5.4 Multi-Objective Search
19.6 Alleviating Patch Overfitting
19.6.1 Overfit Detection
19.6.2 Patch Ranking
19.7 Experimental Design
19.7.1 Research Questions
19.7.2 Dataset of Bugs
19.7.3 Parameter Setting
19.8 Results and Discussions
19.8.1 Performance Evaluation (RQ1)
19.8.2 Novelty in Generated Repairs (RQ2)
19.8.3 Effectiveness of Overfit Detection (RQ3)
19.9 Conclusion
References
Index