A simple example of genetic algorithm

For a better idea of what this section is about, let us have a look at a simple genetic algorithm and use it in an everyday application: searching for a maximum of the function , where x can take values between 0 and 31.

It is clear right away that the solution is the value x = 31, but this problem is simple enough that it shows nicely the genetic algorithm operation basics. General genetic algorithm starts with a randomly chosen population which is made up of binary series. The criterion function helps us determine their quality and based on this information, the number of copies which each individual subject will have at the construction of the next generation is set. Then, the acquired copies cross-over randomly between themselves and a random selection is made of the genetic string (chromosome) length which will cross-over or be switched (See Figure 3.3 below).

Figure 3.3: Genetic code of the parents and the offspring before and after the cross-over

It can easily be seen that a good subject, which has many copies, has an advantage in comparison with the weak one, because his genetic material can cross-over with more subjects than the genetic material of the weak ones. What follows is also the mutation for which we set the probability of 0.001 in this experiment. This means that there is a possibility of one in a thousand for each bit in the series to change from 0 to 1, or reverse. In our experiment (Figures 3.1 and 3.2), not even one bit mutated in the first generation. That is fine. If we take a look at the generation quality value, we can see that it has increased in the first generation already. We could continue with the process until we reached a subject with the quality 31² = 961, which would meet our criterion to stop searching for a maximum, or until the number of iterations would reach the value, prescribed in advance. That would mean that the algorithm did not find the solution; at least not a solution that would be as good as we determined it to be in our criterion in the beginning.

This execution of the genetic algorithm was simple, but it still shows the essential element of its operation, which is that the result of the optimisation is improving from generation to generation.

Table 3.1: The computation of a starting randomly chosen population characteristics

Table 3.2: The presentation of the cross-over and the first generation offspring characteristics computation

Table 3.1 shows an example of the characteristics (quality) computation of a randomly chosen starting population (first generation or the starting parents). On the basis of the computed characteristics of the individual subjects, a selection is made and only the best subjects are allowed to continue with the cross-over (multiplication). Table 3.2 shows the cross-over of this first generation and the "birth" of the offspring and their characteristics (quality) computation with the criterion function . When we cross-over the parents (first column in Table 3.2), we get a new population with better characteristics (See Table 3.2 - columns 4-6). We assumed the value 0.001 for the mutation. Since there are four subjects in each generation, each of the subjects being five bits (binary places) long, the probability that one of them would mutate is 4*5*0.001=0.02. In the first step, none of the bits has mutated. We can keep computing in the same way until we reach the value x = 31 in just a few iterations.

It takes many more modifications and improvements for successful operation at solving a very complex problem, however, they are beyond this section.

A Genetic Algorithm Example

As a simple example, imagine a population of four strings, each with five bits. Also imagine an objective function f(x)=2x. The goal is to optimize (in this case maximize) the objective function over the domain  . Now imagine a population of the four strings in Table , generated at random before GA execution. The corresponding fitness values and percentages come from the objective function f(x).

Table 1:   Four strings and their fitness values.
   

The values in the ``  '' column provide the probability of each string's selection. So initially 11000 has a 38.1% chance of selection, 00101 has an 7.9% chance, and so on. The results of the selections are given in the ``Actual Count'' column of Table 1. As expected, these values are similar to those in the ``Expected Count'' column.
After selecting the strings, the GA randomly pairs the newly selected members and looks at each pair individually. For each pair (e.g. A = 11000 and B = 10110), the GA decides whether or not to perform crossover. If it does not, then both strings in the pair are placed into the population with possible mutations (described below). If it does, then a random crossover point is selected and crossover proceeds as follows: A = 1 1 | 0 0 0 B = 1 0 | 1 1 0 
are crossed and become A' = 1 1 1 1 0 B' = 1 0 0 0 0. 
Then the children A' and B' are placed in the population with possible mutations. The GA invokes the mutation operator on the new bit strings very rarely (usually on the order of  probability), generating a random number for each bit and flipping that particular bit only if the random number is less than or equal to the mutation probability.
After the current generation's selections, crossovers, and mutations are complete, the new strings are placed in a new population representing the next generation, as shown in Table . In this example generation, average fitness increased by approximately 30% and maximum fitness increased by 25%. This simple process would continue for several generations until a stopping criterion is met.

Table 2:   The population after selection and crossover.
  ca