Genetic Algorithms for a novice
Genetic Algorithms(GA) is a method of breeding computer programs and solutions to optimization or search problems by means of simulated evolution. They are often used in fields such as engineering to create incredibly high quality products; utilizing their ability to search through a huge combination of parameters to find the (nearly) best match.
They are based on the concept of evolution by natural selection observed in nature. Surprisingly, GA essentially replicate the way in which life uses evolution to find solutions to real world problems. This can be used to find solutions to incredibly complicated (complicated to compute) problems and solve other optimization solutions. GA can also be used to create sandboxes to study evolution and cognitive science.
Understanding the game of chance
Let’s programmatically try to simulate the process of evolution that happens on earth. God creates a bunch of organisms. Each of them have a unique set of genes (of course, they’re randomly chosen). Let’s name them as the first generation. Each of the organisms have a unique trait that determines their survival, (we’ll call it fitness). Now, say that organisms that are more fit tend to get together and reproduce and produce a second generation of offsprings. Also assume that the first generation die after reproduction (i.e. they no longer exist in the population). The second generation now reproduces and the cycle repeats.
The GA keeps producing new generations until a perfect organism is evolved or a certain threshold (say 10000th generation of offsprings) is achieved.
Approaching the perfect solution
A canonical GA requires the following components:
- A representation of candidate solution
- A way of calculating the correctness of a candidate solution, the fitness function.
- A mutation function that changes a candidate solution slightly, in an attempt to obtain a better candidate.
To understand the concepts better, try developing these three GA solutions before you dive into parallelization of GAs.
- The first one would be a simple GA to arrive at an expression of additions/ subtractions for a given number. (e.g. Input = 27, Output = 2 + 24 - 5 + 6).
- The second is the modelling of canonical GA. Natural selection based.
- The third one is implementing the travelling salesman problem using GA.
Once this is done, you can work on the parallelization of the same using GPGPUs.