daniel shiffman

Examples

GA_Shakespeare.zip

Related

The Computational Beauty of Nature, Gary William Flake, Chapter 20 — Genetics and Evolution

Craig Reynolds’ resources on genetic algorithms, evolutionary programming, and genetic programming.

Exercises

Taking the “To be or not to be.” example, can you evolve text in a more interesting way? What if your goal isn’tt to match an exact phrase? What if each element of the DNA isn’t one character, but is a word, sentence, paragraph, etc? Can you evolve some type of language, poetry, narrative?

Take the Boid class from last week and assign DNA to each boid by using maxspeed, maxforce, weights for rules, etc. as elements of that DNA. Can you develop a goal for the boids and a corresponding fitness function? Can you “evolve” some type of individual or group behavior?

Design an image that is generated via DNA (for example, consider color, size, shape, etc.) Perhaps you could encode the rules of an L-System as DNA? Or somehow treat pixels as DNA? How can you assign fitness? Can you allow the user to rate and evolve their own imagery?

Genetic Algorithms

In many of our examples, we’ve made objects with various behaviors and characteristics — virtual plants, autonomous steering agents, attractive bodies, etc. In a lot of cases, we’ve picked pseudo-random numbers in order to initialize these properties as well as assigned simple rules to determine motion behaviors. What if we could encode the properties and behaviors of our objects into DNA-like structures and simulate the elements of biological adaptation — variation, heredity, and selection — in order to evolve the properties and behaviors of our objects?

A genetic algorithm refers to the process of evolving populations of DNA-like data (encoded as a series of bits, 0s and 1s).

SETUP

Step 1: The Population

Create an empty population (an array or ArrayList)

Fill it with DNA encoded objects (pick random values to start)

 
LOOP (for some given amount of time)

Step 1: Selection

Create an empty mating pool (an empty ArrayList)

For every member of the population, evaluate its fitness based on some criteria / function, and add it to the mating pool in a manner consistent with its fitness, i.e. the more fit it is the more times it appears in the mating pool, in order to be more likely picked for reproduction.

 
Step 2: Reproduction

Create a new empty population

Fill the new population by executing the following steps:
     1. Pick two “parent” objects from the mating pool.
     2. Crossover — create a “child” object by mating these two parents.
     3. Mutation — mutate the child’s DNA based on a given probability.
     4. Add the child object to the new population.

Replace the old population with the new population and continue looping. . . .

 
Strictly speaking, a genetic algorithm involves the use of virtual DNA encoded as bits and follows a series of precise steps. In this week’s first example, we will attempt to adhere as closely as possible to the strict definition of a genetic algorithm. However, we will employ some minor shortcuts. As we continue with further examples, we may also find it more convenient to a bit more flexible. For example, we might encode our DNA as an array of floating point values (instead of bits), and use custom random number distributions to mutate (as opposed to flipping bits). In addition, we might expand our concept of selection, creating systems where objects have built-in lifespans, mate based on an intersection test, etc.

Evolving Text

Our first example is somewhat trivial in nature — we use it to demonstrate the process and strategy behind coding a genetic algorithm. In this example, we will create a population of random phrases, as well as a target phrase. Each random phrase’s fitness will be evaluated according to how close it resembles the target phrase. As the phrases continue to “evolve”, they will eventually reach the target sequence of characters.

What’s interesting about this example is it proves the power of genetic algorithms over brute force algorithms. To randomly arrive at a the phrase “To be or not to be.” would take unfathomable amounts of time, yet genetics allows us to get there potentially within seconds.

Nevertheless, this case is not terribly interesting simply because the “answer” is known. We could easily arrive at the target phrase because, well, we already know the target phrase!

More interesting examples (several of which are described in Chp 20 of CBON) involve using the evolutionary process to find solutions in seemingly unknowable situations (where the variables of the system are too numerous to use conventional methods.)

Some Code

The first thing we need to do is encode our virtual DNA. For this we create a DNA class — it contains an array of characters (the “DNA” or “genotype”). We have two constructors — one that fills that new DNA sequence with random characters and one that fills it based on an existing array.

class DNA {

  // The genetic sequence
  char[] dna;

  // Constructor (makes a random DNA)
  DNA(int num) {
    dna = new char[num];
    for (int i = 0; i < dna.length; i++) {
      dna[i] = (char) random(32,128);  // Pick from range of chars
    }
  }

  // Constructor #2, creates the instance based on an existing character array
  DNA(char[] newdna) {
    dna = (char []) newdna.clone();
  }

Next we need a method to calculate fitness. Here, the fitness is a value between 0 and 1.0, the percentage of “correct” characters:

  // Fitness function (returns floating point % of "correct" characters)
  float fitness (String target) {
     int score = 0;
     for (int i = 0; i < dna.length; i++) {
        if (dna[i] == target.charAt(i)) {
          score++;
        }
     }
     float fitness = (float)score / (float)target.length();
     return fitness;
  }

Finally, we need two methods, one for “crossover” (a method that takes a given object’s current DNA sequence and combines it with another’s), and one for “mutation” (a method that mutates given characters in the sequence randomly, according to some probability).

  // Crossover
  DNA mate(DNA partner) {
    // A new child
    char[] child = new char[dna.length];
    int crossover = int(random(dna.length)); // Pick a midpoint
    // Half from one, half from the other
    for (int i = 0; i < dna.length; i++) {
      if (i > crossover) child[i] = dna[i];
      else               child[i] = partner.getDNA(i);
    }
    // make a new DNA object
    DNA newdna = new DNA(child);
    return newdna;
  }

  // Based on a mutation probability, picks a new random character
  void mutate(float m) {
    for (int i = 0; i < dna.length; i++) {
      if (random(1) < m) {
        dna[i] = (char) random(32,128);
      }
    }
  }

Once our DNA class is complete, we can develop a population class that implements the functionality outlined above in the process of virtual evolution. The goal is to create a simple “main” program (i.e. setup() and draw()) where all that is required is to call methods from the population class step by step. For example:

Population popul;

void setup() {
  String phrase = "To be or not to be.";
  int popmax = 150;
  float mutationRate = 0.01f;
  popul = new Population(phrase,mutationRate,popmax);    //**SETUP: STEP 1 — INITIALIZING THE POPULATION **//
}

void draw() {
 popul.calcFitness();          //**LOOP: STEP 1a — FITNESS CALCULATION**//
 popul.naturalSelection();     //**LOOP: STEP 1b — CREATING THE MATING POOL **//
 popul.generate();             //**LOOP: STEP 2b — CREATING THE NEXT GENERATION **//

}

(The full code for the population class is available in GA_Shakespeare.zip.) Examining the code, we see each population object has the following instance variables:

  int MAX;                      // Population maximum
  float mutationRate;           // Mutation rate
  DNA[] population;             // Array to hold the current population
  float[] fitness;              // Separate array to hold corresponding fitness value for each "organism"
  ArrayList darwin;             // ArrayList which we will use for our "mating pool"
  String phrase;                // Target phrase
  int generations;              // Number of generations
  boolean finished;             // Are we finished evolving?

The crucial two steps are creating and filling the mating pool, as well as creating the next generation based on that mating pool. Each member of the population has a fitness stored in an array of identical size (filled in the calcFitness method.) In order to create our weighted mating pool (with high fitness DNA more likely to be picked for mating), we must calculate the fitness normal for each DNA sequence, using that value to calculate the number of times each object should appear in the mating pool (we use an ArrayList data structure to manage the pool.) To accomplish this we multiply the fitness normal by 1000. For example, a fitness normal of 0.003 would yield 30 entries into the mating pool, 0.0001 would yield 1 entry, 0.

  // Generate a mating pool
  void naturalSelection() {
    // Clear the ArrayList
    darwin.clear();

    // Calculate total fitness of whole population
    float totalFitness = getTotalFitness();

    // Calculate *normalized* fitness for each member of the population
    // based on normalized fitness, each member will get added to the mating pool a certain number of times
    // a higher fitness = more entries to mating pool = more likely to be picked as a parent
    // a lower fitness = fewer entries to mating pool = less likely to be picked as a parent
    for (int i = 0; i < population.length; i++) {
      float fitnessNormal = fitness[i] / totalFitness;
      int n = (int) (fitnessNormal * 10000.0f);  // There are better ways to do this. . .
      for (int j = 0; j < n; j++) {
        darwin.add(population[i]);
      }
    }
  }

Once the mating pool is complete, the next step is easy. We refill our main population array by picking two parents and using the crossover and mutation methods written into our DNA class.

  // Create a new generation
  void generate() {
    // Refill the population with children from the mating pool
    for (int i = 0; i < population.length; i++) {
      int m = int(random(darwin.size()));
      int d = int(random(darwin.size()));
      DNA mom = (DNA) darwin.get(m);
      DNA dad = (DNA) darwin.get(d);
      DNA child = mom.mate(dad);
      child.mutate(mutationRate);
      population[i] = child;
    }
    generations++;
  }