Skip to content

Evolution of Code

Genetic Algorithms

  1. Create an initial population
    • The creature has a genotype and a phenotype (gene and phenomenon). Genotype is the data that passes down from generation to generation, and Phenotype is the expression of that data.
  2. Selection
    • Decide a fitness function to calculate a fitness score for each creature. This is our programmatic way of simulating "survival of the fittest".
    • Create a mating pool - choose some parents to reproduce for the next generation.
      1. Elitist method: Choose the fittest individuals to be the parents. This is bad for variety.
      2. Probabilistic method: Use a wheel of fortune, where the probability of each parent is determined by their normalized fitness score.
    • Note: This part can be interactive. Instead of calculating fitness programmatically, we can let people decide what creatures should pass on their genes. This is usually a lengthy process because people are far less efficient than computers, and it can be boring. One solution is to crowd-source this process or hide it behind a disguise. For example, Karl Sims had an exhibition in 1997, Galapagos, where he showed images on screens and used the length of time the audience looked at an image to decide that image's fitness.
  3. Reproduction
    • Crossover. Produce the next generation's genes by combining the genes from the parents.
      1. Method 1: Midpoint. Find a midpoint. Inherit one parent's genes for the left of the midpoint, and the other parent's for the right.
      2. Method 2: Coin-flip. For each gene, randomly decide which parent to inherit from.
    • Mutation. An optional step to add variety. Each gene has a probability (the mutation rate) to mutate into another gene. Be careful, if the mutation rate is too high, the effect of inheritance is effectively eliminated.

Key variables

  • Mutation rate
  • Population
  • Fitness function
  • How to encode genotype

Smart cars

A simple genetic algorithm for evolving the cars (blue triangles) to arrive at the destination (orange circle). The genotype is a list of Vec2, one for each frame's acceleration direction during a car's lifespan. The fitness score takes three things into consideration: 1) distance to target, 2) line of sight to target, and 3) whether it hit an obstacle.

Ecosystem simulation

The genetic algorithm listed above has its great value in computer science applications, but is not exactly accurate if we try to simulate evolution in nature with it. A population doesn't just all give birth and die at once, and they certainly don't all have the same life span. There are more restrictions in reproduction - genders, asexuality, physical locations, and feasibility. In nature, luck is also at play when deciding the fate of a creature. These are all things to think about when using a genetic algorithm to simulate a natural-looking system.

References