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 ApproachTypical “Chromosome”1Genetic AlgorithmsCS 5612The Traditional Approach•Ask an expert•Adapt existing designs•Trial and errorCS 5613Nature’s Starting PointAlison Everitt’s “A User’s Guide to Men”CS 5614Optimised Man!CS 5615Example: Pursuit and Evasion•Using NNs and Genetic algorithm•0 learning•200 tries•999 triesCS 5616Comparisons•Traditional•best guess•may lead to local, not global optimum•Nature•population of guesses•more likely to find a better solutionCS 5617More 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 5618The 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 5619A “Population”CS 56110Ranking by Fitness:CS 56111Mate Selection: Fittest are copied and replaced less-fitCS 56112Mate Selection Roulette:Increasing the likelihood but not guaranteeing the fittest reproduction11%38%7%16%0%3%25%CS 56113Crossover:Exchanging information through some part of information (representation)CS 56114Mutation: Random change of binary digits from 0 to 1 and vice versa (to avoid local minima)CS 56115Best DesignCS 56116The GA CycleCS 56117Genetic AlgorithmsAdv: •Good to find a region of solution including the optimal solution. But slow in giving the optimal solutionCS 56118Genetic 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 56119Typical
View Full Document
Unlocking...