DOC PREVIEW
Penn CIT 594 - Genetic Algorithms

This preview shows page 1-2-19-20 out of 20 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 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 20 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 20 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 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Genetic AlgorithmsEvolutionGenotypes and phenotypesThe basic genetic algorithmA really simple exampleA more realistic example, part IA more realistic example, part IIA more realistic example, part IIIAsexual vs. sexual reproductionThe really simple example againThe example continuedComparison of simple examplesCurve fitting with sexual reproductionDirected evolutionProbabilistic matchingGenetic programmingShrinking the search spacePrograms as treesConcluding remarksThe EndJan 18, 2019Genetic Algorithms2EvolutionHere’s a very oversimplified description of how evolution works in biologyOrganisms (animals or plants) produce a number of offspring which are almost, but not entirely, like themselvesVariation may be due to mutation (random changes)Variation may be due to sexual reproduction (offspring have some characteristics from each parent)Some of these offspring may survive to produce offspring of their own—some won’tThe “better adapted” offspring are more likely to surviveOver time, later generations become better and better adaptedGenetic algorithms use this same process to “evolve” better programs3Genotypes and phenotypesGenes are the basic “instructions” for building an organismA chromosome is a sequence of genesBiologists distinguish between an organism’s genotype (the genes and chromosomes) and its phenotype (what the organism actually is like)Example: You might have genes to be tall, but never grow to be tall for other reasons (such as poor diet)Similarly, “genes” may describe a possible solution to a problem, without actually being the solution4The basic genetic algorithmStart with a large “population” of randomly generated “attempted solutions” to a problemRepeatedly do the following:Evaluate each of the attempted solutionsKeep a subset of these solutions (the “best” ones)Use these solutions to generate a new populationQuit when you have a satisfactory solution (or you run out of time)5A really simple exampleSuppose your “organisms” are 32-bit computer wordsYou want a string in which all the bits are onesHere’s how you can do it:Create 100 randomly generated computer wordsRepeatedly do the following:Count the 1 bits in each wordExit if any of the words have all 32 bits set to 1Keep the ten words that have the most 1s (discard the rest)From each word, generate 9 new words as follows:Pick a random bit in the word and toggle (change) itNote that this procedure does not guarantee that the next “generation” will have more 1 bits, but it’s likely6A more realistic example, part ISuppose you have a large number of (x, y) data pointsFor example, (1.0, 4.1), (3.1, 9.5), (-5.2, 8.6), ...You would like to fit a polynomial (of up to degree 5) through these data pointsThat is, you want a formula y = ax5 + bx4 + cx3 + dx2 +ex + f that gives you a reasonably good fit to the actual dataHere’s the usual way to compute goodness of fit:Compute the sum of (actual y – predicted y)2 for all the data pointsThe lowest sum represents the best fitThere are some standard curve fitting techniques, but let’s assume you don’t know about themYou can use a genetic algorithm to find a “pretty good” solution7A more realistic example, part IIYour formula is y = ax5 + bx4 + cx3 + dx2 +ex + fYour “genes” are a, b, c, d, e, and fYour “chromosome” is the array [a, b, c, d, e, f]Your evaluation function for one array is:For every actual data point (x, y), (I’m using red to mean “actual data”)Compute ý = ax5 + bx4 + cx3 + dx2 +ex + fFind the sum of (y – ý)2 over all xThe sum is your measure of “badness” (larger numbers are worse)Example: For [0, 0, 0, 2, 3, 5] and the data points (1, 12) and (2, 22):ý = 0x5 + 0x4 + 0x3 + 2x2 +3x + 5 is 2 + 3 + 5 = 10 when x is 1ý = 0x5 + 0x4 + 0x3 + 2x2 +3x + 5 is 8 + 6 + 5 = 19 when x is 2(12 – 10)2 + (22 – 19)2 = 22 + 32 = 13If these are the only two data points, the “badness” of [0, 0, 0, 2, 3, 5] is 138A more realistic example, part IIIYour algorithm might be as follows:Create 100 six-element arrays of random numbersRepeat 500 times (or any other number):For each of the 100 arrays, compute its badness (using all data points)Keep the ten best arrays (discard the other 90)From each array you keep, generate nine new arrays as follows:Pick a random element of the sixPick a random floating-point number between 0.0 and 2.0Multiply the random element of the array by the random floating-point numberAfter all 500 trials, pick the best array as your final answer9Asexual vs. sexual reproductionIn the examples so far,Each “organism” (or “solution”) had only one parentReproduction was asexual (without sex)The only way to introduce variation was through mutation (random changes)In sexual reproduction,Each “organism” (or “solution”) has two parentsAssuming that each organism has just one chromosome, new offspring are produced by forming a new chromosome from parts of the chromosomes of each parent10The really simple example againSuppose your “organisms” are 32-bit computer words, and you want a string in which all the bits are onesHere’s how you can do it:Create 100 randomly generated computer wordsRepeatedly do the following:Count the 1 bits in each wordExit if any of the words have all 32 bits set to 1Keep the ten words that have the most 1s (discard the rest)From each word, generate 9 new words as follows:Choose one of the other wordsTake the first half of this word and combine it with the second half of the other word11The example continuedHalf from one, half from the other:0110 1001 0100 1110 1010 1101 1011 0101 1101 0100 0101 1010 1011 0100 1010 0101 0110 1001 0100 1110 1011 0100 1010 0101Or we might choose “genes” (bits) randomly:0110 1001 0100 1110 1010 1101 1011 0101 1101 0100 0101 1010 1011 0100 1010 0101 0100 0101 0100 1010 1010 1100 1011 0101Or we might consider a “gene” to be a larger unit:0110 1001 0100 1110 1010 1101 1011 0101 1101 0100 0101 1010 1011 0100 1010 0101 1101 1001 0101 1010 1010 1101 1010 010112Comparison of simple examplesIn the simple example (trying to get all 1s):The sexual (two-parent, no mutation) approach, if it succeeds, is likely to succeed much fasterBecause up to half of the


View Full Document

Penn CIT 594 - Genetic Algorithms

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
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?