Skip to 0 minutes and 14 seconds 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.
Skip to 1 minute and 40 seconds 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.
Skip to 2 minutes and 50 seconds 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.
Skip to 4 minutes and 6 seconds 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.
Skip to 5 minutes and 22 seconds 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.
Genetic Algorithm (GA)
In this video, Prof. Cheng will introduce the Genetic Algorithm(GA). He will introduce the background, Genetic Algorithm, and its applications.
The genetic algorithm is an optimization algorithm inspired by the biological evolution process. You can see from the diagram of the basic step of the genetic algorithm. Prof. Cheng will introduce the whole process of the genetic algorithm.
Five phases are considered in a genetic algorithm:
- Initial population
- Fitness function
Learning genetic algorithms is not enough unless we use the algorithm in real calculation and its application. Robotics is a common field that uses genetic algorithm. Let’s see next step, Prof. Cheng will talk about its application.