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 Algorithms2EvolutionHere’s a very oversimplified description of how evolution works in biologyOrganisms (animals or plants) produce a number of offspring which are almost, but not entirely, like themselvesVariation 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’tThe “better adapted” offspring are more likely to surviveOver time, later generations become better and better adaptedGenetic algorithms use this same process to “evolve” better programs3Genotypes and phenotypesGenes are the basic “instructions” for building an organismA chromosome is a sequence of genesBiologists 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 algorithmStart with a large “population” of randomly generated “attempted solutions” to a problemRepeatedly do the following:Evaluate each of the attempted solutionsKeep a subset of these solutions (the “best” ones)Use these solutions to generate a new populationQuit when you have a satisfactory solution (or you run out of time)5A really simple exampleSuppose your “organisms” are 32-bit computer wordsYou want a string in which all the bits are onesHere’s how you can do it:Create 100 randomly generated computer wordsRepeatedly do the following:Count the 1 bits in each wordExit if any of the words have all 32 bits set to 1Keep 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) itNote that this procedure does not guarantee that the next “generation” will have more 1 bits, but it’s likely6A more realistic example, part ISuppose you have a large number of (x, y) data pointsFor 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 pointsThat is, you want a formula y = ax5 + bx4 + cx3 + dx2 +ex + f that gives you a reasonably good fit to the actual dataHere’s the usual way to compute goodness of fit:Compute the sum of (actual y – predicted y)2 for all the data pointsThe lowest sum represents the best fitThere are some standard curve fitting techniques, but let’s assume you don’t know about themYou can use a genetic algorithm to find a “pretty good” solution7A more realistic example, part IIYour formula is y = ax5 + bx4 + cx3 + dx2 +ex + fYour “genes” are a, b, c, d, e, and fYour “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 + fFind the sum of (y – ý)2 over all xThe 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 = 13If these are the only two data points, the “badness” of [0, 0, 0, 2, 3, 5] is 138A more realistic example, part IIIYour algorithm might be as follows:Create 100 six-element arrays of random numbersRepeat 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 sixPick a random floating-point number between 0.0 and 2.0Multiply the random element of the array by the random floating-point numberAfter all 500 trials, pick the best array as your final answer9Asexual vs. sexual reproductionIn the examples so far,Each “organism” (or “solution”) had only one parentReproduction was asexual (without sex)The only way to introduce variation was through mutation (random changes)In sexual reproduction,Each “organism” (or “solution”) has two parentsAssuming 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 againSuppose your “organisms” are 32-bit computer words, and you want a string in which all the bits are onesHere’s how you can do it:Create 100 randomly generated computer wordsRepeatedly do the following:Count the 1 bits in each wordExit if any of the words have all 32 bits set to 1Keep 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 wordsTake the first half of this word and combine it with the second half of the other word11The example continuedHalf 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 0101Or 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 0101Or 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 examplesIn the simple example (trying to get all 1s):The sexual (two-parent, no mutation) approach, if it succeeds, is likely to succeed much fasterBecause up to half of the
View Full Document