Genetic Algorithms课件.ppt

The 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 0101 Comparison 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 bits change each time, not just one bit However, with no mutation, it may not succeed at all By pure bad luck, maybe none of the first (randomly generated) words have (say) bit 17 set to 1 Then there is no way a 1 could ever occur in this position Another problem is lack of genetic diversity Maybe some of the first generation did have bit 17 set to 1, but none of them were selected for the second generation The best technique in general turns out to be sexual reproduction with a small probability of mutation Curve fitting with sexual reproduction 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] What’s the best way to combine two chromosomes into one? You could choose the first half of one and the second half of the other: [a, b, c, d, e, f] You could choose genes randomly: [a, b, c, d, e, f] You could compute “gene averages:” [(a+a)/2, (b+b)/2, (c+c)/2, (d+d)/2, (e+e)/2,(f+f)/2] I suspect this last may be the best, though I don’t know of a good biological analogy for it Directed evolution Notice that, in the previous examples, we formed the child organisms randomly We did not try to choose the “best” genes from each parent This is how natural (biological) evolution works