Genetic Programming Theory and Practice XVII (Genetic and Evolutionary Computation)

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