Genetic Algorithms tutorial

Possibly one of the simplest tutorials on GA

Problem formulation

Let us 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 us 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 the population. Click on Initiate to do this.

Selection

In this step, we will randomly pick two parent individuals from the initial population. We will apply selection pressure by picking the better of the 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 win this tournament.

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. 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 becomes 1 and 1 becomes 0) with a probability (mutationrate) of 1/(array length). This is achieved using a random number generator. For each bit, a random number is generated uniformly between 0 and 1. The bit is flipped if the random number is less than the mutationrate. 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 also refresh the page, scroll down and start clicking repeat immediately. 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!



Bonus tip

You can play with this program using the console. For example, to update the population size or bit length, update the variables npop or genomelength. To do this, open console by right-click > inspect, click on Console, and then enter the following: 

                npop = 12 
                genomelength = 6


Then click on Initiate. You should see that the initial population has 12 individuals, each with 6 bits.

Feel free to explore!