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. Neil Rickert: Drift takes over when the selective pressure is low.

    Not true. Drift is ever present.

    It is important to note, however, that the impact of genetic drift is not limited to neutral mutations. Because of genetic drift, most advantageous mutations are eventually lost, whereas some weakly deleterious mutations may become fixed.

    ETA: I see Joe beat me to it. 🙂

  2. Mung,

    keiths: Not only did he demand a general-purpose GA — he wants one that can solve any problem.

    That is false. My claim was that it can’t be done.

    keiths:
    Of course, no one here claimed that there was such a GA.

    AFIAK, no one claimed there wasn’t such a GA, except me. You have evidence to the contrary?

    That’s not how I remember the discussion, so I looked it up. Here’s your last comment on that thread:

    Meanwhile, you and all the other fans of GA’s here at TSZ just can’t be bothered to create an OP and publish the generic GA that can solve any problem.

    It doesn’t look like the claim you said you were making.

  3. Patrick: It doesn’t look like the claim you said you were making.

    Well, technically he didn’t say it CAN be done, he was simply mocking others for failure to “bother” to produce one.

  4. Flint: Well, technically he didn’t say it CAN be done, he was simply mocking others for failure to “bother” to produce one.

    But then he claimed he claimed it can’t be done.

    Who said it could? Why did mung bring it up in the first plsce?

  5. petrushka: But then he claimed he claimed it can’t be done.

    Who said it could? Why did mung bring it up in the first plsce?

    My guess is, he was simply getting in a cheap shot. What’s your guess?

  6. Flint: My guess is, he was simply getting in a cheap shot. What’s your guess?

    I can’t guess mung’s motives, but everyone has a choice either to make a positive case for their position, or to monkey wrench the works.

  7. petrushka: I can’t guess mung’s motives, but everyone has a choice either to make a positive case for their position, or to monkey wrench the works.

    I think I actually understand what Joe was saying. Drift will be stronger than selection under circumstances where a population is highly adapted to its environment, the environment is fairly static, and no mutations make some slightly different environment more suited (in which case selection sets in again). It seems a truism that the better fitted a population is, the less likely any mutation is to be beneficial, while drift is a constant, unavoidable background noise.

  8. Mung:

    In the example GA provided by keiths, 199 members of the population get killed off and one member survives and produces 200 offspring to seed the next generation.

    keiths:

    No. One member survives and is retained in the population, while 199 members are killed off and replaced by mutated copies of the survivor:

    Mung:

    A fine bit of pedantry!

    It isn’t pedantry. The difference has a considerable effect on the amount of drift. Think about it.

    You’re the one worried about drift, remember?

  9. keiths:

    He’s hoping that Weasel somehow cheats and uses drift, not selection, to achieve its success.

    Mung:

    Um, no.

    Um, yes. You wrote:

    Are we really seeing “the power of cumulative selection” or are we seeing “the power of cumulative random sampling”?

    The answer, of course, is that we’re seeing the power of cumulative selection. Turn off selection and the program won’t converge on the target.

  10. Mung:

    Meanwhile, you and all the other fans of GA’s here at TSZ just can’t be bothered to create an OP and publish the generic GA that can solve any problem.

    keiths:

    Of course, no one here claimed that there was such a GA.

    Mung:

    AFIAK, no one claimed there wasn’t such a GA, except me.

    Exactly. You’re the one obsessed with battling straw men. The rest of us just watch and laugh.

    This is you, except you’re not as cute.

  11. Mung: Richardthughes, there is a glaring problem with your claim and the claim of keiths and that is that keiths agrees with me.

    Eh? is this in response to

    keiths: I’m disinclined to take your word for it, for good reason.

    Because I think I’ve explained so that even you can understand that even though you’re posting in good faith, it’s highly likely you’re wrong. What exactly do you and KeithS agree on? that you don’t understand GAs?

  12. Rich,

    Why can’t linear regression make me a coffee?

    It’s pretty funny how hard Mung will work at scraping up something to complain about.

    Hey Mung, have you noticed that you can’t shave with your slow cooker? Time to demand a refund.

  13. I think I’ve identified the source of Mung’s confusion. He seems to have focused on this sentence from the Nature article:

    In other words, in small populations, the stochastic effects of random genetic drift overcome the effects of selection.

    Since Mung doesn’t understand GAs or evolution, he read that statement uncritically and literally. It’s reflected in these claims of his:

    Given small population sizes drift ought to dominate yet in GAs drift does not dominate.

    And:

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

    But it isn’t population size alone that allows drift to overpower selection. The selection coefficient also matters, as the Nature article makes clear:

    It is important to note that the effectiveness of selection on a mutation depends both on the fitness effect of this mutation (the selection coefficient s) and on the effective population size (Ne). Specifically, when the product Ne * s is much less than 1, the fate of mutations is essentially determined by random genetic drift. In other words, in small populations, the stochastic effects of random genetic drift overcome the effects of selection. Thus, all mutations for which Ne * s is much less than 1 can be considered effectively neutral.

    Mung seems to have realized that the selection coefficient matters, as the Nature article stresses. He wrote:

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

    Yet he went ahead and made his categorical statements despite having no inkling of the actual value of the selection coefficient.

    Typical Mung sloppiness.

  14. Yes, and as already explained by Prof. Felsenstein, the selection coefficient in these GA’s is infinite, simply because drift is not modeled (if evaluation of the fitness function produces the same value as the former max, the new mutant is discarded: only fitter mutants are kept)

    How can you keep asking such dumb questions as “why doesn’t drift take over” Mung? BTW, if only selection is modeled, that makes these GA’s purely Darwinian evolution models. Modeling larger populations, drift, more complex/accurate mutational models, speciation… all that increases the computational cost, in some cases exponentially

    Will any of that ever sink Mung? I doubt it

  15. Flint,

    I think I actually understand what Joe was saying. Drift will be stronger than selection under circumstances where a population is highly adapted to its environment, the environment is fairly static, and no mutations make some slightly different environment more suited (in which case selection sets in again). It seems a truism that the better fitted a population is, the less likely any mutation is to be beneficial, while drift is a constant, unavoidable background noise.

    I don’t think that’s quite it (though not wrong).

    Drift is the stochastic component of allele frequency change. You get more departure from expectation with small sample sizes than with larger – larger samples converge on the expected value. So for a given nonzero selection coefficient, a small population is more likely to depart from the expectation – the mean of infinite runs – than a large one. But this also depends on the coefficient itself. Small selection coefficients have a larger component of drift, and so need bigger populations to allow convergence on that mean.

    But further, when an allele is rare, however big a population it is in, it can simply disappear through drift, regardless of its selection coefficient, before sufficient trials have been performed to converge significantly on its mean.

    In a well adapted population, it is true that fewer novel alleles will be beneficial, and so drift will dominate. But that’s not drift being stronger than selection; the selection coefficients of novel alleles has gone down.

  16. Given small population sizes drift ought to dominate yet in GAs drift does not dominate. Why not?

    Um, because they’re not made to mimic drift, even if drift often does occur with GAs anyway.

    Why don’t GAs model extinction by asteroid? After all, it looks like that has happened (likely along with other stressors).

    Funny, GAs don’t fully model everything that happens in evolution. I just don’t remember anyone suggesting that they do, rather they were made to take advantage of what “natural selection” can do.

    Glen Davidson

  17. GlenDavidson: Funny, GAs don’t fully model everything that happens in evolution. I just don’t remember anyone suggesting that they do, rather they were made to take advantage of what “natural selection” can do

    WEASEL is perhaps the simplest possible version of a GA, and yet the folks at UD spent months months failing to comprehend how it works. Even years later, Mung fails to understand how it works. Apparently, Dembski failed for some years to understand how it works. I don’t think kariosfocus understands it yet.

    It’s really the baseline from which you could hold a useful discussion of evolution. Without understanding it, no further discussion is possible.

    I recommend that Mung write a WEASEL program from scratch, following the recipe, and watch how it works, and as keiths suggests, play with it.

  18. Joe Felsenstein: This would make the model nearly a Wright-Fisher model. Movement toward the target would be slower.

    ..I would also think it wouldn’t be linear. Could we say that the lack of linearity was due to drift?

  19. Petrushka:

    WEASEL is perhaps the simplest possible version of a GA, and yet the folks at UD spent months months failing to comprehend how it works. Even years later, Mung fails to understand how it works. Apparently, Dembski failed for some years to understand how it works. I don’t think kariosfocus understands it yet.

    But Cordova made his own version of WEASEL with some improvements, so much so his GA is known as “Cordova’s Remarkable Genetic Algorithm”:

    http://www.pandasthumb.org/archives/2006/08/calling_ids_blu_1.html

    Cordova’s algorithm is exactly like Dawkins’ “Weasel”, with the major difference being that, while Dawkins was searching for the specific target “METHINKS IT IS LIKE A WEASEL,” Cordova is searching for the specific sequence of numbers 251, 252, 253, … 750. When these are summed and doubled, the result is the sum of the numbers from 1 to 1000: 500,500.
    ….
    As an exercise in Smoke and Mirrors, Cordova’s algorithm is remarkable.

    I understood WEASEL, I even improved upon by making work like a Rube Goldberg machine to boot. It illustrates how an intelligent designer (me) can engineer selection to work toward a pre determined goal.

  20. stcordova: I understood WEASEL, I even improved upon by making work like a Rube Goldberg machine to boot. It illustrates how an intelligent designer (me) can engineer selection to work toward a pre determined goal.

    Since the point of WEASEL is to make the operation of a GA transparent, making it opaque is hardly an improvement.

    Why not use your intelligence for something useful, like understanding how a GA works when the target is not otherwise known or is not fixed?

  21. 1. Drift over comes selection when the population size is small. The most extreme conceptual example is a sexually reproducing population of 2 being maintained constantly.

    2. Drift over comes selection if the selection strength is weak, weak enough to make the advantage look nearly neutral.

    If hypothetically we had a biased coin that would be heads 52% of the time, it doesn’t mean flipping it will guarantee heads just because it has a bias toward heads. It’s the same thing with selection especially in sexually reproducing populations where there is an almost random flip whether the genes from one parent even get passed on to the kid!

    In fact an advantageous trait can be blasted by drift out of a population:

    if a mutant gene is selectively neutral the probability is 0.79 that it will be lost from the population
    ….
    if the mutant gene has a selective advantage of 1%, the probability of loss during the fist seven generations is 0.78. As compared with the neutral mutant, this probability of extinction [with natural selection] is less by only .01 [compared to extinction by purely random events].
    ….

    Theoretical Aspects of Population Genetics
    Motoo Kimura and Tomoko Ohta

    Contrast that with Darwin’s naive view:

    Natural Selection is daily and hourly scrutinising, throughout the world, the slightest variations; rejecting those that are bad, preserving and adding up all that are good.

    C.DARWIN sixth edition Origin of Species — Ch#4 Natural Selection

    Darwin’s view has been falsified by Kimura, but it persists — WEASEL is an example of that naive view.

  22. stcordova:Darwin’s view has been falsified by Kimura, but it persists — WEASEL is an example of that naive view.

    A view is not false because it is simplified. As an analogy, consider the migration of a butterfly. Watch it all day, and it flies apparently at random, in all directions. Overall, it actually does move several miles per day in a consistent direction. So is it false to say the butterfly is flying in that direction?

    Darwin’s statement reflects a statistical pattern, not a rigid rule. I doubt even Darwin thought that every beneficial mutation, however slight, went quickly to fixation, while every deleterious mutation, however slight, was guaranteed to render its possessor infertile.

  23. The accuracy of WEASEL to model biological evolution would be greatly improved if selection of advantageous traits were not deterministic (as in always picking the best).

    If something in WEASEL is 1% better than all others, it always gets selected for.

    A more realistic scenario is that it frequently gets accidentally selected against — much like a coin biased to be heads 52% of the time flips tails 48% of the time! This will add drift to the model!

    Then if such advantaged traits only show up once in a buzillion trials, then we start to see a higher fidelity model for TRG and complex autapomorphy evolution.

    Add more realism where selection has to clean out bad traits that newly emerge when bad trait ratio is 1000 bad to 1 good, then we run into genetic load and genetic erosion scenarios. Thus accumulation via cumulative selection become the exception rather than the norm.

    Add interspecies competition whereby 10 species can be wiped out by 1 successful species, then we have “Elimination of Species by Means of Natural Selection”.

    In light of these considerations, the ANNIHILATOR model starts to look more accurate. The Blind Watch Destroyer is the book Dawkins should have written.

  24. stcordova,

    On The Use Of Tools That Don’t Work, by STC …

    And yet, when these refinements are introduced, digital populations do not universally come crashing down about the researchers’ ears. Hence the use of these models in investigating these very phenomena.

  25. stcordova: The accuracy of WEASEL to model biological evolution would be greatly improved if selection of advantageous traits were not deterministic (as in always picking the best).

    Sal, I gave you a link to a simple WEASEL variant, and you haven’t looked at it or commented on it. It combines selection, drift and occasional death of the fittest.

    And there are far more sophisticated models.

    A naive person might conclude you are afraid to look at the literature.

    Being able to understand WEASEL puts you a notch ahead of nearly all the UD denizens, but that bar is not high.

  26. The way to make Dawkins WEASEL into DRIFTING WEASEL:

    Let the 1 good trait be assigned a selective (S-coefficient) of 0.1% and all the bad -0.1%.

    Say the ratio is 24 bad vs. 1 good.

    What are the odds, the bad mutation gets selected? Darn near 96% for bad, 4% for good.

    (24 * (1-0.001) ) = 23.976 bad individuals
    1 * (1 + .001) = 1.001 good individuals

    1.001 / (23.976 + 1.001) = 4.01% chance of good getting passed on
    23.976/ (23.976 + 1.001) = 95.99% chance of bad being passed on

    We can see from this DRIFTING WEASEL will have substantially worse performance than Dawkins WEASEL. In fact, in light of this, I’m not so sure how quickly DRIFTING WEASEL will reach the goal since if selection is weak enough, evolution could go in reverse and be like a random walk.

  27. stcordova: The way to make Dawkins WEASEL into DRIFTING WEASEL:

    A simpler way would be to make it into a real GA, and have a reproducing population, rather than always selecting the “fittest single individual.

    Why is you don’t care to look at GAs where this is done?

  28. A simpler way would be to make it into a real GA,

    What software GA isn’t fundamentally deterministic whereby the most advantaged is always selected and there is no chance for the less advantaged to be the one chosen.

    I provided the illustration of how to build DRIFTING WEASEL. Any takers? Or if I build it, are you guys not going to believe the results any way? Better you guys build it. I provided concepts almost straight out of pop gen with my interpretation of S-coefficients.

    Btw, the way I put the numbers, the first version of DRIFTING WEASEL will go to extinction, do you see why? 🙂

  29. Sal, I gave you a link to a simple WEASEL program that doesn’t always select the most fit. Have you looked at it?

  30. Sal, I gave you a link to a simple WEASEL program that doesn’t always select the most fit. Have you looked at it?

    If that was the language one, yes. To be honest, I didn’t understand why the thing worked.

    Apologies, didn’t mean to be dismissive.

    Maybe I’ll go ahead and write DRIFTING WEASEL someday.

    But what I just wrote above, illustrates situation when mutation and drift will become little different from a random walk even if selection is present.

    Since so many mutants are being added each generation (96% chance there will be damage even supposing the prior generation had a gain), I think DRIFTING WEASEL will not hit the target any time soon, it might only be marginally better than a random walk on astronomical scales.

  31. stcordova: If that was the language one, yes. To be honest, I didn’t understand why the thing worked.

    Did you bother to ask?

  32. What if there is no target, just degrees of “goodness” scattered weblike in phase space.

  33. I’m just wondering why you pontificate about what would happen, you write post after post about imaginary programs you haven’t bothered to write, ignore the literature on GAs that actually solve commercially useful problems, and so forth.

  34. I always thought WEASEL wasn’t intended as any sort of model of evolution or any sort of GA. And that’s because it had a predetermined target, which real GAs and nature lack. So it was only intended to show that selection is far far more powerful than creationists give it credit for.

    The next breakthrough, if anyone reaches it, is to recognize that selection can act, and is just as powerful, even when there is no specific target, and even when the ground is shifting under your feet.

  35. Ok, I just sent this to one of the underground forums (reddit/r/creation), maybe someone there will pitch in to write DRIFTING WEASEL:

    [ Slightly advanced topic.

    The following link is the middle of a conversation at The Skeptical Zone why I think Dawkins WEASEL program is flawed.

    When we some randomness as to what gets selected for the next generation, Darwinian ideas totally break down.]

    I wrote down a simple specification of the basic idea, namely, even if a trait is slightly advantaged, it only has a 4% chance of getting passed on to the next generaiton, and there is a 96% chance bad mutations get passed on to the next generation! 🙂 It’s that simple.

    If any one wants to write software for , this would be a great project to illustrate the failure of Dawkins BlindWatchmaker. Some humorous graphics (like a weasel exploding) won’t hurt. 🙂 I could probably write it in a week, JoeCoder maybe in 30 minutes, but some graphics would be nice.

    So here is the discussion so far:

    http://theskepticalzone.com/wp/genetic-algorithms-when-drift-overcomes-selection/comment-page-2/#comment-111375

    JoeCoder or any IT types, feel free to visit TSZ. They are generally civil over there, and if you don’t like someone, you can push the “Ignore” button and you won’t see their troll trash any more.

  36. Sal, get over trying to extrapolate from a toy program and profound implications for population genetics. WEASEL doesn’t have a population.

    But suppose you take your drifting weasel and make it select a population rather than an individual. Make it semi-realistic by allowing the number of offspring vary according to “fitness”.

    Now, in nature, fit individuals may have tens or even tens of thousands of offspring. So you could take your fitness scores and assign some sort of reproductive penalty for lower fitness.

    Do you think you could predict the outcome? How about in nature?

  37. petrushka,

    A simpler way would be to make it into a real GA, and have a reproducing population, rather than always selecting the “fittest single individual.

    Why is you don’t care to look at GAs where this is done?

    Here you go, Sal:

    “Another significant variation is that reproduction in this GA engine is stochastic. The most fit individual in a population is not guaranteed to be selected as a parent of the next generation population.”

    ETA: Sal asks “What software GA isn’t fundamentally deterministic whereby the most advantaged is always selected and there is no chance for the less advantaged to be the one chosen.”

    Answer: This one.

  38. stcordova,

    Ok, I just sent this to one of the underground forums (reddit/r/creation)

    That’s not an underground forum, it’s just a subreddit that was made non-public because the creationists posting there were getting their asses kicked in every argument.

  39. Of course, WEASEL never goes extinct, so any fitness coefficient will show progress.

    The problem of declining fitness in biology is solved by fecundity.

    Obviously, if you start with a tiny population having a significant number of recessive and detrimental traits, the population can run to extinction. We’ve seen it happen.

    But we also have good reason to believe that many island populations have started by single individuals or very small populations. If a population, through ordinary fecundity, reaches a size level, the ordinary process of neutral mutation begins to provide diversity. In island populations, this can be measured.

  40. Patrick:
    stcordova,
    That’s not an underground forum, it’s just a subreddit that was made non-public because the creationists posting there were getting their asses kicked in every argument.

    I shudder to think what credentials you must have to be invited.

  41. http://sandwalk.blogspot.com/2015/12/waiting-for-multiple-mutations-michael.html

    https://www.researchgate.net/publication/25916970_A_response_to_Michael_Lynch

    (Response to Lynch 2005, not to Lynch 2010)

    Behe’s most recent response includes the assertion that complex adaptations must include deleterious steps, and that is exactly what is addressed in Lynch’s 2010 paper.

    I can find numerous responses to Lynches earlier paper, but not to the 2010 paper.

Leave a Reply

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