Week 13: Inexact Optimization
Week of 11/23
Happy Thanksgiving!
Mandatory videos
Heuristics & Approximation Algorithms; Evolutionary Computation; Search Spaces and Fitness Landscapes
Heuristics
Approximation Algorithms
Introduction to Evolutionary Computation
Coding an Evolutionary Algorithm
Decisions to make in Evolutionary Computation
In class: HW5 Review; Example Problems
Evolutionary Algorithms to play with
- Evolving robots
- Boxcar 2d - evolve 2D cars that can drive along a bumpy track
- Genetic walkers - evolve bipedal walking
- Genetic cat - evolving a cat that can jump onto a shelf
- Evolving 2D agents - here a population of agents is evolving to avoid walls, eat other agents, and avoid being eaten
- Picbreeder - evolve your own images
- Biomorphs - click on the pictures to apply selection, click “mutation” button to apply mutation
- Avida-Ed - this is designed to teach biology, but is actually using genetic programming (evolved assembly code)
- Visualization of evolving controllers for a digital car - great Twtiter thread
- Aagos - a system that we built to answer some questions about evolution, both for the purposes of biology and evolutionary computation
- Slime volleyball - evolved neural networks playing slime volleyball (you can play against them too!)
- MAP-Elites robotic arm - the task is for a robotic arm to figure out how to reach a position in the smoothest way. Circle colors indicate the fitness of the best solution for that position (click on them to see it). Note that this app uses MAP-Elites, which works slightly different from other evolutionary algorithms.
- Dishtiny - groups of evolved programs working together to take in resources
- Cephlapods - pretty agents evolving to eat food
- Explore different mutation operators and problem landscapes
- Play with the balance between selection and mutation - the vertical axis is selection the horizontal axis is mutation. The maroon bars represent the fitness of the population (more, higher bars = more fit).
- Good written reference if you want to know more