Genetic AlgorithmsThe Traditional ApproachNature’s Starting PointOptimised Man!Example: Pursuit and EvasionComparisonsMore ComparisonsThe Genetic Algorithm ApproachA “Population”Ranking by Fitness:Mate Selection: Fittest are copied and replaced less-fitMate Selection Roulette: Increasing the likelihood but not guaranteeing the fittest reproductionCrossover: Exchanging information through some part of information (representation)Mutation: Random change of binary digits from 0 to 1 and vice versa (to avoid local minima)Best DesignThe GA CycleSlide 17Genetic ApproachExample: Karl Sim’s creaturesTypical “Chromosome”1Genetic AlgorithmsCS 561, Session 262The Traditional Approach•Ask an expert•Adapt existing designs•Trial and errorCS 561, Session 263Nature’s Starting PointAlison Everitt’s “A User’s Guide to Men”CS 561, Session 264Optimised Man!CS 561, Session 265Example: Pursuit and Evasion•Using NNs and Genetic algorithm•0 learning•200 tries•999 triesCS 561, Session 266Comparisons•Traditional•best guess•may lead to local, not global optimum•Nature•population of guesses•more likely to find a better solutionCS 561, Session 267More Comparisons•Nature•not very efficient•at least a 20 year wait between generations•not all mating combinations possible•Genetic algorithm•efficient and fast•optimization complete in a matter of minutes•mating combinations governed only by “fitness”CS 561, Session 268The Genetic Algorithm Approach•Define limits of variable parameters•Generate a random population of designs•Assess “fitness” of designs•Mate selection•Crossover•Mutation•Reassess fitness of new populationCS 561, Session 269A “Population”CS 561, Session 2610Ranking by Fitness:CS 561, Session 2611Mate Selection: Fittest are copied and replaced less-fitCS 561, Session 2612Mate Selection Roulette:Increasing the likelihood but not guaranteeing the fittest reproduction11%38%7%16%0%3%25%CS 561, Session 2613Crossover:Exchanging information through some part of information (representation)CS 561, Session 2614Mutation: Random change of binary digits from 0 to 1 and vice versa (to avoid local minima)CS 561, Session 2615Best DesignCS 561, Session 2616The GA CycleCS 561, Session 2617Genetic AlgorithmsAdv: •Good to find a region of solution including the optimal solution. But slow in giving the optimal solutionCS 561, Session 2618Genetic Approach•When applied to strings of genes, the approaches are classified as genetic algorithms (GA) •When applied to pieces of executable programs, the approaches are classified as genetic programming (GP) •GP operates at a higher level of abstraction than GACS 561, Session 2619Example: Karl Sim’s creatures•Creatures•Sea Horse•SnakeCS 561, Session 2620Typical
View Full Document
Unlocking...