Introduction To Genetic Algorithms - IIT Guwahati

1 1 Bhattacharjya/CE/IITG. Introduction To Genetic Algorithms Dr. Rajib Kumar Bhattacharjya Department of Civil Engineering IIT Guwahati Email: 7 November 2013. References 2 Bhattacharjya/CE/IITG. D. E. Goldberg, Genetic Algorithm In Search, Optimization And Machine Learning', New York: Addison Wesley (1989). John H. Holland Genetic Algorithms ', Scientific American Journal, July 1992. Kalyanmoy Deb, An Introduction To Genetic Algorithms ', Sadhana, Vol. 24 Parts 4 And 5. 7 November 2013. Introduction to optimization 3 Bhattacharjya/CE/IITG.

2 Global optima Local optima Local optima Local optima Local optima f X 7 November 2013. Introduction to optimization 4 Bhattacharjya/CE/IITG. Multiple optimal solutions 7 November 2013. Genetic Algorithms 5 Bhattacharjya/CE/IITG. Genetic Algorithms are the heuristic search and optimization techniques that mimic the process of natural evolution. 7 November 2013. Principle Of Natural Selection 6 Bhattacharjya/CE/IITG. Select The Best, Discard The Rest . 7 November 2013. An Example . 7 Bhattacharjya/CE/IITG. Giraffes have long necks Giraffes with slightly longer necks could feed on leaves of higher branches when all lower ones had been eaten off.

3 They had a better chance of survival. Favorable characteristic propagated through generations of giraffes. Now, evolved species has long necks. 7 November 2013. An Example . 8 Bhattacharjya/CE/IITG. This longer necks may have due to the effect of mutation initially. However as it was favorable, this was propagated over the generations. 7 November 2013. Evolution of species 9 Bhattacharjya/CE/IITG. Initial Population of animals Struggle For Existence Years Millions Of Survival Of the Fittest Surviving Individuals Reproduce, Propagate Favorable Characteristics Evolved Species 7 November 2013.

4 10 Bhattacharjya/CE/IITG. Thus Genetic Algorithms implement the optimization strategies by simulating evolution of species through natural selection 7 November 2013. Simple Genetic Algorithms 11 Bhattacharjya/CE/IITG. Start Initialize population Evaluate Solutions T=0 NO. Optimum Solution? Selection YES. T=T+1 Stop Crossover Mutation 7 November 2013. Simple Genetic Algorithm 12 Bhattacharjya/CE/IITG. function sga (). {. Initialize population;. Calculate fitness function;. While(fitness value != termination criteria). {. Selection.}}

5 Crossover;. Mutation;. Calculate fitness function;. }. }. 7 November 2013. GA Operators and Parameters 13 Bhattacharjya/CE/IITG. Selection Crossover Mutation Now we will discuss about Genetic operators 7 November 2013. Selection 14 Bhattacharjya/CE/IITG. The process that determines which solutions are to be preserved and allowed to reproduce and which ones deserve to die out. The primary objective of the selection operator is to emphasize the good solutions and eliminate the bad solutions in a population while keeping the population size constant.

6 Selects the best, discards the rest . 7 November 2013. Functions of Selection operator 15 Bhattacharjya/CE/IITG. Identify the good solutions in a population Make multiple copies of the good solutions Eliminate bad solutions from the population so that multiple copies of good solutions can be placed in the population Now how to identify the good solutions? 7 November 2013. Fitness function 16 Bhattacharjya/CE/IITG. A fitness value can be assigned to evaluate the solutions A fitness function value quantifies the optimality of a solution.

7 The value is used to rank a particular solution against all the other solutions A fitness value is assigned to each solution depending on how close it is actually to the optimal solution of the problem 7 November 2013. Assigning a fitness value 17 Bhattacharjya/CE/IITG. Considering c = 23 h d 7 November 2013. Selection operator 18 Bhattacharjya/CE/IITG. There are different techniques to implement selection in Genetic Algorithms . They are: Tournament selection Roulette wheel selection Proportionate selection Rank selection Steady state selection, etc 7 November 2013.

8 Tournament selection 19 Bhattacharjya/CE/IITG. In tournament selection several tournaments are played among a few individuals. The individuals are chosen at random from the population. The winner of each tournament is selected for next generation. Selection pressure can be adjusted by changing the tournament size. Weak individuals have a smaller chance to be selected if tournament size is large. 7 November 2013. Tournament selection 20 Bhattacharjya/CE/IITG. 22 32 Selected 22 25. 22 25. 13 +30 25. 32 22. 32 40. 32 22. 25 13 +30.

9 40 22. Best solution will have two copies 7 +45 Worse solution will have no copies 7 +45. Other solutions will have two, one 25 13 +30 or zero copies 25 13 +30 7 November 2013. Roulette wheel and proportionate 21. selection Bhattacharjya/CE/IITG. Chrom # Fitness % of RW EC AC. Parents are selected 1 50 2. 2 6 0. according to their 3 36 1. fitness values 4 30 1. 5 36 1. The better 6 28 1. chromosomes have 186 6 6. more chances to be 6 Roulet wheel 16% 1. 21%. selected 2. 3%. 5. 21%. 3. 21%. 4. 7 November 2013. 18%. Rank selection 22 Bhattacharjya/CE/IITG.

10 Chrom # Fitness Sort Chrom # Fitness Chrom # Rank 1 37 according 1 37 Assign 1 6. 2 6 to fitness 3 36 raking 3 5. 3 36 5 36 5 4. 4 30 4 30 4 3. 5 36 6 28 6 2. 6 28 2 6 2 1. Chrom # % of RW Roulette wheel Chrom # EC AC. 1 29 1 2. 3 24 3 1. 5 19 5 1. 4 14 4 1. 6 10 6 1. 2 5 6 5 4 3 2 1 2013 0. Steady state selection 23 Bhattacharjya/CE/IITG. In this method, a Then some bad The rest of few good chromosomes are population migrates chromosomes are removed and the to the next used for creating new offspring is generation without new offspring in placed in their going through the every iteration.