DOC PREVIEW
Rutgers University CS 105 - Genetic Algorithms

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Rutgers University CS 105 - Genetic Algorithms

Download Genetic Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Genetic Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Genetic Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?