Genetic Algorithms: When Drift Overcomes Selection

I often encounter posters here at TSZ who claim that Genetic Algorithms (GAs) either model or simulate evolution. They are never quite clear which it is, nor do they say what it means to model or simulate evolution (what would be required) and how GAs qualify as either one or the other. My position is that GAs neither model nor simulate evolution. In addition to other reasons I’ve given in the past I’d like to present the following argument.

GAs are often used to demonstrate “the power of cumulative selection.” Given small population sizes drift ought to dominate yet in GAs drift does not dominate. Why not?

Three questions:

  1. How do we determine the effective population size for a GA?
  2. How do we calculate the value of the selection coefficient?
  3. How do we determine when genetic drift will overcome the effects of selection?

In a GA written by keiths (a version of the WEASEL program) the default population size is 200.

#define POPULATION_SIZE 200 // total population size

Effective population size is the number of individuals in a population who contribute offspring to the next generation.

Even though the population size is 200, only one is selected to contribute offspring to the next generation.

#define NUM_SURVIVORS 1 // number of survivors per generation (must be less than POP_SIZE)

Given an effective population size of one, drift ought to dominate, but it doesn’t.

Given an effective population size of one, what must the selection coefficient be for drift to not dominate selection?

I’d truly appreciate any assistance with the concepts or the math.

In any event, there is no way that this GA (the keiths WEASEL program) either models or simulates evolution.

Reference:

Neutral Theory: The Null Hypothesis of Molecular Evolution

535 thoughts on “Genetic Algorithms: When Drift Overcomes Selection

  1. Frankie: “weasel” is a great example of evolution by intelligent design. Unfortunately people like you will never come to realize that all GAs are examples of evolution by intelligent design.

    Good. OK, let’s agree with Frankie. Then we can also of course conclude that mutation plus natural selection “is evolution by intelligent design”, and that intelligent design is what Darwin should have called his theory. So that way ID and the Modern Synthesis both get to win out.

  2. Joe Felsenstein: Good.OK, let’s agree with Frankie.Then we can also of course conclude that mutation plus natural selection “is evolution by intelligent design”, and that intelligent design is what Darwin should have called his theory.So that way ID and the ModernSynthesis both get to win out.

    .
    Natural selection includes mutation, Joe. And there isn’t any way to model natural selection producing something like ATP synthase.

    Again you show no clue as to what is actually being debated.

  3. For those who don’t know nor care natural selection includes mutation and that the mutations have to be happenstance occurrences (Mayr). Natural selection is not a search whereas GAs are- GAs actively search for solutions to problems they were designed to solve. NS doesn’t care and is not actively searching for anything.

    If the mutations happen by design and are guided towards some goal then that is the antithesis of natural selection.

  4. Frankie:
    For those who don’t know nor care natural selection includes mutation and that the mutations have to be happenstance occurrences (Mayr). Natural selection is not a search whereas GAs are- GAs actively search for solutions to problems they were designed to solve. NS doesn’t care and is not actively searching for anything.

    If the mutations happen by design and are guided towards some goal then that is the antithesis of natural selection.

    Why do you consider survival to NOT be a problem life solves? GAs provide environments constructed to reward results optimized for certain purposes. So does the Real World.

    It will be interesting watching our real-world experiment, to see if an environment increasingly overheated, polluted, and stripped of resources produces species adapted to thrive there.

  5. I do not have time to read Sal’s program and the other Weasel programs here, but was struck by the thought that some theory could be done. If interested, please bear with me (if not, please skip to the next comment). Imagine a Weasel program whose adult population size is one haploid genotype. To come close to a Wright-Fisher model of natural selection and mutation, we have that parent produce an infinite number of offspring. We’re going to have independent mutation at each of the L sites, with mutation rate u per site. We’re also going to assume a finite amount of natural selection at each site. At each site if there is a match to the target phrase, the fitness of that newborn is multiplied by 1+s compared to what it would be if not a match. Thus a genotype with m matches has relative fitness (1+s)^m.

    This is a particular fitness function, multiplicative fitness. Which is what you might expect if the sites aren’t interacting. In the infinite offspring population, if a site is the offspring of a non-matching site, the frequency of the matching allele is u/26. After natural selection acts, that is enriched to

        \[ \frac{\frac{u}{26}(1+s)}{1 - \frac{u}{26} + \frac{u}{26}(1+s)} \]

    which simplifies to

        \[ \frac{u(1+s)}{26 + su} \]

    Since the adult of the next generation is simply randomly chosen from the newborn pool once that pool has had its allele frequencies change owing to natural selection. The probability that a non-matching site changes to be matching is then the above quantity.

    Similarly one can imagine a matching site, and calculate the probability that it will change to become non-matching. That turns out to be

        \[ \frac{u}{u + (1-u)(1+s)}, \]

    or

        \[ \frac{u}{1+(1-u)s} \]

    Thus at each site there is a simple two-state Markov process with the states being Match and Don’t Match.

    The equilibrium distribution at a site is that, in the long run, there will be

        \[ \frac{\frac{u(1+s)}{26 + su}}{\frac{u}{1+(1-u)s}} \]

    times as large a probability of matching as of not matching.
    This simplifies to

        \[ \frac{(1+s)(1+(1-u)s)}{26+su} \]

    The interesting thing is that with this multiplicative selection, each site changes independently. To predict the time dynamics and equilibrium we can just predict the change at one site that starts out not matching, and also of one site that starts out matching. I will break off here for now. Check my algebra and tell me where I went wrong.

  6. keiths: Too difficult for you? Exceeds your attention span?

    Is it too difficult for you to try to figure out why it may be handy to have a program that doesn’t require a user sitting at a screen?

    I want to run many versions of the program at once, in parallel. Each run will use different parameters. I want to be able to halt a run that doesn’t seem to be converging and start up a new one in it’s place. I don’t want to have to sit at the computer screen trying to monitor all runs at once. These are the kinds of things computers are good at. Why would I do it manually?

    No, your program doesn’t allow the parameters to be set from the command line, but that can be changed.

    Multiple simultaneous runs with different parameter settings and without human monitoring.

    Now stop and let that sink in.

  7. petrushka: File a complaint with the moderator.

    Please join the rest of us in the modern world where we let computers do what they do best.

  8. Bunch of peckerheads who can’t think past the next gotcha. keiths thinks because he wrote his program one way that’s the only way it can be run.

  9. Mung: Please join the rest of us in the modern world where we let computers do what they do best.

    Don’t like it, write your own.

  10. Mung: It’s design all the way down.

    This is not an unreasonable position. Nature and natural processes are still far more ingenious designers than people, but I won’t argue that they produce designs. I think all snowflakes are works of art, and quite beautiful.

  11. Joe,

    It looks right to me, both algebraically and conceptually.

    Sal’s code is a mess, so I’ll make the appropriate changes to my program as time permits. Then we can compare program performance to model predictions.

  12. Is it too difficult for you to try to figure out why it may be handy to have a program that doesn’t require a user sitting at a screen?

    My program doesn’t require the user to sit in front of the screen. Think, Mung.

    I want to run many versions of the program at once, in parallel. Each run will use different parameters.

    Nobody’s stopping you from writing your own. In fact, if you had the skills, you could modify my program to do that instead of just whining that it doesn’t.

  13. keiths:
    Joe,

    Sal’s code is a mess, so I’ll make the appropriate changes to my program as time permits.Then we can compare program performance to model predictions.

    As long as you produce a set number of offspring, you can’t replicate the model that I described. To do it, the best way to simulate it would be to compute the probabilities of change at the matching sites and also at the unmatched sites. Then just choose a new adult sequence according to those.

    In that case my probabilities must match very closely.

    In all these cases unless s is infinite the Weasel will wander. In the long run the number of matched sites will be distributed in a binomial distribution whose mean can be worked out from the expressions I gave.

    I just did a few more calculations. At what value of s does selection have a noticeable impact? If there is no natural selection the expected ratio of matched to unmatched sites will be 1 : 26. If the mutation rate u is small, the ratio will approach (1+s)^2 / 26. That means that when s = 0.41421 the ratio of the predicted numbers of matched to unmatched sites will be double the no-selection value.

  14. Joe,

    As long as you produce a set number of offspring, you can’t replicate the model that I described.

    I can’t model an infinite population, obviously, but I can approximate it by a) using a large population size, and b) before randomly choosing the next parent, adjusting the probability of choosing any particular offspring to reflect the effects of differential fitness.

    In all these cases unless s is infinite the Weasel will wander. In the long run the number of matched sites will be distributed in a binomial distribution whose mean can be worked out from the expressions I gave.

    I’ll generate a histogram based on the fitness of the parent in each generation.

  15. Keiths:

    Sal’s code is a mess,

    That’s why I came to TSZ so you guys could help me clean it up. 🙂 It was worth the price of admission.

    As you have quickly found out, modelling fractional s_coefficients in populations of only 25 being truncated to 1 in each generation is not exactly straight forward nor textbook. Stuff has to be kludged to work with populations that small.

    Petrushka helped me find a bug in V2.

  16. Dazz,

    Thanks for finding an error, I’m working on fixing it.

    Patrick, thanks for the run and the crash, likely because I had a stray pointer.

    I had the wrong statement with

    kid[i] = (char *) malloc(target_strlen) + 1;

    should be

    kid[i] = (char *) malloc(target_strlen +1);

    Thanks again to all who provided comments and helpful criticisms.

  17. Sal,

    As you have quickly found out, modelling fractional s_coefficients in populations of only 25 being truncated to 1 in each generation is not exactly straight forward nor textbook. Stuff has to be kludged to work with populations that small.

    The approach I described above seems pretty straightforward, and it will work with small populations as well as large.

    The reason for using a large population is simply to track Joe’s model better. It isn’t because there’s anything difficult about handling small populations.

  18. Flint,

    Why do you consider survival to NOT be a problem life solves?

    Life is already alive- ie it is surviving. What GAs do has nothing at all to do with natural selection- already explained why that is.

  19. keiths: Nobody’s stopping you from writing your own. In fact, if you had the skills, you could modify my program to do that instead of just whining that it doesn’t.

    And we’re back to where we started.

    Mung: So here’s a potentially interesting exercise.

    Is there a way to tell if a WEASEL program is converging on the solution without waiting for it to halt?

    IOW, what if we want to play with the parameters without having to [potentially] wait forever to see if it finds the target?

    There’s no whining at all there about your program. That all came later, after you claimed your program did what I was asking for.

    Perhaps I should have asked the question this way:

    Is there a way to tell if a WEASEL program is not converging on the solution without waiting for it to never halt?

  20. Mung: Is there a way to tell if a WEASEL program is not converging on the solution without waiting for it to never halt?

    Not if there is a strong component of drift. A drifting population will not show steady progress.

  21. petrushka: Not if there is a strong component of drift. A drifting population will not show steady progress.

    And a drifting population will never produce any novel adaptations

  22. stcordova,

    As you have quickly found out, modelling fractional s_coefficients in populations of only 25 being truncated to 1 in each generation is not exactly straight forward nor textbook. Stuff has to be kludged to work with populations that small.

    Nah. I think you may have misunderstood the notion of selection coefficient. You don’t need to put a value on it at all. It comes out of the dynamics of the simulation. Essentially, everything at the same Hamming distance from the target will have the same selection coefficient (and will drift against each other), but the arrow will depend on what else is in the population at the time, and the degree of stochasticity you introduce into the selection process. At any point, the population will have a set of Hamming distances with a variance and mean. The mean will generally move. The variance will be the number of selectively distinct alleles in the population at that time. You can’t just attach a selection coefficient to each such allele, and you don’t need to.

  23. petrushka: Not if there is a strong component of drift. A drifting population will not show steady progress.

    Are you saying it is possible to detect whether there is convergence towards a solution but that it is not possible to detect whether there is not convergence towards a solution?

  24. Mung:

    And we’re back to where we started.

    Mung: So here’s a potentially interesting exercise.

    Is there a way to tell if a WEASEL program is converging on the solution without waiting for it to halt?

    The answer is the same as before. You look at the Fitness value that is displayed on the screen and observe whether it is increasing toward 28. You don’t have to wait for the program to halt.

    Is there a way to tell if a WEASEL program is not converging on the solution without waiting for it to never halt?

    Same answer. Watch the Fitness field.

  25. keiths,

    “But I don’t want to watch it. Is there a way to tell whether it is converging without me having to put any effort in?”

    One could, of course, graph the mean Hamming distance, which will almost certainly start out around 26 and a bit for random strings. If it stays at 26 and a bit, it’s not departing from random.

  26. Allan,

    One could, of course, graph the mean Hamming distance…

    But then Mung would have to look at the screen. Can’t we beam the information directly into his brain?

    P.S. Or equivalently, the mean fitness. The advantage of your approach is that Mung wouldn’t have to remember the fitness value of a perfect match. One less thing for him to screw up.

    ETA: Of course, he’d still have to remember that zero corresponded to a perfect match. Maybe we should just put a frowny/smiley face on the screen and modulate the emotion to match the Hamming distance.

  27. I watched Sal’s program, and it dithered around 25, sometimes dropping back to 16, but eventually reached the target. Don’t know what it was doing.

  28. keiths,

    he’d still have to remember that zero corresponded to a perfect match

    Yeah, my first version got the greater than/less than test the wrong way round. Less is more.

  29. A preview snapshot of the output of my drift vs. selection version of Weasel.

    It seems to be working, but I want to review my changes and add some more comments before posting my code.

  30. keiths: It seems to be working, but I want to review my changes and add some more comments before posting my code.

    Some tests would be nice.

  31. keiths: You’re welcome to test it to your heart’s content. I already have.

    keiths tested. atheist approved. heck of an endorsement. It didn’t crash isn’t much a test.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.