Genetic Algorithms – Example

To download the program with the genetic algorithm shown in this post, you can download it by clicking HERE.

As we already saw in the post "What Is Evolutionary Computation?", genetic algorithms are a type of evolutionary algorithm used to solve optimization problems. What mainly sets them apart from other types of evolutionary algorithms is how they represent individuals: they use binary strings (binary arrays).

In this post we are going to work through an example of how to find the maximum of the function shown below over the range [0-15] using a genetic algorithm (the argument of the sine is given in radians). In this example, this function will be the "Fitness Function", or quality function, that we will use for this problem, since the 'x' that maximizes this function will be the best solution to the problem.

Before seeing how to solve the problem, the following image shows the graph of this function, so we can check that the maximum of this function over the interval [0-15] is "x=11". That way we will be able to see how "good or bad" genetic algorithms are:

The first "problem" we face is "how to represent the individuals" in this genetic algorithm. In this case it is very simple, and the problem was designed that way on purpose. Since individuals in genetic algorithms are represented with binary strings, it is very intuitive that if we want to find the maximum in the interval [0-15], we represent the individuals as "binary numbers", in this case binary numbers of length 4. With a 4-bit binary number we can represent 16 numbers (2^4=16), so we say that "the individuals will be represented by a chromosome of length 4". Example:

Once we have defined the fitness function and how to represent the individuals, we need to work out how to generate the first generation of individuals, how to pair them up, and how they mutate. To do all this we will generate a set of random numbers to work with, and we will see what they mean shortly. To do so, first of all we need to define how many individuals we want to work with, the chromosome generation probability, the crossover probability and the mutation probability. To see this whole process in detail, following the pseudocode shown in the post "What Is Evolutionary Computation?", we are going to define all these things and walk through the algorithm step by step:

1. 1. Chromosome length: 4
   2. Set of chromosome elements: {0,1}
   3. Number of individuals in the population: 2
   4. For creating the first generation:
      3.1.- Probability of element '0': random num < 0.5
      3.2.- Probability of element '1':  random num >0.5
   5. Crossover probability: 0.7
   6. Mutation probability: 0.3

The set of random numbers we are going to work with is the following:

First, we are going to get the first two individuals that will make up the initial generation. To get the chromosomes of the two individuals we will use the first 8 random numbers (4 per individual). If the random number is less than 0.5 we put the element '0' in the chromosome, and if it is greater than 0.5 we give it the value '1'. Below we show how we generate the individuals:

Once we know the individuals, we apply the fitness function to find out which of the two is better and by how much, so we can later see what crossover probability each one has:

As we can see, both individuals are very similar because they have a similar quality, although individual 2 is a bit better than individual 1, since what we are trying to do is find the maximum of the function. Now we calculate each individual's crossover probability, and we do this with a simple rule of three:

What we want with this is to see which individuals we select for crossover. To do that we take the next two random numbers, and if they fall within the selection ranges, that individual will be eligible for crossover (if crossover happens in that generation). This means that if we draw a random number within the interval [0-0.48), individual 1 will be selected for crossover, and if another random number is in the interval [0.48-1], individual 2 will also be eligible for crossover. Below we see whether or not they are eligible:

With this we see that both individuals are eligible for crossover, but will there be crossover in this generation? To find out, we check whether the next random number falls within the crossover probability, which we defined as 0.7. That means that if the random number is in the range [0-0.7) there will be crossover, and if it is in [0.7-1] there will not. We show this below:

We see that there is crossover in this generation and that both individuals will be paired, so now we need to see how these two individuals are crossed. To do that we have to calculate the "cut point" of the chromosome where the exchange will take place. As shown below, there are 3 cut points in the chromosome where crossover can happen:

This means that we again create selection ranges and pick one of the three cut points for the crossover. We show this cut point selection below:

With everything we have calculated, we can now generate new individuals. Since we selected the third position as the cut point, the first individual will take as the value of the last position of its chromosome the value of the last position of individual 2's chromosome. This means the crossover will produce two new individuals with the chromosome values swapped. We show this exchange below:

Finally, we need to see whether any of the individuals will undergo a mutation. To do that we take one random number per chromosome element (8 random numbers, 4 for each individual) and check whether it falls within the mutation probability. That is, if the random number is within the range [0-0.3), the chromosome element mutates to its complement, and if it is not in that range there is no mutation. Below we see the mutations that occur:

At this point we have created a new generation of individuals, one in which we have an individual (individual 2 with x=1) that is "better" than those of the previous generation, since its value when applying the fitness function is 1.41, as shown below:

We also see that individual 1 is worse than its parents. As you can see, with just a single generation we have not gotten close to the best individual, which would be the one with x=11, so we would need more individuals and many more generations. That is, we would repeat this process 'n' times and take the best individual in generation 'n'.

So that you can "play around" and see how good or bad genetic algorithms are, I have shared a program written in JAVA (a ".jar" that you can download from the link at the beginning of the post) where you can solve this problem using as many individuals and generations as you want, over larger ranges of the function (that is, with individuals represented by more chromosome elements), and changing the crossover and mutation probabilities. You can also see all the details and steps the genetic algorithm takes in each generation. Below is an image of the program after a run:

When you run this program (be patient with long runs, because I did not use threads and it takes a while to give results), you will see that most of the time it does not give the best result, no matter how many generations you use or how much you vary the crossover and mutation probabilities. As mentioned in the post "What Is Evolutionary Computation?", genetic algorithms give "decent" results but (in most cases) do not give the best result to the problem, although the result may or may not be quite good. In this post I have explained step by step how a genetic algorithm works, but WATCH OUT: for the problems you need to solve, consider other options before using a genetic algorithm, because a genetic algorithm is probably not the best option unless you have no idea how to approach the problem.

BIBLIOGRAPHY

This problem was proposed in the “Artificial Intelligence” course taught in the second year of the Computer Engineering degree at the Escuela Universitaria de Informática of the UPM.