Neuroevolution

Sebastian Risi is a Professor at the IT University of Copenhagen, where he directs the Creative AI Lab, and a Research Scientist at Sakana AI. Yujin Tang is a Research Scientist at Sakana AI, with a research focus on machine learning and evolutionary algorithms. David Ha is a cofounder and CEO of Sakana AI. Risto Miikkulainen is a Professor of Computer Science at the University of Texas at Austin and VP of AI Research at Cognizant AI Labs.

Foreword
Online Supplement
Preface
1 Introduction
1.1 Evolving Neural Networks
1.2 Extending Creative AI
1.3 Improving the World
1.4 Plan for the Book
1.5 Plan for Hands-on Exercises
1.6 Chapter Review Questions
2 The Basics
2.1 Evolutionary Algorithms
2.1.1 Representation
2.1.2 Population-Based Search
2.1.3 Selection
2.1.4 Variation Operators
2.1.5 Fitness Evaluation
2.1.6 Reproduction and Replacement 20
2.1.7 Termination 21
2.2 Types of Evolutionary Algorithms 22
2.2.1 Genetic Algorithm 22
2.2.2 Evolution Strategy 24
2.2.3 Covariance-Matrix Adaptation Evolution Strategy 26
2.2.4 OpenAI Evolution Strategy 29
2.2.5 Multiobjective Evolutionary Algorithms 31
2.2.6 Further Evolutionary Computation Techniques 33
2.2.7 Try These Algorithms Yourself 35
2.3 Neural Networks 37
2.3.1 Feedforward Neural Networks 37
2.3.2 Training Feedforward Neural Networks with Gradient Descent 38
2.3.3 Recurrent Neural Networks 40
2.3.4 Long Short-Term Memory 41
2.3.5 Convolutional Neural Networks 43
2.3.6 Transformers 45
2.4 Neuroevolution: An Integrated Approach 47
2.5 Chapter Review Questions 48
3 The Fundamentals of Neuroevolution 49
3.1 Neuroevolution Taxonomy 49
3.1.1 Fixed-Topology Neuroevolution 50
3.1.2 Topology and Weight Evolving Artificial Neural Networks 50
3.1.3 Direct Encoding 51
3.1.4 Indirect Encoding 51
3.2 Case study: Evolving a Simple Walking Agent 52
3.2.1 The Challenge 52
3.2.2 Fitness Function 53
3.2.3 Neural Network Architecture 54
3.2.4 Evolutionary Algorithm 54
3.2.5 Training for Generality 55
3.3 Neuroevolution of Augmenting Topologies 56
3.3.1 Motivation and Challenges 56
3.3.2 Genetic Encoding and Historical Markings 58
3.3.3 Speciation and Fitness Sharing 62
3.3.4 Example: Double Pole Balancing 63
3.4 Scaling up Neuroevolution 66
3.4.1 Neuroevolution vs. Deep Learning 66
3.4.2 Deep Neuroevolution 68
3.4.3 Taking Advantage of Big Compute 70
3.5 Chapter Review Questions 71
4 Indirect Encodings 73
4.1 Why Indirect Encodings? 73
4.2 Developmental Processes 75
4.2.1 Cell-Chemistry Approaches 75
4.2.2 Grammatical Encodings 77
4.2.3 Learning Approaches 81
4.3 Indirect Encoding through Hypernetworks 85
4.3.1 Compositional Pattern Producing Networks 86
4.3.2 Case Study: Evolving Virtual Creatures with CPPN-NEAT 90
4.3.3 HyperNEAT 91
4.3.4 Multiagent HyperNEAT 95
4.3.5 Evolvable Substrate HyperNEAT 98
4.3.6 General Hypernetworks and Dynamic Indirect Encodings 101
4.4 Self-attention as Dynamic Indirect Encoding 103
4.4.1 Background on Self-Attention 104
4.4.2 Self-Attention as a Form of Indirect Encoding 104
4.4.3 Self-Attention Based Agents 106
4.5 Chapter Review Questions 110
5 Utilizing Diversity 111
5.1 Genetic Diversity 111
5.2 Behavioral Diversity 113
5.3 Novelty Search 116
5.4 Quality Diversity Methods 118
5.4.1 Motivation and Challenges 119
5.4.2 Novelty Search with Local Competition 121
5.4.3 MAP-Elites 122
5.4.4 Implementing and Enhancing QD Algorithms 126
5.5 Multiobjectivity 128
5.6 Ensembling 129
5.7 Utilizing Population Culture and History 132
5.8 Chapter Review Questions 136
6 Neuroevolution of Behavior 139
6.1 From Control to Strategy 139
6.2 Discovering Robust Control 143
6.2.1 Noise, Exploration, and Novelty 143
6.2.2 Symmetry, Context, and Adaptation 144
6.2.3 Transfer to Physical Robots 148
6.3 Discovering Flexible Strategies 150
6.3.1 Switching between Behaviors 151
6.3.2 Evolving Cognitive Behaviors 154
6.3.3 Utilizing Stochasticity, Coevolution, and Scale 156
6.4 Decision-Making 158
6.4.1 Successes and Challenges 158
6.4.2 Surrogate Modeling 159
6.4.3 Case Study: Mitigating Climate Change through Optimized Land Use 163
6.4.4 Case Study: Optimizing NPIs for COVID-19 166
6.4.5 Leveraging Human Expertise 171
6.5 Chapter Review Questions 176
7 Neuroevolution of Collective Systems 179
7.1 Cooperative Coevolution 179
7.1.1 Evolving a Single Neural Network 180
7.1.2 Evolving Structured Heterogeneous Networks 182
7.1.3 Evolving a Team 185
7.2 Competitive Coevolution 188
7.2.1 Evolving Single Neural Networks 188
7.2.2 Evolving Multiple Teams 191
7.3 Cellular Automata 194
7.3.1 Evolving Neural Cellular Automata 195
7.3.2 Growing Functional Machines 196
7.3.3 Case Study: Growing Game Levels with QD-Evolved NCAs 198
7.3.4 Evolving Self-Assembling Neural Networks 201
7.3.5 Combining Evolutionary Creativity with Gradient Descent Precision 206
7.4 Chapter Review Questions 208
8 Interactive Neuroevolution 211
8.1 The NERO Machine Learning Game 211
8.2 Incorporating Human Knowledge into NERO 216
8.3 Neuroevolution-enabled Collaboration 220
8.4 Case Study: Collaborative Interactive Neuroevolution Through Play 222
8.5 Making Human Contributions Practical 227
8.6 Chapter Review Questions 229
9 Open-ended Neuroevolution 231
9.1 Open-ended Discovery of Complex Behavior 231
9.1.1 Neutral Mutations with Weak Selection 231
9.1.2 Extinction Events 233
9.1.3 Evolvable Representations 234
9.1.4 Expressive Encodings 237
9.1.5 Major Transitions 238
9.1.6 Open-ended Evolution of Intelligence 240
9.2 Cooperative Coevolution of Environments and Solutions 240
9.2.1 The Influence of Environments 240
9.2.2 Body and Brain Coevolution 241
9.2.3 Coevolution Driven by Interestingness 243
9.3 Competitive Coevolution of Environments and Solutions 246
9.3.1 Paired Open-Ended Trailblazer 246
9.3.2 Learning to Chase-and-Escape
9.4 Chapter Review Questions
10 Evolutionary Neural Architecture Search
10.1 Neural Architecture Search with NEAT
10.2 NAS for Deep Learning
10.3 Case Studies: Improving Deep Learning SOTA
10.3.1 LSTM Designs
10.3.2 CoDeepNEAT
10.3.3 AmoebaNet
10.4 Multiobjective and Multitask NAS
10.5 Making NAS Practical
10.6 Beyond Neural Architecture Search
10.7 Chapter Review Questions 283
11 Optimization of Neural Network Designs 285
11.1 Designing Complex Systems 285
11.2 Bilevel Neuroevolution 286
11.3 Evolutionary Meta-learning 289
11.3.1 Loss functions 289
11.3.2 Activation Functions 292
11.3.3 Data Use and Augmentation
11.3.4 Learning Methods
11.3.5 Utilizing Surrogates
11.3.6 Synergies
11.4 Case Study: Meta-learning vs. Human Design
11.5 Neuroevolution of Neuromorphic Systems
11.5.1 Neuromorphic Computation
11.5.2 Evolutionary Optimization 304
11.5.3 Examples 305
11.5.4 Future Directions 307
11.6 Chapter Review Questions 308
12 Synergies with Reinforcement Learning 311
12.1 Reinforcement learning vs. Neuroevolution 311
12.2 Synergistic Combinations 313
12.2.1 Integrating Population-Based and Reinforcement-Based Search 313
12.2.2 Evolving Value Networks for RL 314
12.2.3 Evolving Starting Points for RL 317
12.3 Evolving Neural Networks to Reinforcement Learn 319
12.3.1 Evolving Hebbian Learning Rules 320
12.3.2 Case Study: Hebbian Learning for Physical Robot Transfer 324
12.3.3 Learning When to Learn through Neuromodulation 327
12.3.4 Indirectly Encoded Plasticity 329
12.3.5 Learning to Continually Learn through Networks with External Memory
12.4 Integrating Evolution, Learning, and Embodiment
12.5 Chapter Review Questions
13 Synergies with Generative AI
13.1 Background on Large Language Models
13.2 Evolutionary Computing Enhances LLMs
13.2.1 Evolutionary Prompt Engineering/Adaptation 340
13.2.2 Evolutionary Model Merging 345
13.3 LLMs Enhance Evolutionary Computing 349
13.3.1 Evolution through Large Models 349
13.3.2 Language Model Crossover 352
13.3.3 LLMs as Evolution Strategies 357
13.3.4 AlphaEvolve 359
13.4 Case Studies: NE-enhanced Generative AI for Game Level Generation 362
13.4.1 MarioGAN 363
13.4.2 MarioGPT 365
13.5 World Models 367
13.5.1 A Simple World Model for Agents 368
13.5.2 Using the World Model for Feature Extraction 370
13.5.3 Training an Agent Inside Its Own World Model 371
13.6 Chapter Review Questions 373
14 What Neuroevolution Can Tell Us About Biological Evolution? 375
14.1 Understanding Neural Structure 375
14.2 Evolutionary Origins of Modularity 379
14.3 Understanding Neuromodulation 381
14.4 Developmental Processes 383
14.4.1 Synergistic Development 383
14.4.2 Development through Genetically Directed Learning
14.5 Constrained Evolution of Behavior
14.6 Case Study: Understanding Human-like Behavior
14.7 Case Study: Understanding an Evolutionary Breakthrough
14.8 Evolution of Language
14.8.1 Biology of Language
14.8.2 Evolving Communication
14.8.3 Evolution of Structured Language 402
14.9 Chapter Review Questions
15 Epilogue
Notes
References
Subject Index
Author Index