Evolutionary Computation
Overview
Evolution
The Algorithm of Life
Evolutionary Algorithm
Same pattern for (almost) all evolutionary methods
Artifical Evolution in Action
Historical perspective
- Evolutionary Strategies
- developed by Rechenberg, Schwefel, etc. in 1960s
- focus: real-valued parameter optimization
- Evolutionary Programming
- developed by Fogel et al in 1960s
- focus: evolve intelligent behavior with Finite State Machines
- Genetic Algorithms
- developed by Holland in 1960s
- focus: robust, adaptive systems, reproduction via mutation and recombination
- Genetic Programming
- developed by Koza in 1988
- focus: evolution of programs
Applications
- Software design
- Robotics and hardware design
- Biology and bioinformatics
- Management, scheduling
- Economics, trading systems
- and more
Well-known algorithms
- CMA-ES
- Covariance Matrix Adaptation Evolutionary Strategy
- Continuous optimization
- NSGA-II
- Non-dominated Sorting Genetic Algorithm II
- Multi-objective optimization
- NEAT
- Neuroevolution of Augmenting Topologies
- Evolution of neural networks
- MAP-Elites
- Illuminating Search Spaces by Mapping Elites
- Evolution of behavior
Resources
Evolutionary computation methods in many languages
- ECJ: very mature, general framework, Java
- GPLAB: genetic programming, MATLAB
- Optimization Toolbox: implements genetic algorithm, MATLAB
- pycma: CMA-ES, Python
- pymoo: Multi-objective, Python
- BEAGLE: framework, C++
- MABE: new framework, C++
- eaopt: new generic, Go
and many many more
In this class
- Genetic Algorithms: Mutation, Crossover, TSP
- Evolutionary Algorithms: 1+1, 1+lambda
- Evolutionary Strategies: Continuous optimization
- Neuroevolution: Neural network optimization with ES
- Multi-Objective Optimization: NSGA-II
- Behavior and Novelty: behavioral diversity, novelty search and Quality Diversity
- Genetic Programming: Tree-based representation
- Symbolic Regression: Data function optimization
Evogym project: Form and policy
Not in this class
- Estimation of distribution algorithms
- Evolutionary Programming
- Artificial Immune Systems
- Learning Classifier Systems
- Surrogate models
- Swarm intelligence
- Particle Swarm Optimization
- Simulated annealing
The GECCO (Genetic and Evolutionary Computation Conference) Proceedings include excellent tutorials on many of these subjects for further reading.
Exercise
Break into groups and discuss:
What drives selection in biological evolution? Can these selection pressures be expressed, quantified, or measured? How can we replicate selection pressures in artificial evolution?
