Genetic Algorithm tutorial

Possibly one of the simplest tutorials on genetic algorithms

Problem formulation

Let's consider the simple problem of maximising the sum of a bit array:

\(\max \qquad f=\sum_{i=1}^{N} x_{i} \)

\( \qquad \qquad x_i \in \{0,1\} \)

The solution is obviously \( \mathbf{x}=[1, 1, 1, 1, ...] \).
Let's see how to use genetic algorithms to find this solution.

Initiate population

First, let's generate a set of random bit arrays as our initial solutions. We will call these individual candidate solutions as the population. Click on Initiate to do this.




Selection

In this step, we will pick two parent individuals from the initial population randomly. We will apply selection pressure by picking the better of two. This is analogous to "survival of the fittest" in Darwinian evolution. There are other ways to apply selection pressure, but picking the best of two is called "tournament selection" since it mimics a typical knockout tournament. Click all the Pick randomly buttons and then click "select" to see who wins this tournament.
Parent 1
Parent 2



Crossover or Recombination

The selected individuals in the previous step are allowed to crossover or reproduce. There are various ways one can perform the crossover and these ways are called crossover operators. In this demonstration, we illustrate three methods, namely uniform, single-point and two-point crossover. Pick one and click crossover. You may click crossover as many times as you want. Each time a new pair of children will be generated.
Parent 1
Parent 2
Child 1
Child 2




Mutation

In this step, the recombined solutions of the crossover operation are mutated. In this implementation, each bit is flipped (0 made 1 and 1 made 0) with a probability of 1/(array length). This is achieved using a random number generator. For each bit, generate a random number uniformly between 0 and 1. Flip the bit if the random number is less than the mutation rate. Click mutate as many times as you want.
Child 1
Mutant 1
Child 2
Mutant 2


Replacement

In this step, a decision will be made as to whether the mutated offspring will replace the parents. Again there are several ways to perform this. In this implementation, a greedy acceptance is used i.e., only if the offspring is strictly better (has more ones) it replaces the parent. Once you click replace button, the population will be updated.
Mutant 1
Parent 1
Mutant 2
Parent 2

Best found solution

After completing each generation, you can check the best solution obtained so far. The update best solution button may be clicked anytime during the algorithmic process.






Repeat

That must have been a lot of clicks, wasn't it? Now you may conveniently repeat all these steps with a single click on the following button. You may even refresh the page, scroll down and start clicking repeat right away. Pressing the button will check if the solutions are initiated and if not done, does it automatically for you.


Generation: 1


Now if you repeatedly click the repeat button, eventually the best solution will be all ones.
Hope you understood how genetic algorithms work from this simple example. Cheers for trying out this tutorial!



Advanced Tip

You can play with this program using the console. For example, to update the population size or solution length update the variables npop and genomelength respectively.

npop = 12
genomelength=6

Then click Repeat. You should see that the initial population has 12 individuals and each have 6 bits. To open console Chrome, rightclick and click inspect.

Feel free to explore!