Genetic Algorithm (GA)

Hello everybody. Today, I want to introduce Genetic Algorithm (GA) and its applications. This is the outline of today’s course including Background, Genetic Algorithm and applications. Now I am going to start with the background of Genetic Algorithm. Genetic algorithm is an optimization algorithm Inspired by the biological evolution process. It use the concepts of “Natural Selection” and “Genetic Inheritance” proposed by Darwin. Genetic algorithm is proposed by John Holland in 1975. Now I am going to introduce Genetic Algorithm. This is the flow chart of genetic algorithm including some basic steps of population initialization, fitness calculation, selection, crossover and mutation. I will start with population initialization and fitness calculation. At first we have to initialize a population of chromosomes.

A chromosome represent a solution of a problem in terms of bit stream. According to the problem, a fitness function should be given for calculating the fitness of each chromosome. For example, we want to find the integer x belonging to 0 to 7 such the function f(x) has the maximum value. At first we initialize a population of 4 chromosomes. Since we want to find the solution such f(x) has the maximum value, we directly use f(x) as the fitness function. Then we can calculate the fitness of each chromosome as shown in this table. After fitness calculation, if the chromosome with the best fitness satisfies the termination condition, the algorithm will be stopped.

In this case the chromosome with the best fitness is returned to be the solution of the optimization problem. If the termination condition is not satisfied, we have to do selection, crossover and mutation. Then we have to do the fitness calculation again until the termination condition is satisfied. Now we move to the next step “selection”. The step selection use the concept of Natural Selection. The chromosome with higher fitness has more possibility to be reproduced. According to the fitness of each chromosome, we can calculate the running totals as shown in this table. Then generate a random number between 0 to total fitness. According to the random number and running totals, we can determine which chromosome will be reproduced.

It is noted that the population should be the same after reproduction. In this example, if the generated random number is between 0 to 21, then Chromosome 1 will be reproduced. If the generated random number is between 21 to 30, then Chromosome 2 will be reproduced and so on. The selection process simulates a Roulette wheel with slot sizes proportion to fitness values as shown in this figure. After selection, we move to the next two steps “crossover” and “mutation”. In the step of crossover, a crossover point is randomly selected. Then bits to the right of that point are swapped between the two parent chromosomes as shown here. Typically the crossover rate is between 0.8 to 0.95.

In the step of Mutation, we select one or more random bits and flip them as shown here. Typically the Mutation rate is between 0.1 to 0.001. Mutation intends to break the chromosome out of local optimum. After selection, crossover and mutation, we have to do the fitness calculation again until the termination condition is satisfied.