Evolutionary Computation
Overview
Evolution
The Algorithm of Life
Biological Evolution
Why do giraffes have such long necks?
Lamarck vs. Darwin
What is true? What do we use in artificial evolution? What benefits could both ideas have?
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
Oftentimes the results obtained with evolutionary algorithms outperform humans, there is a category of awards for this!
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 course
- Genetic Algorithms: Mutation, Crossover, TSP
- Evolutionary Algorithms: 1+1, 1+lambda
- Genetic Programming: Tree-based representation
- Symbolic Regression: Data function optimization
- Evolutionary Strategies: Continuous optimization
- Multi-Objective Optimization: NSGA-II
- Neuroevolution: Neural network optimization with ES
- Behavior and Novelty: behavioral diversity, novelty search and Quality Diversity
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?
