Downloaded 121 times
![Outline of the Basic Genetic Algorithm 1. [Start] Generate random population of n chromosomes (suitable solutions for the problem) 2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population 3. [New population] Create a new population by repeating following steps until the new population is complete 1. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected) 2. [Crossover] With a crossover probability crossover the parents to form a new children. If no crossover was performed, children is an exact copy of parents. 3. [Mutation] With a mutation probability mutate new children at each position in chromosomeNext Page To Continue……](https://image.slidesharecdn.com/geneticalgorithmartificialintelligencepresentation-160406044728/75/Genetic-algorithm-artificial-intelligence-presentation-6-2048.jpg)
![Outline of the Basic Genetic Algorithm 4. [Replace] Use new generated population for a further run of algorithm 5. [Test] If the end condition is satisfied, stop, and return the best solution in current population 6. [Loop] Go to step 2](https://image.slidesharecdn.com/geneticalgorithmartificialintelligencepresentation-160406044728/75/Genetic-algorithm-artificial-intelligence-presentation-7-2048.jpg)
Genetic algorithm artificial intelligence presentation
- 1. Genetic Algorithm In thefield of artificial intelligence...
- 2. Presenters’ Tauhidul Khandaker ID :011 111 010 Abu Sayed ID : 011 111 009
- 3.
- 4. Why Genetic Algorithm? Widely-usedin business, science and engineering Optimization and Search Problems Scheduling and Timetabling
- 5. Basic Algorithm ofGenetic Algorithm randomly initialize population(t) determine fitness of population(t) repeat select parents from population(t) perform crossover on parents creating population(t+1) perform mutation of population(t+1) determine fitness of population(t+1) until best individual is good enough
- 6. Outline of theBasic Genetic Algorithm 1. [Start] Generate random population of n chromosomes (suitable solutions for the problem) 2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population 3. [New population] Create a new population by repeating following steps until the new population is complete 1. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected) 2. [Crossover] With a crossover probability crossover the parents to form a new children. If no crossover was performed, children is an exact copy of parents. 3. [Mutation] With a mutation probability mutate new children at each position in chromosomeNext Page To Continue……
- 7. Outline of theBasic Genetic Algorithm 4. [Replace] Use new generated population for a further run of algorithm 5. [Test] If the end condition is satisfied, stop, and return the best solution in current population 6. [Loop] Go to step 2
- 8. List of GeneticAlgorithm applications 1. Airlines Revenue Management. 2. Wireless sensor/ad-hoc networks. 3. Audio watermark insertion/detection. 4. Protein folding and protein/ligand docking. 5. Pop music record producer. 6. Financial Mathematics. 7. Finding hardware bugs. 8. Game theory equilibrium resolution.
- 9. Initial Population We startwith a population of n random strings. Suppose that length is = 10 and total n = 6 s1 = 1111010101 s2 = 0111000101 s3 = 1110110101 s4 = 0100010011 s5 = 1110111101 s6 = 0100110000
- 10. Fitness Function: f() s1= 1111010101 f (s1) = 7 s2 = 0111000101 f (s2) = 5 s3 = 1110110101 f (s3) = 7 s4 = 0100010011 f (s4) = 4 s5 = 1110111101 f (s5) = 8 s6 = 0100110000 f (s6) = 3 Total = 34
- 11. Selection (1) Next weapply fitness proportionate selection with the roulette wheel method: We repeat the extraction as many times as the number of individuals we need to have the same parent population size (6 in our case)
- 12. Selection (2) Suppose that,after performing selection, we get the following population: s1’ = 1111010101 (s1) s2’ = 1110110101 (s3) s3’ = 1110111101 (s5) s4’ = 0111000101 (s2) s5’ = 0100010011 (s4)
- 13. Basic Algorithm ofGenetic Algorithm randomly initialize population(t) determine fitness of population(t) repeat select parents from population(t) perform crossover on parents creating population(t+1) perform mutation of population(t+1) determine fitness of population(t+1) until best individual is good enough
- 14. Perform Crossover Before Crossover S1’= 1111010101 S2’ = 1110110101 S5’ = 0100010011 S6’ = 1110111101 After Crossover S1’ = 1110110101 S2’ = 1111010101 S5” = 0100011101 S6” = 1110110011
- 15. Basic Algorithm ofGenetic Algorithm randomly initialize population(t) determine fitness of population(t) repeat select parents from population(t) perform crossover on parents creating population(t+1) perform mutation of population(t+1) determine fitness of population(t+1) until best individual is good enough
- 16. Mutation Before applying mutation:After applying mutation: s1” = 1110110101 s2” = 1111010101 s3” = 1110111101 s4” = 0111000101 s5” = 0100011101 s6” = 1110110011 s1”’ = 1110100101 s2”’ = 1111110100 s3”’ = 1110101111 s4”’ = 0111000101 s5”’ = 0100011101 s6”’ = 1110110001
- 17. Basic Algorithm ofGenetic Algorithm randomly initialize population(t) determine fitness of population(t) repeat select parents from population(t) perform crossover on parents creating population(t+1) perform mutation of population(t+1) determine fitness of population(t+1) until best individual is good enough
- 18. Fitness of NewPopulation After Applying Mutation s1”’ = 1110100101 s2”’ = 1111110100 s3”’ = 1110101111 s4”’ = 0111000101 s5”’ = 0100011101 s6”’ = 1110110001 f(s1”’) = 6 f(s2”’) = 7 f(s3”’) = 8 f(s4”’) = 5 f(s5”’) = 5 f(s6”’) = 6 Total = 37
- 19. Example (End) ➔ Inone generation, the total population fitness changed from 34 to 37, thus improved by ~9%. ➔ At this point, we go through the same process all over again, until a stopping criteria is met.
- 20. Issues Choosing basic implementationissues: representation population size, mutation rate, ... selection, deletion policies crossover, mutation operators Termination Criteria Performance, scalability Solution is only as good as the evaluation function
- 21. When to Usea GA Alternate solutions are too slow or overly complicated Need an exploratory tool to examine new approaches Problem is similar to one that has already been successfully solved by using a GA Want to hybridize with an existing solution
- 22. Conclusion Inspired from Nature Hasmany areas of Applications GA is powerful
- 23.