We use cookies to give you a better experience. Carry on browsing if you're happy with this, or read our cookies policy for more information.

Skip main navigation

Genetic Algorithm (GA)

TBC
14.4
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.
100.3
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.
170.1
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.
246
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.
321.7
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.
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
  • Selection
  • Crossover
  • Mutation
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.
This article is from the free online

Applications of AI Technology

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education