Dive into Genetic Algorithms: A 101

A voyage into the strange world of Genetic Algorithms.

Back in the day, I was a big old AI kind of guy. I was very interested in making computers think and also, evolve.

As a hobby, I used to build robots in my early 20's using PIC microcontrollers (no Arduinos or Teenies back then) and whilst the circuitry was wired together to drive motors and take input from various sensors, the firmware was deliberate designed not to know anything about either of these two set of periopherals. The robots didn't know how to use the motors, what pins they were wired to, what input GPIO it had, nothing. Akin to how babies or most species are born.

Sure, so learning about its environment, was a job for Artificial Neural Nets. However, this was only half the story.

If anyone has ever done any work with devices like PIC Microcontrollers, they'll know it's a painfully slow process. As someone who does a lot with Arduino devices these days too, I can't imagine how I ever got by with PICs. In the end, I had to develop an emulator utility for the robot which ran on my PC, which took the PIC binaries and ran them through the emulator. Not just that, the starting weights of the Neural Nets were also evolved to hit the sweet spot between too much and too little learning. It was one of the most funny experiences of my life watching that thing spin around struggling to hone in on an understanding of how to use it's limbs, but within it were important questions about how machine and indeed, humans learn.

You see, babies are born with particular folds in their brains and other genetic traits. "Successful" genes evolved over millions of years and they enable humans to make a success of itself as a species... certain world leaders aside.The genes provide us with a baseline which our brains then build atop to make us the indvidual humans we are, shaped by the context we're in.

Background

Genetic Algorithms are considered by many a branch of artificial intelligence. Personally, I don't think that's entirely correct, as it's more in the realms of distributed multi-agent systems and the software side of BIMPA. The "intelligence" in such systems is the ability to solve a problem or smartly traverse a search space. A rough comparison is it's like 'wisdom of the crowds' but operating through genetic or memetic transfer of information. These same genetic concepts can also be applied to programming in such a way that programs built from scratch solve problems more effectively than humans have by coding traditional algorithms. As is often the case, the complex behaviour of the population is non-linear even though an individual member's rules of reproduction are inherently simple.

A genetic algorithm, just like monte-carlo approaches, uses multiple agents or samples to determine solutions to the problem you're trying to solve. Each agent is a member of a population and it contains an encoding of the information you wish to find, or use, akin to a genetic sequence in biological systems.

Very often starting with a random sequence and using a process of one or more subsequence cross-overs, a parent swaps substrings in that genetic code with a fit member of its cohort. There is also a probability of a potential mutation of one or more characters of the resulting encoded genetic sequences. It produces children (usually two children per cohort-pair) who share ideally, the best characteristics of each parent, perhaps with a 'genetic mutation' which then goes on to "thrive" in the population, or perhaps dies out over time.

Each time the entire cohort reproduces is a generation. Members of the preceding generation may remain or die out depending on the approach to the problem you're trying to solve.

The introduces a few key problems we need to solve not least, measuring "Fitness". How do you know what the fittest members of thepopulation are?

You have to know two things. Firstly, what or where it is you want to get to. Secondly, where each agent is now. If you don't have either of those two things, you can't measure how fit for purpose a candidate solution is. Any measure of displacement is conducted through a distance metric, measuring how far you are away from the desired outcome.

Walkthrough

I put together some scrap code aftera talk I gave at Manchester BarCamp 2015, to illustrate a really simply genetic algorithm at work. It's a useful introduction to the topic.

What You'll Need?

If you want to roll your own, you'll need JQuery and your favourite editor. I dumped the code in JSBin here.

The scrap of code breeds agents towards an ideal string, in this case provided by a user in the text box labelled "Fitness string:". For this demo, I slowed the evolution down to make it easier to see how it works in a visualisation. you can see it in the rightmost JSBin frame which contains a population of 100 agents, each as a circle in the grid.

Distance Metric

All I've done to demonstrate the distance metric is use what's called the Hamming Distance between the ideal string and the agent string.

The Hamming Distance is simply the number of points in the string where the characters differ. Which in this case, are the number of differnt characters each of the two strings have.

For example the word 'tire' and 'tyre' have a hamming distance of 1, as they differ at character 1 (one has an 'i' the other a 'y').

Similarly, 'stage' and 'staff' have a Hamming Distance of 2. The closer to zero the fitness function result is, the fitter the candidate. Let's have a look at how this is coded:

function fitness(agent) {
  // Get the target string to find
    var target = $("#fitness-name").val().toUpperCase();
    var distance = hammingDistance( agent, target );
    
    return distance;    
}

// ...

function HammingDistance(agent, targetFitness) {
  var distance = 0;
    var target = targetFitness.toUpperCase();
    var upperAgent = targetFitness.toUpperCase();
    
    for( var i = 0; i < agent.generCode.length; i++ ) {
    	distance += upperAgent[i] === target[i]? 0 : 1;
    }
    return distance;
}

Here you can see that an agent's fitness is determined using the Hamming Distance between the ideal (targetFitness) word and the agent's genecode.

Note:

If you are familiar with TDD/BDD, this may seem strangely familiar. The goal is your acceptance test criteria, the initial condition is where the agents start and the actions, how it gets from pre to post-conditions you don't care about Kind of how you'd hope managers/architects leave devs to fill in the gaps.

Breeding

In this code block, all I am doing is taking the top 33% when sorted by fitness and breeding them.There is no reason they can't breed across other parts of the population, but this may take longer to converge on the solution.

 this.Breed = function () {
        // Sort the populous by fitness utility
        me.population.sort(function(agent1, agent2) {
            return  fitness(agent1) - fitness(agent2);
        });

        // Only breed the first half of the list
        for (var j = 0; j < (me.population.length / 3) ; j++) {
            var item = me.population[j];
            var matePosition = Math.round((Math.random() * (me.population.length / 3)));
            var pairedMate = me.population[matePosition];
            item.crossOverWith(pairedMate);
        }
    };

Breeding happens in two steps. The first sorts the population by fitness (in order of increasing distance), the second then breeds them with any other in that space. This then runs into the crossover function, which takes the genecodes of each members, pairs them and mutates them (for illustration, I took out the random occurrence of mutations and maintained the random mutation point). You can see this as part of the Baby() class, which represents each cohort member:

function Baby(name, geneCode) {
    this.geneCode = geneCode;
    this.name = name;

    this.crossOverWith = function(otherParent)
    {
        // Pick a random point in the string
        var endOfString = this.geneCode.length;
        var swapPoint = Math.random() * endOfString;

        // Find same position in other parent
        var myGeneticSubencoding = geneCode.substring(swapPoint, endOfString);
        var myPartnerGeneticSubencoding = otherParent.geneCode.substring(swapPoint, endOfString);

        // Swap the two bits from then on
        this.geneCode = geneCode.substring(0, swapPoint) + myPartnerGeneticSubencoding;
        otherParent.geneCode = geneCode.substring(0, swapPoint) + myGeneticSubencoding;
    };

    this.mutate = function() {
        // This mutates itself. 
        // Pick digit position
        var endOfString = this.geneCode.length;
        var mutatePoint = Math.random() * endOfString;

        // randomise the digit in that position
        this.geneCode[mutatePoint] = Math.random() * 9;
    };
}

Shocking Frankenstein's Monster...

When the button is clicked, the population breeds. I count the number of generations for convenience.

The darker the circle, the shorter the distance from the goal. A fully black circle, (hex rgb = #000000), has found an exact matc whilst lighter circles, are further away from the goal. I circle the winning members in green when they hit it.

Note how the cohort responds to longer strings of characters, how long it takes to get to a solution. Also run exactly the same test twice and see how the different start configurations change the number and placement of generations required to reach the goal as well as where the winning members are. Are there any you've found which don't ever seem to get closer?

Evolutionary Strategies

Crucially, there are many ways (and combinations of such ways) you can employ as an evolution strategy. Indeed, you can even use a genetic algorithm, to evolve another genetic algorithm's evolution strategy! I know, meta!

• Change the distance function/metric
• Number of fit members (I chose 33% but this can vary)
• Increase number of cross-over points
• Increase the number in the cohort
• Apply attrition/mortality rate
• Unconstrain population growth
• Run large populations in parallel
• Randomise whether a mutation occurs or not
  ....

Play around with any or all of these. It would be interesting to see what you come up with. If you have any questions, you know where I am!

Like this? Follow along on twitter @Axelisys or if you don't mind a good rant, you can find me @EtharUK