Chapter 9:Beyond EngineeringCS105: Great Insights in Computer ScienceGenetic 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 ProblemsSegway SpillEngineering 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!GA Circle of Life010100101001100110populationindividualinterpretationsolution 1solution 2solution 3fitness evaluation139641selection010100101001100110reproduction/crossover101000101001100110mutation101000101001110110next generation• Each generation tends to improve on the previous ones.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)?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’ AccomplishmentsCreatures• In each case:- Sims wrote a program to turn bit sequences into creatures (bodies and behaviors).- Fitness was evaluated by “running” creatures in a simulated 3d world.- Higher scoring (more fit) individuals replicated.• Surprisingly interesting creatures created!A 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 appears as if everything is connected to everything else---unlike the neat, hierarchical