A “Hello World!” to the genetic algorithms

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.

I would like to develop three GA solutions before I dive into parallelization of GAs.

  1. 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).
  2. The second is the modelling of canonical GA. Natural selection based.
  3. The third one is implementing the travelling salesman problem using GA.

Once this is done, I will work on the parallelization of the same using GPGPUs. So, stay tuned!


Modelling a simple genetic algorithm

Modelling the genetic algorithms is pretty straightforward. This would be a pathway for finding solutions to complex search problems.

Let’s try to model a simple genetic algorithm. As mentioned in the previous post, genetic algorithms are based on the process of natural selection.

A canonical GA requires the following components:

  1. A representation of candidate solution
  2. A way of calculating the correctness of a candidate solution, the fitness function.
  3. A mutation function that changes a candidate solution slightly, in an attempt to obtain a better candidate.

To model the process of natural selection, we create the population (a randomly generated one). We calculate the fitness of each individual of the population. We then consistently improve the population’s overall fitness. This helps us to discard misfits and only keep the more fit individuals of the population.

The next most important part is the crossover. Crossover creates new individuals by combining (desirable?) aspects of the individuals selected. This is in the hope that we create more fit offsprings which inherit the best traits of their parents.

Now comes the mutation. We need to consider the anamolies. we’ll add a bit of randomness into our population’s genetics.

We continue the above until we reach the termination condition.