Saturday, November 01, 2014

Weasel

Dawkin’s Weasel Evolution Model

Here is some Javascript to implement Dawkin’s Weasel algorithm as demonstrated in the 1987 BBC Horizon program “The Blind Watchmaker”. The algorithm is supposed to demonstrate the evolutionary process of cumulative natural selection, it is in fact simply a stochastic search algorithm with a future target .. but an interesting toy problem nonetheless.

LIVE DEMO HERE

The algorithm works as follows:

  1. select a random string of length k and make it our current string
  2. select a target string of length k
  3. generate p copies of the current string
  4. mutate the letters in each of the copies with probably m for random letters
  5. score s each copy by counting the number of correct characters that match the target
  6. choose the string with highest score to be the current string
  7. repeat steps 3 - 6 until the score s=k
    (we restrict the algorithm to only work on uppercase characters and spaces n=27)

First let’s define some helper functions and the set of characters we will be choosing strings from

/* the set of available chatacters */
var options = [" ","A","B","C","D","E","F","G","H",
               "I","J","K","L","M","N","O","P","Q",
               "R","S","T","U","V","W","X","Y","Z"];

/* function: create an array [0..i] */
var range = function (i) {
    return i?range(i-1).concat(i):[];
};

/* function: generate random number min <= r <= max */
var rand = function (min, max) {
    return Math.floor(Math.random() * (max - min)) + min;
};

/* function: generate a random string of length k */
var getRandomString = function (k) {
    return range(k).map(function () {
        return options[rand(0,k-1)].toLowerCase();
    }).join('');
};

/* function: capitalise letter */
var capitalise = function (string, i)
{
    var start = string.slice(0,i),
        letter = string.charAt(i).toUpperCase(),
        end = string.slice(i+1);
    return start + letter + end;
};

Now we will define the evolve() function. We need to initialise some parameters including a cutoff to make sure the algorithm doesn’t carry on forever if it doesn’t converge.

var evolve = function (init, target, p, m) {
    var k = init.length, // number of letters in string
        n = options.length, // number of characters to use
        cutoff = 1000, // failsafe to stop if not converging
        iter = 0; // initiliase iteration counter
    ...    

Let’s define some functions inside of the evolve function. We want to use the closure of evolve so that we can make use of the parameters in sub-functions. We will take a “functional” approach to programming this, so will rely on functions like map(), filter(), reduce() etc.

We can now define a function called clone() that will make p copies of the initial string

/* function: create p clones of the string */
var clone = function (string, p) {
    return range(p).map(function () {
        return string;
    });
};

Similarly, we will define a mutate() function, which takes a string and mutates letters with probability m. This function will be called from a map() on the array of cloned strings.

/* function: mutate letters with probability m */
var mutate = function (string) {
    var map = Array.prototype.map;
    return map.call(string, function (letter) {
        if (Math.random() < m) {
            return options[rand(0,k-1)].toLowerCase(); // mutate
        } else {
            return letter; // don't mutate
        }
    }).join('');
};

Now our score() function will map() each mutated string and generate a score for it, replacing the original string with an object containing the string and its score.

/* function: score the string compared to the target */
var score = function (string) {
    var output,
        filter = Array.prototype.filter,
        matched = filter.call(string, function (letter, i) {
        if (letter.toUpperCase() === target[i]) {
            string = capitalise(string, i);
            return true;
        }
    });
    output = {string: string, score: matched.length};
    return output;
};

Here is a function that will select the best string (the first string with the highest score) when called from a reduce() function on our array of mutated copies.

/* function: select the best scored string */
var best = function (prev, curr) {
    if (!prev || curr.score > prev.score) {
        return curr;
    } else {
        return prev;
    }
};

So now let’s plug it all together and run it.

/* the set of available chatacters */
var options = [" ","A","B","C","D","E","F","G","H",
               "I","J","K","L","M","N","O","P","Q",
               "R","S","T","U","V","W","X","Y","Z"];

/* function: create an array [0..i] */
var range = function (i) {
    return i?range(i-1).concat(i):[];
};

/* function: generate random number min <= r <= max */
var rand = function (min, max) {
    return Math.floor(Math.random() * (max - min)) + min;
};

/* function: generate a random string of length k */
var getRandomString = function (k) {
    return range(k).map(function () {
        return options[rand(0,k-1)].toLowerCase();
    }).join('');
};

/* function: capitalise letter */
var capitalise = function (string, i)
{
    var start = string.slice(0,i),
        letter = string.charAt(i).toUpperCase(),
        end = string.slice(i+1);
    return start + letter + end;
};

var evolve = function (init, target, p, m) {
    var k = init.length, // number of letters in string
        n = options.length, // number of characters to use
        cutoff = 1000, // failsafe to stop if not converging
        iter = 0; // initiliase iteration counter

    /* function: create p clones of the string */
    var clone = function (string, p) {
        return range(p).map(function () {
            return string;
        });
    };

    /* function: mutate letters with probability m */
    var mutate = function (string) {
        var map = Array.prototype.map;
        return map.call(string, function (letter) {
            if (Math.random() < m) {
                return options[rand(0,k-1)].toLowerCase(); // mutate
            } else {
                return letter; // don't mutate
            }
        }).join('');
    };

    /* function: score the string compared to the target */
    var score = function (string) {
        var output,
            filter = Array.prototype.filter,
            matched = filter.call(string, function (letter, i) {
            if (letter.toUpperCase() === target[i]) {
                string = capitalise(string, i);
                return true;
            }
        });
        output = {string: string, score: matched.length};
        return output;
    };

    /* function: select the best scored string */
    var best = function (prev, curr) {
        if (!prev || curr.score > prev.score) {
            return curr;
        } else {
            return prev;
        }
    };

    // initialise the current best string
    var bestString = score(init); 

    /* run this on an interval timer to slow it down */
    var timer = setInterval(function () {
        var scores = clone(bestString.string, p)
        .map(mutate)
        .map(score);

        bestString = scores.reduce(best);
        console.log(iter, bestString, running);

        if (bestString.score === k || iter === cutoff) {
            clearInterval(timer);
        }
        iter++;
    }, 100);
};

var initialString = getRandomString(28),
    targetString = "METHINKS DAWKINS GOTIT WRONG",
    p = 100,
    m = 0.04;
evolve(initialString, targetString, p, m);

You can run this code using nodeJS on the command line.

No comments: