Genetic Algorithm

Genetic Algorithm:

The genetic algorithm developed by Gold Berg was inspired by Darwin's Theory of Evolution. The survival of an organism can be maintained through the process of reproduction, crossover, and mutation. This algorithm is a search heuristic that mimics the process of natural evolution. A solution generated by the genetic algorithm is called chromosome. The collection of chromosomes is referred to as the population.

A chromosome is composed of genes and its value can be either numerical or binary value or character depending upon the nature of the problem. These chromosomes will undergo a process called fitness to measure the suitability of solutions that are generated by the genetic algorithm. Some chromosomes in the population will make through the process called crossover producing new chromosomes which are also known as offspring in which its gene composition is the combination of the parent. In a generation, a few chromosomes will undergo mutation. Chromosomes in the population will be selected for the next generation depending upon the value of fitness. Higher the fitness value higher will be the probability of being selected again in next generation. After several generations, the chromosome value will converge to a certain value which is considered to be the best solution.

Algorithm:

1. Determine the number of chromosomes and generation.
2. Initialize the genes of chromosomes with the random value.
3. Repeat step 4 to 8 until the number of generation is met.
4. Evaluate fitness value of each chromosome by using the objective function.
5. Select the chromosomes.
6. Perform crossover.
7. Perform mutation.
8. Generate new chromosome that is offspring.
9. Display the best chromosome that is the solution of the problem.

Example:

Create population as follows:

chromosome [1] = [a; b; c; d] = [12; 05; 23; 08]

chromosome [2] = [a; b; c; d] = [02; 21; 18; 03]

chromosome [3] = [a; b; c; d] = [10; 04; 13; 14]

chromosome [4] = [a; b; c; d] = [20; 01; 10; 06]

chromosome [5] = [a; b; c; d] = [01; 04; 13; 19]

chromosome [6] = [a; b; c; d] = [20; 05; 17; 01].

Step 1:
a + 2b + 3c + 4d = 30
f(a, b, c, d) = a + 2b + 3c + 4d - 30.

Step 2: Evaluate objective of fⁿ of each chromosome.
f_obj [1] =a + 2b + 3c + 4d - 30
= 12 + 2 * 5 + 3 * 23 + 4 * 8
=93.

f_obj [2] =a + 2b + 3c + 4d - 30
=2 + 2 * 21 + 3 * 18 + 4 * 3 - 30
= 80.

f_obj [3] =a + 2b + 3c + 4d - 30
= 10+ 2 * 4 + 3 * 13 + 4 * 14 - 30
= 83.

f_obj [4] =a + 2b + 3c + 4d - 30
= 20+ 2 * 1 + 3 * 10 + 4 * 6 - 30
= 46.

f_obj [5] =a + 2b + 3c + 4d - 30
= 1 + 2 * 4 + 3 * 13 + 4 * 19 - 30
= 94.

f_obj [4] =a + 2b + 3c + 4d - 30
= 20+ 2 * 5 + 3 * 17 + 4 * 1 - 30
= 55.

Step 3: Calculate the fitness value for each chromosome.

fitness [1] = 1 / (1 + f_obj [1]) = 1 / 94 = 0.0106.

fitness [2] =1 / (1 + f_obj [2]) = 1 / 81 = 0.0123.

fitness [3] =1 / (1 + f_obj [3]) = 1 / 84 = 0.0119.

fitness [4] =1 / (1 + f_obj [4]) = 1 / 47 = 0.0213.

fitness [5] =1 / (1 + f_obj [5]) = 1 / 95 = 0.0105.

fitness [6] =1 / (1 + f_obj [6]) = 1 / 56 = 0.0179.

Total fitness value =0.0106 +0.0123 +0.0119 +0.0213 +0.0105 +0.0179 = 0.0845.

Calculate probability of each chromosome.

p [1] = 0.0106 / 0.0845 = 0.1254, cumulative probability = 0.1254.

p [2] = 0.0123 / 0.0845 = 0.1456, cumulative probability = 2710.

p [3] = 0.0119 / 0.0845 = 0.1408, cumulative probability = 0.4118.

p [4] = 0.0213 / 0.0845 = 0.2521, cumulative probability = 0.6639.

p [5] = 0.0105 / 0.0845 = 0.1243, cumulative probability = 0.7882.

p [6] = 0.0179 / 0.0845 = 0.211, cummulative probability = 1.

Random number between 0 and 1.

R [1] = 0.202.

R [2] = 0.284.

R [3] = 0.099.

R [4] = 0.822.

R [5] = 0.398.

R [6] = 0.502.

For new generation,

chromosome [1] = [a; b; c; d] = [02; 21; 18; 03]

chromosome [2] = [a; b; c; d] = [10; 04; 13; 14]

chromosome [3] = [a; b; c; d] = [12; 05; 23; 08]

chromosome [4] = [a; b; c; d] = [20; 05; 17; 01]

chromosome [5] = [a; b; c; d] = [10; 04; 13; 14]

chromosome [6] = [a; b; c; d] = [20; 01; 10; 06].

Crossover:

chromosome [1] = Ch..... [1] Ch ..... [4].

= [02; 21; 18; 03]

= [20; 05; 17; 01]

∴ chromosome [1] = [02; 05; 17; 03].

chromosome [4] = Ch..... [4] Ch ..... [1].

=[20; 05; 17; 01]

= [02; 21; 18; 03]

= [20; 21; 17; 01].

Mutation:

Total number of mutation = 1 % of total gene

= 0.01 * 24

= 0.24≈ 0.

References:

1. Elaine Rich, Kevin Knight 1991, "Artificial Intelligence".
2. Nilsson, Nils J. Principles of Artificial Intelligence, Narosa Publishing House New Delhi, 1998.
3. Norvig, Peter & Russel, Stuart Artificial Intelligence: A modern Approach, Prentice Hall, NJ, 1995
4. Patterson, Dan W. Introduction to Artificial Intelligence and Expert Systems, Prentice Hall of India Private Limited New Delhi, 1998.