Genetic Algorithms illustrative examples

Illustrative Examples

Maximizing a Function

Consider the problem of maximizing the function, f (x) = x2, 0<x<31

Step 1: one must first code the decision variable ‘x’ into a finite length string. Using a five bit unsigned binary integer, numbers between 0(00000) and 31(11111) can be obtained.

•To start with, select initial population at random. Here initial population of size 4 is chosen.

Table.1 shows an initial population randomly selected

Step 2: Obtain the decoded x values for the initial population generated. Consider string 1,

Step 3: Calculate the fitness or objective function. This is obtained by simply squaring the ‘x’ value, since the given function is f(x) = x2.

When, x = 12, the fitness value is, f(x) = x2 = (12)2 = 144

for x = 25, f(x) = x2 = (25)2 = 625 and so on, until the entire population is computed

Step 4: Compute the probability of selection,

where

n- no of populations

f(x)- fitness value corresponding to a particular individual in the population

Σf(x)- Summation of all the fitness value of the entire population.

Considering string 1, Fitness f(x) = 144, Σf(x) = 1155

The probability that string 1 occurs is given by, P1 = 144/1155=0.1247

The percentage probability is obtained as  0.1247∗100 = 12.47%. It should be noted that, summation of probability select is 1.

Step 5: The next step is to calculate the expected count, which is calculated as,

where

For string 1,

Expected count = Fitness/Average = 144/288.75 = 0.4987

Computing the expected count for the entire population. The expected count gives an idea of which population can be selected for further processing in the mating pool.

Step 6: Now the actual count is to be obtained to select the individuals, which would participate in the crossover cycle using Roulette wheel selection. The Roulette wheel is formed as shown in Fig.11

Now the wheel may be spun and the no of occurrences of population is noted to get actual count.

•String 1 occupies 12.47%, so there is a chance for it to occur at least once. Hence

its actual count may be 1.

•With string 2 occupying 54.11% of the Roulette wheel, it has a fair chance of being selected twice. Thus its actual count can be considered as 2.

•On the other hand, string 3 has the least probability percentage of 2.16%, so their occurrence for next cycle is very poor. As a result, it actual count is 0.

•String 4 with 31.26% has at least one chance for occurring while Roulette wheel is spun, thus its actual count is 1.

•The above values of actual count are tabulated as shown is Table .1

Step 7: Now, writing the mating pool based upon the actual count as shown in Table .2

The actual count of string no 1 is 1, hence it occurs once in the mating pool. The actual count of string no 2 is 2, hence it occurs twice in the mating pool. Since the actual count of string no 3 is 0, it does not occur in the mating pool. Similarly, the actual count of string no 4 being 1, it occurs once in the mating pool. Based on this,

the mating pool is formed.

Table 2: Cross over

Step 8: Crossover operation is performed to produce new offspring (children).

The crossover point is specified and based on the crossover point, single point crossover is performed and new offspring is produced. 

                               The parents are

                      The offspring is produced as

Step 9: After crossover operations, new off springs are produced and ‘x’ values are decodes and fitness is calculated.

Step 10: In this step, mutation operation is performed to produce new off springs after crossover operation. Table 3. shows the new offspring after mutation.

•Once the off springs are obtained after mutation, they are decoded to x value and find fitness values are computed.

•This completes one generation.

•The crossover probability and mutation probability was assumed to 1.0 and 0.001 respectively. Once selection, crossover and mutation are performed, the new population is now ready to be tested.

•This is performed by decoding the new strings created by the simple genetic algorithm after mutation and calculates the fitness function values.

                                 

                                Table 3: Mutation

•From the tables, it is noted that maximal and average performance has improved in the new population.

•The population average fitness has improved from 288.75 to 636.5 and maximum fitness has increased from 625 to 841 in one generation.

•This example has shown one generation of a basic genetic algorithm.

Example-2

Maximize     Sin(x)

Subject to   0 ≤  x  ≤ П

•We use 5bit strings to represent the variable x in the range (0, П)

•String (00000) represents the x=0 solution and the string (11111)

represents  X=П solution

•The other 30 strings are mapped in the range (0, П) uniformly

•Assume      

            Population size=4

            Proportionate selection

            Single point crossover with Pc=1

            No Mutation or Pm=0

Linear Mapping Rule

Advantages of linear mapping rule

• Variable bounds are taken care of by the mapping function given in equation

• Decision variables are allowed to take positive and negative values

• Different  decision variables  can have different precisions by simply using different  substring lengths

• Any arbitrary precision can be achieved in the decision variables by using long enough string