Part 2. Genetic Algorithms
Following on from my previous article on Neural Networks this is a short and simple primer on the subject of Genetic Algorithms.
Read Part 1. Neural Networks (although each article can be read independently)
If a creature was to have ten babies, each being very similar to their parent but slightly different, the chances of at least one of those offspring being superior at a particular task would be quite high.
This is one of the general concepts behind genetic algorithms (GAs). However instead of creatures we are discussing algorithms and, of course, the most obvious question is; how can a computer program produce offspring?
If we think about nature; creatures, animals and even humans, we know that everything about us is controlled by our genes. Long sequences of ‘switches’ with each gene controlling a particular aspect of our appearance or behavior.
We also know that computer programs operate based on their set of variables. Let’s consider a computer program that is written to assist engineers in designing bridges. There are many variables to think about during the design process, including the choice of material, its thickness and positioning within a structure etc. but each of these decisions could be constrained to a set a possible values. For example we might limit the computer program to a choice of ten materials, thickness between a range of values etc. thereby reducing the computer program to a set of variables each with a set of potential values. Therefore the variables and the values in our example could be encoded into a data structure that resembles a gene sequence.
Moving forwards, let’s say our engineering computer program actually operates by using this gene sequence of data. When each gene changes the program will operate in a different way and the program will design a different type of bridge.
If we were to clone (or copy) our computer program many times and provide each copy with different gene values we would have many bridge designs.
Now its important to say that many of the bridges may not be a good design, they may be structurally unsound or unsuitable in numerous ways. For this particular problem we must also be able to simulate how the bridges might perform in the real world, with calculations for gravity, wind and earthquakes being likely tests. In the field of genetic algorithms we call this a fitness function.
A fitness function is like a score and it rates how well the algorithm performs in its environment.
So part of the software here (the algorithms) are acting as the creative genius and another part of the software is able to assess and rate their designs within a simulated (but fixed) environment.
We could indeed simply randomize thousands of algorithms by providing random gene sequences but it would still be a very hit-and-miss process so instead we work in generations. We can produce, say, ten genetic algorithms and find the best one (which would probably not be very good, but better than the others). We would then take the gene sequence from that algorithm and mutate that set of genes (again) ten times. This is akin to the algorithm producing ten offspring, each being similar to itself but slightly different, and we would refer to the new set as ‘generation 2’.
In generation 2 we would expect to find some of the GAs to be worse than the parent and some of them to be better. By continually taking the best GAs within each generation and breeding from them we can slowly move towards a solution.
This process simulates a tiny part of evolution and Darwin’s theory of ‘survival of the fittest’.
So far we have covered mutation of genes from a single parent but there are many other aspects to Genetic Algorithms including crossover (the process by which we combine the genes from two or more parents) and selection (the method by which we chose the best GAs from within a population).
The final result of this process is to narrow in on a solution by leveraging the rules of natural selection.
In the field of artificial intelligence, genetic algorithms are just one method that permits creativity to arise from the binary depths of the computer rather than the mind of the programmer.