The Evolution Simulation

The simulation is mentioned in "The Blind Watchmaker", by Richard Dawkins. It is an example showing how natural selection achieves better results for adaptability than random chance.

The idea is to start with a goal string g of upper case letters and spaces, for example 

   METHINKS IT IS LIKE A WEASEL
An initial string of the same length is chosen randomly as the first parent, p. Unless you are really lucky this string will not resemble the goal string.

Measuring the closeness of two strings

We need a way to measure the closeness of such a string to the goal string. If g[0],...,g[n] are the ascii codes of the characters of g and p[0],...,p[n] are the codes for p then the closeness of p to g is defined as 
   closeness(p, g) = abs(p[0] - g[0]) + ... + abs(p[n] - g[n])
This has the useful property that closeness(p,g) = 0 if and only if p = g

Introuducing mutations into a string

We want to see if the initial parent can be made to evolve toward the goal string by introducing random mutations in the initial parent string. Thus, we define a mutated string or child string c derived from p as follows 
   c = p with one character replaced by a random letter or space

A random chance algorithm

As our first evolution attempt we can produce 1 child at each step, and use it as the parent for the next step. Here is the algorithm 
   Choose a goal string g
   Choose an inital parent p randomly
   while (closeness(p,g) > 0)
      Choose new p = mutation of p
   end while
You can try this with the applet below by choosing 1 as the number of children and pressing the start button. The applet uses METHINKS IT IS A WEASEL as a default goal string. You will quickly discover that there is no convergence to the goal string. This is clear since with only one child per generation we have no natural selection, only random chance. Click the suspend button to stop the applet.

You may think that the goal string is too long so type a smaller one such as HELLO and press the start button. Again the chances of producing the goal string is pretty slim.

A natural selection algorithm

The trick is to choose several children at each generation. Each is obtained by a single character mutation from the previous parent. From these children choose the one closest to the goal string as the next parent and continue. Here is the algorithm 
   Choose the number of children, n, per generation
   Choose a goal string g
   Choose an initial parent p randomly
   while (closeness(p,g) > 0)
      Choose n children c[0], ... c[n-1] as mutations of p
      Choose new p as the closest child to g
   end while
Now with a sufficient number of children we obtain rapid evolution to the goal string. For example, try 100 children in the applet and the default goal string. Convergence is obtained in 50 to 60 generations. Experiment with different strings and numbers of children.

The Evolution Simulation Applet (Java 1.0)