Tuesday 8 September 2015

The cosmic watchmaker and the genetic algorithm

Reading about artificial neural networks has been a life-changer. That led on to the unexpected topic of the genetic algorithm, which is very effective by itself (i.e. without using a neural network) at solving tricky problems.

After working through my first example I was really astonished to find that applying rules like crossover and mutation (mimicking our own reproduction) in a population of initial random data, you arrive at a very fit population (i.e. gets you lots of good answers very close to the best answer) in remarkably few generations.

This is really profound stuff and I'm more excited than I have been since I first came to conventional computing in the mid-80s. If you watch a trace of your data 'evolving', it's perfectly obvious why we reproduce sexually - anything which reproduces this way can become fit for a new environment or solve a problem in remarkably few generations. 

It's also clear that you can produce something very distinct (all depending on your test for fitness) from random data very quickly. Thus the intricate watch found on a beach (as long as it could be the product of rules such as genetic crossover and mutation and meets a need perfectly) isn't so remarkable.

To demonstrate all this, and just a fun exercise in this stuff, is a face (a very special one) evolving from random noise. 

Without going into too much detail (that's all here) this exercise starts with a 'population' of chromosomes made of random numbers, which represent pixels in the images. For each new generation, the rules of crossover and mutation* and a test for fitness are applied. 'Survival of the fittest' isn't a good description of what really goes on in the natural world or in our algorithm here. Instead, individuals are randomly selected for reproduction with a bias towards the fittest.

In the human population, 'fittest' means thriving and feeding yourself until you can reproduce. Here, it means how closely each chromosome looks like the target picture. (Think females choosing males with a highly decorative tail).  (Target picture is shown on the right for reference.)

The infinite monkeys concept isn't helpful here either. Sometimes an answer to a solution can appear out of random data (the bigger the population, the more likely) but this isn't generating random data until the right answer is found, it's starting with random data and applying some rules to work towards and very quickly arrive at the right answer.

For a smoother animation, the picture in this video isn't the best picture from each generation, but an average of all of them. It shows that a whole population becomes very fit in a short time, rather than just a few outstanding individuals getting very fit and then passing on their genes as the terms 'survival of the fittest' or 'natural selection' imply.

* We tend to associate genetic mutation with disease, but it's an important part of this process. 
** My title is a response to the 'cosmic watchmaker' argument. It's a terrible analogie for many reasons, not least of which is that a timepiece is obviously a manufactured tool (like a flint axe) and not a living, reproducing being. But I'm really not interested in the religious argument, only in the uses for these amazing, almost magical techniques.

No comments:

Post a Comment