The power of natural selection

Last week I wrote a version of Richard Dawkins’s “methinks it is a weasel” program (as explained in The Blind Watchmaker). The point of the program is to demonstrate the power of cumulative selection in comparison to pure chance. Consider a random string such as “in the beginning god created the heavens and the earth”. In a purely random process, the probability of this string occurring is minuscule: with 27 letters in the alphabet (don’t forget the space!) and 54 letters in the string, the number of possible strings is 2754, or 1.97 x 1077. Your chances of hitting on this string by producing random strings are, for all practical purposes, zero.

But the situation changes once we introduce selection and cumulation. The program begins by creating a population of random strings, each 54 letters in length. None of these will be very close to the target string “in the beginning god created the heavens and the earth”. Nevertheless, some strings will match the target string in a few positions. The program evaluates each one to determine the best match. For example, the following best candidate in generation 1 (from an actual run of the program) shares 7 letters with the target string. These are underlined:

 gen 1: tashiwwsmsianhdfyf yvrrjutym bjjoig byxfpkwpkkhzfj g h
target: in the beginning god created the heavens and the earth

The program then takes this one best match and mutates it to create a new population of candidate strings. For example, each letter (in each string in the population) might be replaced with a randomly chosen letter from the alphabet with a probability of 0.09 (resulting, in this case, in around 4.8 replaced letters per string on average). This new population of strings is then again evaluated, and the best match to the target string is again retained and mutated. The mutations can be either neutral (if a non-matching letter is replaced with a non-matching letter, or if a matching letter is replaced with itself), detrimental (if a matching letter is replaced with a non-matching one) or beneficial (if a non-matching letter is replaced with a matching one).

Many generation will yield none or only small improvements — for example, when a new population of 100 strings was created based on the first generation string above, the best candidate in the second generation had gained only one matching letter (underlined) in addition to a number of neutral mutations:

 gen 2: tashiwwsmsitnhdfyfvyvrrjutym bjjoig byxfhkwpkkhzfj gth
 gen 1: tashiwwsmsianhdfyf yvrrjutym bjjoig byxfpkwpkkhzfj g h
target: in the beginning god created the heavens and the earth

This cumulative process of mutation and selection continues until each letter in the string matches the target string, at which point the program stops. Needless to say, in the beginning most mutations will be neutral. As the string approaches the target string, more and more mutations will be detrimental, or in other words, the program can take quite a number of generations towards the end to optimize the last few letters.

I would offer my own version to the internet, but it seems redundant since a nice Python version of it is already available, and it is easier to play around with the source code of the Python program than with the code of my Objective-C implementation. (On a Mac, you can run the Python version by opening a Terminal, cd-ing to the directory of the, and running: “python”.)

The main message of the program is that cumulative selection is very different from random generation. In a typical run of the program, it takes around 112 generations to select the target string. If the proverbial monkeys tapping away randomly at typewriters produced one string per second, it would take them 6 x 1069 years to explore all the possible strings of 54 letters. The equivalent selection process — also producing one string per second — would be completed after only 31 hours. Such is the power of random variation coupled with cumulation!

The program has been criticized for exaggerating the power of selection. The critics argue that the program retains correct letters permanently and does not allow them to mutate any more, which is obviously not how mutations work in nature. However, the criticism backfires, since the selection process of the program works fine even if all letters are allowed to mutate in each generation. (Note: That all letters are allowed to mutate does not mean that all letters will mutate; this depends on the mutation rate, discussed below.) Both my implementation and the Python version allow all strings to mutate: it is entirely possible for the number of differences to the target string to increase from one generation to the next, and this often happens. Nevertheless, over time the deleterious mutations are removed.

When I’ve talked about this program in my lectures, some students were concerned about a kind of cheating. They felt that the program “already knew” the target string, so that it did not mirror evolution in nature, where the outcome is unknown. Maybe there is a version of this objection that I have not considered, but generally speaking I think it misses the point. The evolved string is found by the program through a process of blind variation and selection (just as in nature); the target string is only used to determine the “fitness” of a particular letter in a particular location. This reflects actual selection processes: biological variations will also have fitness values relative to the environment in which they occur.

It is instructive to consider how variations in the parameters “mutation rate” and “population size” affect the selection process. The mutation rate, in this program, is a number between 0 and 1. It determines the probability with which an individual letter in a string is replaced during the production of a new population of strings. Trivially, a mutation rate of 0 means no mutations and thus no change in the strings over time. A mutation rate of 1 means that each letter is mutated in each generation, which amounts to the absence of cumulative selection: gains in one generation are not retained in the next. For cumulative selection to work, mutation rates have to be relatively low (try it). In my experiments, mutation rates much above 0.1 generally lead to a selection process that oscillates around a certain number of differences and does not terminate. The reason for this is clear: high mutation rates interfere with the retention of matching letters.

More surprising perhaps are variations of the population size. This variable determines how many strings are produced (and mutated) in each generation. Even though I should have known better, I expected this not to matter too much: I was thinking about the total number of variations produced, and so surely it should be immaterial whether I’m producing 300 generations x 100 strings or 3000 generations x 10 strings — the total number of strings is the same. But this is where so-called “genetic drift” becomes an issue! Consider that each generation begins with a “best candidate” string and produces a population of mutated variants of it. In a reasonably large population, there will be many neutral or detrimental variants and a few improved ones; the improved ones are then selected as the template for the next generation. However, the smaller the population size, the more probable it becomes that none of the few produced variants are improvements. It is easy to see this if you assume a population size of 1: most one-off variants of a string will not be improvements, especially in the latter parts of the selection process (when most letters already match the target). Thus, small population sizes make it possible for the string to start to “drift” randomly, simply because each generation only realizes a small sample of possible variations, most of which are neutral or detrimental.

However, the effects of population size and mutation rate interact. For instance, a mutation rate of 0.09 and a population size of 1000 will allow “in the beginning god created the heavens and the earth” to evolve. If you change the population size to 100, then the process will not terminate: it will oscillate between 10 and 15 differences or so. If you now reduce the mutation rate a bit, say to 0.05, then the process will again terminate. I leave it as an exercise for the reader to figure out the explanation of the phenomenon!