Lecture 21:Genetic AlgorithmsCS105: Great Insights in Computer ScienceMichael L. Littman, Fall 2006Genetic Algorithms• First scientific talk I went to (college): John Holland on Genetic Algorithms.• Inspiring! (Try it sometime.)• Haven’t quite lived up to their promise, but still useful and interesting.• Sometimes called “the second best way to solve any problem”.Brain• 1012 neurons, 105 connections per neuron.• That’s 1,000,000,000,000 (a million millions) neurons, each with 100,000 (a hundred thousand) connections.• Areas specialized: Example, Broca’s area aids in producing grammatical speech.Frog ExperimentThere was this biologist who was doing some experiments with frogs.He was measuring just how far frogs could jump.So, he puts a frog on a line and says "Jump frog, jump!".The frog jumps 2 feet.He writes in his lab book: 'Frog with 4 legs - jumps 2 feet'.Next, he chops off one of the legs and repeats the experiment."Jump frog jump!" he says.The frog manages to jump 1.5 feet.So he writes in his lab book: 'Frog with 3 legs - jumps 1.5 feet'. He chops off another and the frog only jumps 1 foot.He writes in his book: 'Frog with 2 legs jumps 1 foot'.He continues and removes yet another leg." Jump frog jump!" and the frog somehow jumps a half of a foot.So, he writes in his lab book again: 'Frog with one leg - jumps 0.5 feet'.Finally, he chops off the last leg. He puts the frog on the line and tells it to jump."Jump frog, jump!".The frog doesn't move."Jump frog, jump!!!". Again the frog stays on the line."Come on frog, jump!". But to no avail.The biologist finally writes in his book: 'Frog with no legs - goes deaf'.Specialized, And Yet...• Functions can shift around.• Some functions appear to have elements in multiple areas.• Some areas appear responsible for only vaguely related functions.• Doesn’t seem to have a clean hierarchical functional breakdown like a human-designed processor might.Software ProblemsEngineering Failures• Therac-25: Radiation-treatment machine overdoses patients if operator types too fast.• Patriot missile tracking system: Time measured in tenths of a second, which cannot be accurately represented in binary. Round off error caused it to gradually lose precision.• Mars Climate Orbiter: Lost on entry into the Martian atmosphere because code inconsistently used feet & meters.• Mars Polar Lander: Software misinterpreted the extension of its landing legs as landing, causing engine shutdown.• Ariane 5: Satellite launch missile software couldn’t convert 16-bit real number to 16-bit integer and crashed in flight.Engineering Methodology?• Hillis argues that this type of catastrophic failure is traceable to the engineering process itself: modules built in isolation, often not fully tested together.• Suggests a more holistic way of building complex systems: Genetic Algorithms.GA: New Way To Search• Each solution is an individual and the set is the population. Set size is maybe 200.• Objective function score is fitness.• Higher objective function value solutions are replicated to allow more search to proceed from these examples: asexual reproduction.• Local search steps are mutation. Optimization proceeds in a series of generations.• Two solutions can be combined to create a new one: crossover.• Fit individuals allowed to reproduce, unfit individuals don't. Inspired by Darwinian evolution!Algorithmic Options• What do you need to define to create a GA solution to a problem?• What is the fitness function?• How is an individual represented?• How are individuals selected for reproduction?• How are individuals altered (mutation)?• How do individuals combined (crossover)?Example Problem• Find a 2-coloring of this graph.• Nodes can be black or white. Two nodes that are linked cannot be the same color.Representation Choices• What is the fitness function?• Number of mismatched edges.• How is an individual represented?• n bits (0 = white, 1 = black)Algorithm Choices• How are individuals selected for reproduction?• Less fit half “killed”, remainder get to mate at random.• How are individuals altered (mutation)?• Each generation, one individual chosen to have each bit randomized wp 1/11.• How are individuals combined (crossover)?• Each bit randomly selected from parent.Code: Main Loopdef ga(): p = population() gen = 0 done = 0 while (not done): p = thin(p) winner = fitness(p[0]) p = reproduce(p) i = randint(0,m-1) p[i] = mutate(p[i]) print gen, p[0], winner, sum([fitness(x) for x in p]) done = (winner == n+1) gen = gen + 1makes initial random populationsorts individuals by fitness, deletes bottom halffills in missing half via crossover of existing individualspicks an individual to mutate (set a bit at random)Pop Opsdef mate(x,y): str = "" for i in range(n): if randint(0,1) == 0: str = str + x[i] else: str = str + y[i] return strdef reproduce(p): kids = [] for j in range(m/2): x = p[j] y = p[randint(0,m/2-1)] kids = kids + [mate(x,y)] return p+kidsdef mutate(x): str = "" for i in range(n): if randint(0,10) == 0: if randint(0,1) == 0: str = str + "0" else: str = str + "1" else: str = str + x[i] return strdef thin(p): p.sort(compareFitness) return p[:(m/2-1)]And You Were There...• loops, strings, lists• sorting• random numbers• bits• search / hillclimbing• formal problem• objective function• parallelismKarl Sims’ AccomplishmentsA Virtual Debate• W. Daniel Hillis: Ph.D. in Computer Science at MIT, invented of the 64k processor Connection Machine, the 10,000 year clock, Chairman and Chief Technology Officer of Applied Minds.• Michael J. Behe: Ph.D. in Biochemistry from Penn, Professor at Lehigh, coined the phrase “irreducible complexity”, Fellow of the Discovery Institute.Recognizing Design• Behe (talking about a car): “... when he opens up the hood and sees the engine, he immediately realizes that it was designed.”• Hillis (talking about a monkey brain): “Looking at it
View Full Document