Introduction to Genetic Algorithms
A simple conceptual introduction to genetic algorithms.
The early pioneers of computer science were as much interested in biology and psychology as in electronics, and they looked to natural systems as guiding metaphors for how to achieve their visions.
Through their efforts, three biology inspired problem solving strategies have emerged. The first has grown into the field of neural networks, the second into machine learning, and the third into what is now called “evolutionary computation,” of which genetic algorithms are the most prominent example.
Genetic algorithms
‘Search algorithms’ are strategies that ‘search’ for solutions to problems. A genetic algorithm is a search algorithm inspired by the mechanics of natural selection and genetics. But before finding the solution, we first need to define what a solution looks like.
Encoding Solutions
Let us understand encoding with a toy problem. Consider a box with 5 switches and a bulb. A particular combination of the switches( toggled ON and OFF) turns the bulb on. Our objective is to find the correct combination of switches that turns the bulb on.
We have now defined the problem, next comes the solution. Well, the solution is some combination of switches. How do we represent a combination of switches? A simple approach would be to represent it as sequence of switch states, say [ ‘OFF’, ‘ON’, ‘OFF’, ‘ON’, ‘OFF’ ] .We can further simplify this into a string of ‘0’s and ‘1’s, where a ‘0’ represents a switch toggled OFF, and a ‘1’ represents a switch toggled ON. For example, the string ‘01011’ means that the second, fourth and fifth switches are ON and the remaining are OFF.
Finding the solution to the box is now a matter finding the right binary string of length 5. This process of ‘encoding the parameter set’ is one of the ways genetic algorithms differ from other search algorithms.
Now that we have defined what a solution looks like, let us proceed to the actual algorithm itself. Genetic algorithms consist of the following steps:
- Reproduction/ selection
- Crossover
- Mutation
Reproduction
We start with a population of random candidate solutions. Being random, these are probably not the correct solutions. Nevertheless, this is our first generation. The process of reproduction involves creating a new population of solutions by selecting members from the existing population. On what basis do we select the members?
Simply put, we require that good solutions are more likely to be selected( and multiple times ), while bad solutions are less likely to be selected. This would mean that with each successive generation, we expect the population to contain more copies of the good solutions while the bad solutions are filtered out.
But how do we know if the solution is good or bad? For this, we define a ‘fitness’ criteria that lets us compare candidate solutions.
Fitness
Going back to the switch box example, lets say that the box fully lights up for the combination ‘10110’. This combination is our target solution. In addition, lets say that the box partially lights up for every combination that comes close to the target solution. In other words, every switch that is correctly toggled will increase the brightness of the bulb.
Following this logic, the bulb will be completely turned off for the combination ‘01001’ ( Every switch is incorrectly toggled ) and close to full brightness for the combination ‘10111’ (all but the last switch is correctly toggled). Thus the brightness of the bulb serves as a fitness criteria for candidate solutions.
To model this bulb and it’s brightness, we can simply replace ‘brightness of the bulb’ with ‘number of switches correctly toggled’, thus obtaining a numerical value for the fitness of each candidate solution.
Now that we have a numerical measure of how ‘fit’ each candidate solution is, we need to create a new population that contains more of the fitter solutions. There are many methods to do this, this article will introduce ‘roulette wheel selection’.
Roulette Wheel Selection
As the name suggests, we put all the candidate solutions from the current population on a roulette wheel with the fitter candidates occupying a larger area. This will ensure that candidates are selected in proportion to their fitness.
Now, we simply spin the wheel multiple times and copy the candidates that win into the next generation. We note that the fitter candidates are likely to be selected multiple times while the less fit candidates may not get selected at all. The next step is crossover.
Crossover
Through selection results in more copies of better solutions, it does not produce new solutions. After all, we cannot simply hope that the initial random population just so happens to contain the best solution! This is where crossover comes in. In this article, we will be focusing on single point crossover.
In single point crossover, all individual strings are grouped into pairs. For a pair of strings, a random number k between 1 and the length of the strings is chosen at random. For the pair of strings, every character(bit) after the kth character is swapped. This is done for all pairs of strings.
Now we have a way to ensure that new solutions can be introduced into the population. The last step is mutation.
Mutation
Mutation involves randomly changing a bit every now and then. In other words, every bit of every string has a small chance of being changed ( a ‘1’ becomes a ‘0’ and a ‘0’ becomes a ‘1’).
Mutation is necessary because sometimes the best solution cannot be formed from existing solutions. For example if all the strings in a population has ‘0’ as the first bit while the best solution requires a ‘1’ as the first bit, then no amount of reproduction and crossover can produce the best solution.
Repeat!
One cycle of selection, crossover and mutation produces a new generation. This cycle is repeated multiple times. How many times? Well, ideally until we find a solution. But in case our algorithm takes too long to find a solution or is unable to find a solution at all, we can set a limit to the number of generations.
Conclusion
With this, you should have a basic understanding of how genetic algorithms work and are ready begin implementation. I have an article scheduled for next week, were we shall implement a genetic algorithm in python to tackle a simple problem. Thank you.
