11Evolutionary SearchBurr H. SettlesCS-540, UW-Madisonwww.cs.wisc.edu/~cs540-1Summer 20032AnnouncementsThis week’s mailing list topic: think of a real-world problem where we could apply an optimization search– You may not repeat someone else’s answer!– What are the states?– What are the actions?– What is the objective function? Read Chapter 6 in AI: A Modern Approach for next time3AnnouncementsIf you choose to do a paper instead of a programming project, 6 pages is a minimum… you may write more if you feel that there is too much material (but please no more than 10)– Keep in mind each group will only have 15 minutes to present on the last week– The presentations don’t have to go into as much detail as the paper, though4Homework #1 ClarificationsFor problem 1, part b, your heuristics are for the 2-letter change problem, and don’t have to be admissible– But do think about if they are or aren’t, and explainEven though “hill-climbing” and “beam” searches are local strategies (and often used for complete searching), you can still use them to solve partial search problems like the graph in problem 25Homework #1 ClarificationsFor problem 3, let’s say you have the initial state ABC, and are doing standard HC… what are the neighbors you need to consider?BC, AC, AB, ABCD, ABCE, ABCFSo to do hill-climbing, you will generate all these states, score them all, and choose the best one (since we are maximizing the objective function)6Genetic AlgorithmsSo far the optimization strategies we’ve discussed search for a single solution, one state at a time within a neighborhoodGenetic algorithms (GAs) are a unique search approach that maintains a populationof states, or individuals, which evolves– Also called evolutionary search27Evolutionary AnalogyConsider a population of rabbits: some individuals are faster and smarter than othersSlower, dumber rabbits are likely to be caught and eaten by foxesFast, smart rabbits survive to do what rabbits to best: make more rabbits!!8Evolutionary AnalogyThe rabbits that survive breed with each other to generate offspring, which starts to mix up their genetic material– Fast rabbits might breed with fast rabbits– Fast rabbits with slow rabbits– Smart with not-so-smart, etc…Furthermore, nature occasionally throwsin a “wild hare” because genes canmutate9Evolutionary AnalogyIn this analogy, an individual rabbit represents a solution to the problem (i.e. a single point in the state space)– The state description is its DNA, if you willThe foxes represent the problem constraints– Solutions that do well are likely to surviveWhat we need to create are notions of natural selection, reproduction, and mutation10Core Elements of GAsFor selection, we use a fitness function to rank the individuals of the populationFor reproduction, we define a crossover operator which takes state descriptions of individuals and combines them to create new ones– What advantages does this present over local search?For mutation, we can merely choose individuals in the population and alter part of its state11Genetic Algorithm ExamplePOP = initialPopulation // build a new populationrepeat { // with every generationNEW_POP = emptyfor I = 1 to POP_SIZE { X = fit individual // natural selectionY = fit individualCHILD = crossover(X,Y) // reproductionif small random probability thenmutate(CHILD) // mutationadd CHILD to NEW_POP}POP = NEW_POP} until solution found or enough time elapsedreturn most fit individual in POP12Genetic Algorithm ExampleThe previous algorithm completely replaces the population for each new generation… but we can allow individuals from older generations to live onReproduction here is only between two parents (as in nature), but we can allow for more!!The population size also is fixed… but we can have this vary from one generation to the next313Genetic Algorithm Example Basically, there is no one GA, we can devise many variants of these 3 principles for nearly any problem!!Chapters 7 & 8 in How to Solve It: Modern Heuristics have a very thorough presentation of how to design genetic algorithms for particular problems14SelectionSelection (either to reproduce or live on) from one generation to the next relies on the fitness functionWe can usually think of the fitness function as being a heuristic, or the objective functionWe want to apply pressure that good solutions survive and bad solutions die– Too much and we converge to sub-optimal solutions– Too little and we don’t make much progress15SelectionDeterministic selection1. Rank all the individuals using the fitness function and choose the best k to survive2. Replace the rest with offspring– Can lead fast convergence (and local optima)Stochastic selection– Instead of selecting the best k, we could select each individual in proportion to its relative fitness to the population– Slower to converge, but could lose good solutions16SelectionTournament selection1. For each individual i, create a subset q of the population by random selection2. Assign a point to i for each individual in q that it “beats” (is less fit than itself)3. Rebuild the population based not on fitness scores, but the points accumulated in the tournament– As the size of q increases, though, it becomes more like deterministic selection17ReproductionThe unique thing about GAs is the ability of solutions to inherit properties from other solutions in the populationThe basic way to perform a crossover operation is to splice together parts of the state description from each parent… for example, in SAT:1 0 0 1 1 1 0 10 1 0 0 0 1 1 0parents1 0 0 1 0 1 1 00 1 0 0 1 1 0 1children18ReproductionThere are many different ways to choose crossover point(s) for reproduction:– Single-point: choose the center, or some “optimal” point in the state description… take the first half of one parent, the second half of the other– Random: choose the split point randomly(or proportional to the parents’ fitness scores)– n-point: make not 1 split point, but n different ones– Uniform: choose each element of the state description independently, at random (or proportional to fitness)419Reproduction for 8-QueensFor the 8-queens problem, we could choose a crossover point with the same number of queens on either sideWhat else could we do?20Reproduction for TSPFor TSP, our