Dawkins’ Weasel

November 14, 2014

In his book The Blind Watchmaker, Richard Dawkins says:

I don’t know who it was first pointed out that, given enough time, a monkey bashing away at random on a typewriter could produce all the works of Shakespeare. The operative phrase is, of course, given enough time. Let us limit the task facing our monkey somewhat. Suppose that he has to produce, not the complete works of Shakespeare but just the short sentence ‘Methinks it is like a weasel’, and we shall make it relatively easy by giving him a typewriter with a restricted keyboard, one with just the 26 (capital) letters, and a space bar. How long will he take to write this one little sentence?

(All of our quotes are shamelessly stolen from Wikipedia.) Then Dawkins suggests that this is a bad analogy for evolution, and proposes this alternative:

We again use our computer monkey, but with a crucial difference in its program. It again begins by choosing a random sequence of 28 letters, just as before … it duplicates it repeatedly, but with a certain chance of random error – ‘mutation’ – in the copying. The computer examines the mutant nonsense phrases, the ‘progeny’ of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL.

Then he discusses a computer program that simulates his monkey, which he says took half an hour to run because it was written BASIC; when he rewrote his program in Pascal the runtime dropped to eleven seconds. His program used this algorithm:

  1. Start with a random string of 28 characters.
  2. Make 100 copies of the string (reproduce).
  3. For each character in each of the 100 copies, with a probability of 5%, replace (mutate) the character with a new random character.
  4. Compare each new string with the target string “METHINKS IT IS LIKE A WEASEL”, and give each a score (the number of letters in the string that are correct and in the correct position).
  5. If any of the new strings has a perfect score (28), halt. Otherwise, take the highest scoring string, and go to step 2.

Your task is to write a program to simulate Dawkins’ monkey. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

6 Responses to “Dawkins’ Weasel”

  1. String manipulation suits Perl down to the ground, here we use implicit lambda functions (which is one of the beauties of perl)

    Duration approx 0.15-0.25 seconds depending on randomness…

    use strict;
    use warnings;
    
    my @letters = (q( ),'A'..'Z');
    my $string = join q(), map {($letters[(rand @letters)])} 1..28;
    my $WEASEL = 'METHINKS IT IS LIKE A WEASEL';
    my $iter = 0;
    
    while( $string ne $WEASEL ) {
      $iter++;
      my( $max_score, $max_word ) = (0,q());
      foreach my $word ( map {( join q(), map {((rand 20 < 1) ? $letters[(rand @letters)] : $_ )} split m{}ms, $string)} 1..100 ) {
        my $score = grep { ! ord $_ } split m{}ms, ($word^$WEASEL);
        ( $max_word, $max_score ) = ($word, $score ) if $score >= $max_score;
      }
      $string = $max_word;
      printf "%4d %2d %s\n", $iter, $max_score, $string;
    }
    
  2. Joost Kremers said

    A Common Lisp version I wrote a number of years ago for a class on the evolution of language:

    (defpackage "WEASEL"
      (:use "COMMON-LISP")
      (:export "EVOLUTION"))
    
    (in-package weasel)
    
    (defvar *target* "METHINKS IT IS LIKE A WEASEL")
    
    (defvar *characters* (cons #\Space
    			   (loop
    			      for c from (char-code #\A) to (char-code #\Z)
    			      collect (code-char c))))
    (defun create (length)
      (concatenate 'string (loop
    			  for i from 1 to length
    			  collect (nth (random (length *characters*)) *characters*))))
    
    (defun procreate (text error-rate n-offspring)
      (loop
         for i from 1 to n-offspring
         collect (map 'string #'(lambda (c)
    			      (if (< (random 100) error-rate)
    				  (nth (random (length *characters*)) *characters*)
    				  c))
    		  text)))
    
    (defun select (candidates)
      (car (sort candidates #'(lambda (x y)
    			    (< (fitness x) (fitness y))))))
    
    (defun fitness (string)
      (loop
         for c1 across string
         for c2 across *target*
         count (char/= c1 c2)))
    
    (defun report (entity generation stream)
      (format stream "Generation: ~A~%Entity: ~A~%Fitness (0 is best): ~A~%~%"
    	  generation entity (fitness entity)))
    
    (defun evolution (&key target (error-rate 1) (report-after 10)
    		  (n-offspring 10) max-generations log)
      (let ((*target* (if target
    		      (remove-if-not #'(lambda (c) (member c *characters*)) target)
    		      *target*)))
        (flet ((evolve (output-stream)
    	     (let ((first (create (length *target*))))
    	       (report first 1 output-stream)
    	       (do ((fittest first (select offspring))
    		    (offspring (procreate first error-rate n-offspring)
    			       (procreate fittest error-rate n-offspring))
    		    (generation 1 (1+ generation)))
    		   ((or (and max-generations (= generation max-generations))
    			(= (fitness fittest) 0))
    		    (report fittest generation output-stream))
    		 (when (and report-after
    			    (= (rem generation report-after) 0))
    		   (report fittest generation output-stream))))))
          (if log
    	  (with-open-file (stream log :direction :output :if-exists :overwrite
    				  :if-does-not-exist :create)
    	    (evolve stream))
    	  (evolve *standard-output*)))))
    
  3. Graham said

    This is a fun genetic algorithm experiment! Thanks for posting it.

    #!/usr/bin/env python3
    
    from random import choice, random
    from string import ascii_uppercase
    
    GENES = "".join([ascii_uppercase, " "])
    TARGET = "ME THINKS IT IS LIKE A WEASEL"
    LENGTH = len(target)
    
    def reproduce(sequence):
        return [sequence] * 100
    
    def mutate(sequence):
        return "".join(choice(GENES) if random() < 0.05 else c for c in sequence)
    
    def fitness(sequence):
        return sum(c == t for (c, t) in zip(sequence, TARGET))
    
    def evolve(max_iters=int(1e3)):
        sequence = "".join(choice(GENES) for _ in range(LENGTH))
        for i in range(max_iters):
            population = map(mutate, reproduce(sequence))
            sequence = max(population, key=fitness)
            score = fitness(sequence)
            print("{0:5}: ({1:5}) {2}".format(i, score, sequence))
            if score == LENGTH:
                return
    
    if __name__ == "__main__":
        evolve()
    
  4. Graham said

    oops! s/ME THINKS/METHINKS

  5. A Java solution:

    public class DawkinWeasel {
    
        private static final Random RANDOM = new Random();
    
        private static final String ASCII_UPPERCASE = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
    
        private static int score(String s1, String s2) {
            int score = 0;
            for (int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) == s2.charAt(i)) score++;
            }
            return score;
        }
    
        private static String mutate(String s, int p) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                if (RANDOM.nextInt(100) < p) {
                    sb.append(randomChar());
                } else {
                    sb.append(s.charAt(i));
                }
            }
            return sb.toString();
        }
    
        private static char randomChar() {
            return ASCII_UPPERCASE.charAt(RANDOM.nextInt(ASCII_UPPERCASE.length()));
        }
    
        private static String randomString(int length) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < length; i++) {
                sb.append(randomChar());
            }
            return sb.toString();
        }
    
        private static int evolveTo(String ref) {
            String s = randomString(ref.length()),
                   bestMatch = s;
            int iterations = 0,
                bestScore = score(s, ref);
            while (true) {
                iterations++;
                for (int i = 0; i < 100; i++) {
                    String mutatedCopy = mutate(s, 5);
                    int score = score(mutatedCopy, ref);
                    if (score == ref.length()) {
                        // Perfect match
                        return iterations;
                    }
                    if (score > bestScore) {
                        bestScore = score;
                        bestMatch = mutatedCopy;
                    }
                }
                s = bestMatch;
            }
        }
    
        public static void main(String[] args) {
            String ref = "METHINKS IT IS LIKE A WEASEL";
            System.out.println("Evolved in " + evolveTo(ref) + " iterations");
        }
    }
    
  6. Tom said

    My attempt at a clojure version here (apologies for formatting):

    
    (ns weasel)
    
    (defn rand-char [] (.charAt "ABCDEFGHIJKLMNOPQRSTUVWXYZ " (rand-int 27)))
    
    (defn mutate [chr-vec]
      (assoc chr-vec (rand-int (count chr-vec)) (rand-char)))
    
    (defn score [target candidate]
      (reduce + (map #(if (= %1 %2) 1 0) target candidate)))
    
    (defn next-gen-best [target candidate]
      (apply max-key #(score target %1) (vec (repeatedly 100 #(mutate candidate)))))
    
    (defn best-fit [target first second]
      (if (> (score target first) (score target second)) first second))
    
    (defn run [target-str]
      (let [target (vec (char-array target-str))
            initial (vec (repeatedly (count target) rand-char))]
      (loop [best initial
             i 0]
        (if (= (score target best) (count target))
          i
          (recur (best-fit target best (next-gen-best target best)) (inc i))))))
    
    ; (run "METHINKS IT IS LIKE A WEASEL")
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: