Genetic Algorithms: An Illustrative Example
Let us understand genetic algorithms better through an example.
We will be solving a simple optimization problem step by step to understand the concept of the algorithm.
Let us assume the expression mentioned below is satisfied for the optimal values of a and b using a genetic algorithm.
The expression is:
2a^2 + b= 57.
We will be comparing it with an objective function, therefore the expression can be written as:
f(a,b) = 2a^2 + b- 57.
From our prior knowledge, we know that the value of the function is assumed to be zero. This function is called the objective function and is used to estimate the values of a and b so that the value itself decreases to zero.
So to begin with, we start by guessing the initial sets of values for a and b. It may or may not include the optimal values. We refer to these values as chromosomes, and this process is called “population initialization”. The set of a and b, [a,b] is referred to as the population. As we are taking the example of the optimization problem, we take six sets of a and b values generated between 1 and 10.
The next step, step 2, is to compute the value of the objective function for each chromosome, this method is known as “selection”. We call it selection as we select the fittest chromosomes from the population of subsequent operations.
The fitness values are used to discard the chromosomes that have low fitness values. It is done so to allow the succeeding generations to survive.
The following selection method is widely used:
Roulette wheel method
Roulette wheel refers to a pie plot. In this, the value of each pie is expressed in terms of fitness probability. Chromosomes that produce low fitness value have a high fitness probability, implying these two are very different factors and are inversely related.
The chromosomes that have a higher fitness probability will have a greater chance of being selected.
It is to be noted that the sum of all fitness probabilities always equals one.
Let us assume a scenario where we choose six random probabilities to generate six values between 0 and 1, let us say the six probabilities are as follows:
For chromosome 1, Probability1 = 0.02.
For chromosome 2, Probability2 = 0.13.
For chromosome 3, Probability3 = 0.40.
For chromosome 4, Probability4 = 0.60.
For chromosome 5, Probability5 = 0.85.
For chromosome 6, Probability6 = 0.96.
So based on the position of the above probability values on the roulette wheel are expressed. It is expressed as a cumulative fitness probability. Each segment in this represents the corresponding chromosome.
The third step is known as crossover. In this step, the chromosomes are expressed in terms of genes. We convert the values of a and b into bit strings.
The one parameter we need to keep in mind is the crossover parameter, it decides which out of the six chromosomes, will be able to produce offspring.
Reference