WEBVTT Kind: captions Language: en 00:00:14.380 --> 00:00:20.180 Hello everybody. Today, I want to introduce Genetic Algorithm (GA) 00:00:20.680 --> 00:00:22.780 and its applications. 00:00:23.260 --> 00:00:27.260 This is the outline of today's course including Background, 00:00:27.940 --> 00:00:31.400 Genetic Algorithm and applications. 00:00:32.020 --> 00:00:36.600 Now I am going to start with the background of Genetic Algorithm. 00:00:37.080 --> 00:00:47.220 Genetic algorithm is an optimization algorithm Inspired by the biological evolution process. 00:00:47.700 --> 00:00:57.940 It use the concepts of "Natural Selection" and "Genetic Inheritance" proposed by Darwin. 00:00:58.920 --> 00:01:06.140 Genetic algorithm is proposed by John Holland in 1975. 00:01:06.740 --> 00:01:10.440 Now I am going to introduce Genetic Algorithm. 00:01:10.860 --> 00:01:20.640 This is the flow chart of genetic algorithm including some basic steps of population initialization, 00:01:21.460 --> 00:01:27.000 fitness calculation, selection, crossover and mutation. 00:01:27.800 --> 00:01:33.100 I will start with population initialization and fitness calculation. 00:01:33.620 --> 00:01:39.380 At first we have to initialize a population of chromosomes. 00:01:40.300 --> 00:01:47.500 A chromosome represent a solution of a problem in terms of bit stream. 00:01:48.480 --> 00:01:55.260 According to the problem, a fitness function should be given for calculating the fitness 00:01:55.640 --> 00:01:57.680 of each chromosome. 00:01:58.580 --> 00:01:59.480 For example, 00:02:00.000 --> 00:02:10.820 we want to find the integer x belonging to 0 to 7 such the function f(x) has the maximum value. 00:02:11.360 --> 00:02:17.320 At first we initialize a population of 4 chromosomes. 00:02:18.180 --> 00:02:24.280 Since we want to find the solution such f(x) has the maximum value, 00:02:24.880 --> 00:02:29.440 we directly use f(x) as the fitness function. 00:02:29.960 --> 00:02:36.780 Then we can calculate the fitness of each chromosome as shown in this table. 00:02:37.300 --> 00:02:39.200 After fitness calculation, 00:02:39.700 --> 00:02:46.780 if the chromosome with the best fitness satisfies the termination condition, 00:02:47.240 --> 00:02:49.380 the algorithm will be stopped. 00:02:50.140 --> 00:02:59.460 In this case the chromosome with the best fitness is returned to be the solution of the optimization problem. 00:03:00.280 --> 00:03:03.400 If the termination condition is not satisfied, 00:03:04.060 --> 00:03:08.680 we have to do selection, crossover and mutation. 00:03:09.600 --> 00:03:17.900 Then we have to do the fitness calculation again until the termination condition is satisfied. 00:03:18.760 --> 00:03:23.000 Now we move to the next step "selection". 00:03:23.580 --> 00:03:29.620 The step selection use the concept of Natural Selection. 00:03:30.520 --> 00:03:37.660 The chromosome with higher fitness has more possibility to be reproduced. 00:03:38.520 --> 00:03:41.800 According to the fitness of each chromosome, 00:03:42.340 --> 00:03:47.640 we can calculate the running totals as shown in this table. 00:03:48.500 --> 00:03:49.000 Then 00:03:49.520 --> 00:03:54.900 generate a random number between 0 to total fitness. 00:03:55.580 --> 00:04:00.300 According to the random number and running totals, 00:04:00.580 --> 00:04:05.680 we can determine which chromosome will be reproduced. 00:04:06.000 --> 00:04:11.980 It is noted that the population should be the same after reproduction. 00:04:12.680 --> 00:04:19.640 In this example, if the generated random number is between 0 to 21, 00:04:19.820 --> 00:04:23.420 then Chromosome 1 will be reproduced. 00:04:24.080 --> 00:04:29.060 If the generated random number is between 21 to 30, 00:04:29.140 --> 00:04:34.320 then Chromosome 2 will be reproduced and so on. 00:04:35.120 --> 00:04:43.120 The selection process simulates a Roulette wheel with slot sizes 00:04:43.920 --> 00:04:48.480 proportion to fitness values as shown in this figure. 00:04:49.080 --> 00:04:56.500 After selection, we move to the next two steps "crossover" and "mutation". 00:04:56.980 --> 00:05:03.060 In the step of crossover, a crossover point is randomly selected. 00:05:03.760 --> 00:05:14.180 Then bits to the right of that point are swapped between the two parent chromosomes as shown here. 00:05:14.260 --> 00:05:21.080 Typically the crossover rate is between 0.8 to 0.95. 00:05:21.720 --> 00:05:31.580 In the step of Mutation, we select one or more random bits and flip them as shown here. 00:05:32.280 --> 00:05:40.860 Typically the Mutation rate is between 0.1 to 0.001. 00:05:41.740 --> 00:05:47.840 Mutation intends to break the chromosome out of local optimum. 00:05:48.620 --> 00:05:52.380 After selection, crossover and mutation, 00:05:52.800 --> 00:06:00.260 we have to do the fitness calculation again until the termination condition is satisfied.