Introduction To Genetic Algorithms in JavaScript.

Section 1 - The Setup

1.1 - Introduction

A genetic algorithm aims to solve a problem by simulating the process of natural evolution. This is where a species is more likely to survive if it is 'fit' for its local environment, as proposed by Charles Darwin and Alfred Russel Wallace.

In general, a genetic algorithm will first generate a collection of potential solutions then assess the 'fitness' of each candidate solution. Once the relative fitnesses of the possible solutions have been established, the algorithm tells us to select some of the fittest then mutate and evolve this subgroup of potential solutions in someway to create the next generation of candidates and then repeat these steps. Each iteration will increase the overall fitness of the group until an optimal solution is found or an acceptable fitness threshold has been reached.

In this example we shall seek to apply this process to a well-known thought experiment which was first proposed by Richard Dawkins that he called the Weasel Program.

1.2 - The Weasel Program

The Weasel Program is based on the Infinite Monkey Theorem, where a monkey randomly typing on a typewriter, if given sufficient time, will eventually produce the complete works of William Shakespeare.

To simplify this Dawkins proposed only reproducing a single string, 28 characters in length - "methinks it is like a weasel" (Hamlet: Act 3, Scene 2).

To reproduce this string we shall apply the concepts of genetic algorithms. First we shall generate a series of random strings, find the fittest (i.e. most like the target string), mutate them according to pre-defined probability, create a new collection from these strings and repeat.

Our target string will be in uppercase, as will the alphabet. The alphabet string must also contain a space and to reduce the time taken we shall have an unnaturally high probability of mutation (1 in 10).

For our first step we will define 3 constants; the ALPHABET string, the MUT_PROB or probability of mutation and TARGET, which is the actual string we are looking to reproduce.


        var ALPHABET = "ABCDEFGHIJKLMONPQRSTUVWXYZ ";
        var MUT_PROB = 10;
        var TARGET = "METHINKS IT IS LIKE A WEASEL";
    

1.3 - Generate A Potential Solution

The genetic algorithm process begins by creating candidate solutions made up of individual 'genes', in this case a random string, 28 characters in length and made up from our simplified alphabet. The collection of possible solutions is known as a 'gene pool' and the individual solutions are called 'genomes'. To simplify our experiment we shall create a single genome and clone it to create our gene pool, but we shall return to that in due course...

Next we will write a function called generateGenome() which takes no arguments and returns a string 28 characters in length chosen at random from the alphabet.


        var generateGenome = function() {
            var genome = [];

            for (var i = 0; i < 28; ++i) {
                genome[i] = ALPHABET[Math.floor(Math.random() * ALPHABET.length)];
            }

            return genome.join("");
        };
    

1.4 - How Fit?

To gauge how appropriate a solution is we must create a 'fitness function' which can be applied to each solution and will give us an indication of how close to the optimal solution our candidate is. In this example we know exactly what the optimal solution is, the desired string, so we simply compare each character of the candidate string to the corresponding character in the target string, increase a counter when they match and return the final value.

Now we will write a function called getFitness() which takes an argument genome (a string of 28 characters in length) and returns the total number of positions where genome matches TARGET.


        var getFitness = function(genome) {
            var fitness = 0;

            for (var i = 0; i < TARGET.length; ++i) {
                if (genome[i] === TARGET[i]) {
                    fitness++;
                }
            }
            return fitness;
        };
    

1.5 - Generate A Gene Pool

In our simplified case the gene pool will simply be 50 copies of the fittest genome. In more complex examples, where the evolution process is driven by cross-over of genomes as well as random mutation, it may be desirable to have a bit more diversity in the pool but this will illustrate what is required for our simple case and allow you to see where further diversity may be created.

Next we write a function called getGenePool() which takes an argument genome (also string of 28 random characters is length) and returns an array containing 50 copies of genome.


        var getGenePool = function(genome) {
            var pool = [];

            for (var i = 0; i < 50; ++i) {
                pool[i] = genome;
            }
            return pool;
        };
    

1.6 - Find The Fittest In A Gene Pool

Once we have a collection of potential solutions we must establish which has the highest fitness value in this generation. This is acheived by simply iterating through the gene pool, applying the fitness function to each genome and locating the one with the highest fitness function.

To acheive this we create a function called getFittest() which takes an argument pool which is an array of (potentially) different genome strings and returns a single string, the genome with the highest fitness in the array.


        var getFittest = function(pool) {
            var fittestLoc = 0;
            var fittest = 0;

            for (var i = 0; i < pool.length; ++i) {
                if (getFitness(pool[i]) > fittest) {
                    fittest = getFitness(pool[i]);
                    fittestLoc = i;
                }
            }
            return pool[fittestLoc];
        };
    

Section 2 - Mutating And Evolving

2.1 - Mutation Of A Genome

Earlier we defined the probability of mutation of a genome to be 1 in 10, but what does that actually mean? Between generations of living organisms there is a chance that the next generation may be more able to deal with its environment than its ancestors, either by some random change to an organism's characteristics or by the combination of properties given to it by its parents.

The second of these reasons is known in a genetic algorithm as 'cross-over' and, while we will not apply cross-over here, the concept could be applied by selecting two genomes from the gene pool, splitting them each into two at some point and joining the head of one to the tail of the other and vice versa to produce two new genomes of (potentially) different fitness.

Here our random mutation is simply to replace a character with a (potentially) different character from the defined alphabet. We examine each character in each genome, determine randomly if the character should be mutated and if so, replace it. In this simplified example we are implementing the 'locking' variant of the Weasel Program, that is when a character is known to be correct it will not be mutated. The Non-locking variant can take considerably longer to find a solution since it can mutate already fit genes into unfit genes.

Now we define a function called doMutation() which takes a single argument, a now familiar 28 character string called genome, examines each gene in the genome and if the probability dictates, replace the gene with another randomly selected character from the alphabet. Once each gene in the string has been examined, return the new genome string.


        var doMutation = function(genome){
            var newGenome = "";

            for (var i = 0; i < genome.length; ++i) {
                if (Math.floor(Math.random() * MUT_PROB) === 1){
                    if (genome[i] != TARGET[i]) {
                        newGenome += ALPHABET[Math.floor(Math.random() * ALPHABET.length)];
                    }
                    else {
                        newGenome += genome[i];
                    }
                }
                else {
                    newGenome += genome[i];
                }
            }
            return newGenome;
        };
    

2.2 - Do The Evolution

We now have all the constituent elements required to implement a (simplified) genetic algorithm; we can create a geneome made up of randomised genes, a gene pool made up of randomised genomes, determine the fitness of a single genome, the fittest genome in a gene pool and randomly mutate genes in a given genome.

Now we need to put it all together...

Our final function, evolve() takes no arguments, creates a genome and from that genome generates a gene pool. Once this initial set up is completed the evolve() begins to loop; while the fittest genome in a gene pool does not have a fitness of 28, apply the mutation function to each genome then check each fitness again, repeat... Once the while loop has completed, return the desired string.

You might wish to output the fittest genome every 10 iterations or so to see the progress of the evolution. On my machine with a mutation probability of 1 in 10 it takes an average of about 1000 iterations to reproduce the target string; your mileage may vary...


        var evolve = function() {
            var numGens = 0;
            var fittest = generateChild();

            console.log(fittest);

            while (getFitness(fittest) !== 28) {
                numGens ++;
                var pool = cloneFittest(fittest);
                var pool2 = [];
                for (var i = 0; i < pool.length; ++i) {
                    pool2[i] = doMutation(pool[i], true);
                }
                fittest = getFittest(pool2);
                if (numGens % 10 === 0) {
                    console.log(fittest);
                }
            }
            return fittest;
        };
    

2.3 - Conclusions

This has been a very brief introduction to the main concepts used in genetic algorithms and their parent fields of evolutionary computing and biologically inspired AI, rather than a programming excerise. There are many different implementations of the Weasel Program but the main intent was to demonstrate how to use these techniques to solve a problem. Other classic examples of the application of this style of problem solving include the Knapsack problem, the Travelling Salesman problem and whole host of others.

Hopefully you can see how powerful this type of processing can be and it has whet your appetite for further research into this field. I also tried to vary the terms used to describe the constituent parts, for example sometimes referring to characters, sometimes genes. This was to demonstrate how the more theoretical concepts of genetic algorithms and evolutionary computing can be implemented using real world computing concepts.

Other refinements and improvements you could make to the Weasel Program include, implementing cross-over of genomes or allowing the variation of the mutation probability.

I hope you have enjoyed and taken something from this!

| see it in action


        /**
         * Author: Peter Somerville (peterwsomerville[at]gmail[dot]com)
         * Version: 1.1
         * 13/2/2013
         * Licensed under: GNU GPL
         */

        /**
         * constants
         */
        var ALPHABET = "ABCDEFGHIJKLMONPQRSTUVWXYZ ";
        var MUT_PROB = 10;
        var TARGET = "METHINKS IT IS LIKE A WEASEL";

        /**
         * Create a 'genome' for Weasel Program
         * @return {String} [28 random chars from ALPHABET]
         */
        var generateGenome = function() {

            var genome = [];

            for (var i = 0; i < 28; ++i) {
                genome[i] = ALPHABET[Math.floor(Math.random() * ALPHABET.length)];
            }

            return genome.join("");
        };

        /**
         * Establish how fit a genome is
         * @param  {String} genome [28 random chars from ALPHABET]
         * @return {Number}        [0-28 number of times genome matches TARGET]
         */
        var getFitness = function(genome) {
            var fitness = 0;

            for (var i = 0; i < TARGET.length; ++i) {
                if (genome[i] === TARGET[i]) {
                    fitness++;
                }
            }
            return fitness;
        };

        /**
         * Generate gene pool by copying genome
         * @param  {String} genome [28 random chars from ALPHABET]
         * @return {Array}        [50 copies of genome]
         */
        var getGenePool = function(genome) {
            var pool = [];

            for (var i = 0; i < 50; ++i) {
                pool[i] = genome;
            }
            return pool;
        };

        /**
         * Find fittest genome in gene pool
         * @param  {Array} pool [50 genomes]
         * @return {String}      [genome with highest fitness]
         */
        var getFittest = function(pool) {
            var fittestLoc = 0;
            var fittest = 0;

            for (var i = 0; i < pool.length; ++i) {
                if (getFitness(pool[i]) > fittest) {
                    fittest = getFitness(pool[i]);
                    fittestLoc = i;
                }
            }
            return pool[fittestLoc];
        };

        /**
         * Randomly mutate a given genome according to MUT_PROB
         * @param  {String} genome [28 random chars from ALPHABET]
         * @return {String}        [genome with 0-28 random mutations]
         */
        var doMutation = function(genome){
            var newGenome = "";

            for (var i = 0; i < genome.length; ++i) {
                if (Math.floor(Math.random() * MUT_PROB) === 1){
                    if (genome[i] != TARGET[i]) {
                        newGenome += ALPHABET[Math.floor(Math.random() * ALPHABET.length)];
                    }
                    else {
                        newGenome += genome[i];
                    }
                }
                else {
                    newGenome += genome[i];
                }
            }
            return newGenome;
        };

        /**
         * Generate successive generations of genomes
         * until first fitness of 28 is found
         * @return {String} [string matching TARGET]
         */
        var evolve = function() {
            var numGens = 0;
            var fittest = generateChild();

            console.log(fittest);

            while (getFitness(fittest) !== 28) {
                numGens ++;
                var pool = cloneFittest(fittest);
                var pool2 = [];
                for (var i = 0; i < pool.length; ++i) {
                    pool2[i] = doMutation(pool[i], true);
                }
                fittest = getFittest(pool2);
                if (numGens % 10 === 0) {
                    console.log(fittest);
                }
            }
            return fittest;
        };