Genetic algorithm is a way to solve optimisation problems by mimicking the process of natural selection. It works by taking a group of possible solutions to a problem, and combining them to grow new, potentially better solutions. This is different from more conventional optimisation methods when the one solution is improved with each iteration without considering other solutions.
In this post, I’d like to explain genetic algorithm using 3 different methods: 1) classical algorithm 2) intiutive using rabbits analogy and 3) indutitive cake analogy
There are many papers and tutorials that explain genetic algorithms and many types of genetic algorithms but essentially it boils down to the following algorithm
I’d like to quote one of my favourite experts in genetic algorithms, Zbygniew Michalewicz, from his classic book 1:
…at any given time there is a population of rabbits. Some of them are faster and smarter than other rabbits. These faster, smarter rabbits are less likely to be eaten by foxes, and therefore more of them survive to do what rabbits do best: make more rabbits. Of course, some of them slower, dumber rabbits will survive just because they are lucky. This surviving population of rabbits starts breeding.
The breeding results in a good mixture of rabbit genetic material: some slow rabbits breed with fast rabbits, some fast with fast, some smart rabbits with dumb rabbits, and so on. And on the top of that, nature throws in a ‘wild hare’ every once in a while by mutating some of the rabbit genetic material. The resulting baby rabbits will (on average) be faster and smarter than these in the original population because more faster, smarter parents survived the foxes. (It is a good thing that the foxes are undergoing similar process – otherwise the rabbits might become too fast and smart for the foxes to catch any of them).
To start, we create a population of solutions, often at random, each represented by a set of genetic “instructions” that determine its properties. Think of each gene as an instruction to bake a cake. If you have random instructions, as in the first population, the cakes won’t taste very good.
Next, we evaluate each solution to see how well it solves the problem - we evaluate fitness function. In the cake analogy, we taste and rate them.
We then select the best solutions and “combine” their genetic instructions to create new, potentially better solutions. This produces a new population of solutions which generally solves the problem better on average. In the cake analogy, we take some cakes that taste better than others and try to combine parts of their recipes.
This process is repeated many times, with each new generation of solutions being evaluated and selected based on their fitness to the problem. Over time, the population evolves to produce better and better solutions (cakes), just like how living organisms evolve over time through natural selection.
Genetic algorithm is used to solve all kinds of problems, from optimizing complex engineering designs to training artificial intelligence algorithms. It’s a powerful tool that allows us to find the best solutions to problems, even when they’re very complex or difficult to solve using other methods.
Genetic algorithms + data structures = evolution programs (3rd, revised and extended ed.). Springer-Verlag New York, Inc., New York, NY, USA, 1996. ↩,
This article reflects my personal views and opinions only, which may be different from the companies and employers that I am associated with.