SS Weasel

I’ve written a genetic algorithm, which I have posted below, which implements single-step selection.

The relevant line for single-step selection is line 38:

fitness == 28 ? fitness : 0

  1. Have I successfully coded a genetic algorithm?

  2. Is this a version of the Weasel program?

  3. Does it demonstrate the power of cumulative selection?


#!/usr/bin/env ruby -w

#
# step_weasel.rb
#
# A simple GA in Ruby using single-step selection
#

TARGET_PHRASE = "METHINKS IT IS LIKE A WEASEL".chars
TARGET_LENGTH = TARGET_PHRASE.length

CHAR_SET = [' '] + ('A'..'Z').to_a

POPULATION_SIZE = 100
LENGTH_OF_RUN = 14_444

class WeaselFactory
  def self.create
    Array.new(TARGET_LENGTH).map {CHAR_SET.sample}
  end
end

def mutation_operator candidate
  candidate.map! do |locus|
    if rand(100) > 98
      CHAR_SET.sample
    else
      locus
    end
  end
end

def fitness_function candidate
  fitness = 0
  candidate.each_index do |idx|
    fitness += 1 if candidate[idx] == TARGET_PHRASE[idx]
  end
  fitness == 28 ? fitness : 0
end

def genetic_algorithm
  population = Array.new(POPULATION_SIZE).map {WeaselFactory.create}
  generation = 0
  most_fit_member = []

  while most_fit_member != TARGET_PHRASE
    temp_pop = population.map {|weasel| mutation_operator(weasel).dup}
    most_fit_member = temp_pop.sort_by {|weasel| fitness_function(weasel)}.last
    population = temp_pop.map {most_fit_member.dup}

    puts "#{generation}:" + most_fit_member.join
    generation += 1
    if generation == LENGTH_OF_RUN
      puts "Failed to Weasel"
      exit
    end
  end
end
genetic_algorithm
puts "It's a Weasel!"

I say I have coded both a Weasel and a GA. Now there’s no longer any need for keiths to quote-mine my comments.

Given this is a GA that implements single-step selection, we ought to now have a baseline for comparison against a GA that demonstrates the power of cumulative selection, but how would that work?

277 thoughts on “SS Weasel

  1. Read it again, Mung.

    And this:

    The problem (for Mung) is stark and obvious: the fact that cumulative selection can fail in some cases does not mean that it fails in all, and it doesn’t mean that Weasel fails to demonstrate the power of cumulative selection.

    Your ass has been kicked and rekicked by Weasel. Another anti-Weasel thread of yours has ended in failure. When will you learn?

  2. Mung:

    You can step through the vast majority of EAs, including Weasel and its variants, generation by generation and determine that each successive generation builds upon the previous one, with changes driven by selection pressures. That meets Dawkins’ definition of cumulative selection.

    Do you disagree?

    Yes, I disagree. The “definition” you cite fails to capture an essential characteristic of cumulative selection.

    What essential characteristic is that?

  3. keiths:
    Your “SS Weasel” doesn’t demonstrate the power of cumulative selection. Weasel does.

    By Dawkins’ definition, Mung’s latching weasel demonstrates cumulative selection. His needle-in-a-haystack version does not, because the fitness function he uses there does not allow selection to operate.

  4. keiths: When will you learn?

    I’ll learn when you present objective empirical evidence.

    1. When you tell us how to quantify “the power of cumulative selection.”

    2. When you tell us how to measure “the power of cumulative selection.”

    3. When you show us how to write a test to detect “the power of cumulative selection” in software programs where you claim “the power of cumulative selection” is operating.

    I’d really like to understand why one program demonstrates the power of cumulative selection while another program does not, and be able to compare two programs according to how much “power of cumulative selection” they demonstrate.

    If you can’t produce, I’ll understand.

  5. Patrick: In cumulative slelection, on the other hand, they ‘reproduce’; or in some other way the results of one sieving process are fed into a subsequent sieving, which is fed into into . . . and so on. The entities are subjected to selection or sorting over many ‘generations’ in succession

    Is it your claim, Patrick, that in my SS Weasel, the entities do not ‘reproduce’?

    Is it your claim that my SS Weasel contains no sieving process?

    Is it your claim, Patrick, that in my SS Weasel, the entities are not “fed into a subsequent sieving, which is fed into into . . . and so on.”?

    Because I think my SS Weasel does all those.

    Or is it your claim that my SS Weasel has no sorting or sieving process at all? Because I think it clearly does.

  6. keiths: Christ, Mung.

    Your “SS Weasel” doesn’t demonstrate the power of cumulative selection. Weasel does.

    That doesn’t even begin to address the question I asked you.

    Here’s the question again, again: Does my SS Weasel program NOT start each generation from the results of the previous one? It does. So why not just admit it?

  7. Mung: Do we agree that Dawkins’ Weasel demonstrates the power of cumulative selection?

    It demonstrates cumulative selection, by Dawkins’ definition.

    Now please answer the question. What essential characteristic of cumulative selection does Dawkins’ definition not include?

  8. Mung: Is it your claim, Patrick, that in my SS Weasel, the entities do not ‘reproduce’?

    As I made very clear, the problem with your needle-in-a-haystack implementation is that selection cannot operate on the fitness landscape you’ve defined.

    That says nothing about biological evolution.

  9. Patrick: Now please answer the question. What essential characteristic of cumulative selection does Dawkins’ definition not include?

    The power.

    It demonstrates cumulative selection, by Dawkins’ definition.

    So does my program, by Dawkins’ definition.

  10. Patrick: As I made very clear, the problem with your needle-in-a-haystack implementation is that selection cannot operate on the fitness landscape you’ve defined.

    So what? You’re avoiding the questions.

    Are you claiming that in order to “demonstrate the power of cumulative selection” a program must implement a specific fitness landscape? Because if that is your claim I fail to see how it differs from my claim.

    What must such a landscape look like and how can we test whether a program implements such a landscape?

  11. The Weasel, as a teaching example, is quite sufficient to demonstrate that when creationist debaters claim that evolutionary biologists argue that change is “at random”, that they are massively misleading their audiences.

    It’s very effective at demonstrating that, since it easily is seen that the Weasel reaches its target phrase enormously faster that just making random guesses, faster by a factor of 10^{36} or so.

    I believe that Mung has acknowledged this, and said that it was never at issue between Mung and his opponents here. So Mung agrees with Dawkins that the creationist debaters are perpetuating a falsehood.

    That’s enough for me.

    Exactly what the fitnesses in a Weasel-like model of, say, Wright-Fisher sort, have to be to have that Weasel-like program get to the target much faster than random guesses is an interesting technical question, but does not have to be solved to show that cumulative selection is not equivalent to random guessing.

  12. Yeah I don’t get why this thread is still going either. It seems the central question has been addressed at length and what is left is just digressions and mindless quibbling about details.

  13. The only thing left is for Mung to admit defeat — a defeat that is glaringly obvious to those of us who understand this stuff.

  14. Mung:

    Now please answer the question. What essential characteristic of cumulative selection does Dawkins’ definition not include?

    The power.

    What are you on about? Dawkins’ definition allows an observer to determine if cumulative selection is taking place or not. What more do you want?

  15. Mung:

    As I made very clear, the problem with your needle-in-a-haystack implementation is that selection cannot operate on the fitness landscape you’ve defined.

    So what? You’re avoiding the questions.

    No, I answered it directly.

    Are you claiming that in order to “demonstrate the power of cumulative selection” a program must implement a specific fitness landscape? Because if that is your claim I fail to see how it differs from my claim.

    What must such a landscape look like and how can we test whether a program implements such a landscape?

    In order to demonstrate cumulative selection, by Dawkins’ quite reasonable definition, each generation must build on the changes induced by selection on the previous generation. Your needle-in-a-haystack fitness landscape does not allow for any selection pressure to occur. No selection, no cumulative selection.

    Evolution does not work in all possible fitness landscapes. No one disputes that. Deliberately constructing a fitness landscape in which it doesn’t work says nothing about those in which it does.

  16. Rumraket:
    Yeah I don’t get why this thread is still going either. It seems the central question has been addressed at length and what is left is just digressions and mindless quibbling about details.

    Mung seems to be trying to word lawyer “cumulative selection”, to what end I have no idea.

  17. As I’ve said here before Mung’s mutate-one-position-a-a-time program is a Weasel program, as far as I can see. It does not have a needle-in-a-haystack “fitness” function, because when a position matches the target, it rewards that . (Others here may disagree, and have their own definition of what constitutes a Weasel).

    The version (SS Weasel) that implements the single-step fitness function is not a Weasel, as far as I can see, because it does not reward any intermediate steps toward the target

    Mung’s program, with its somewhat weird one-position-at-a-time mutation scheme, does demonstrate the power of cumulative selection. In fact, it ought to get to the target a little faster than most Weasels.

    All of the non-single-step Weasels demonstrate the power of cumulative selection, all reach the target enormously faster than a program would that would not favor a phrase unless it matched the target perfectly at all positions. All show that the creationist debaters who say that evolution “is random” are either deliberately misleading their audience, or else they mislead their audience because they are massively ignorant about evolution.

  18. Joe Felsenstein:
    As I’ve said here before Mung’s “SS Weasel” is a Weasel program, as far as I can see.It does not have a needle-in-a-haystack “fitness” function, because when a position matches the target, it rewards that .

    I think that’s a correct description of his previous Weasel variant. The SS Weasel listed above does, however, use a needle-in-a-haystack fitness function. This line:

    fitness == 28 ? fitness : 0

    shows that all partial matches have the same fitness as a completely incorrect string. Only a perfect match is rewarded.

    (Yes, I read the code several times before daring to correct Dr. Felsenstein.)

    ETA: It looks like Joe edited his comment after I responded. Nevermind.

  19. Patrick:

    The SS Weasel listed above does, however, use a needle-in-a-haystack fitness function. This line:

    fitness == 28 ? fitness : 0

    shows that all partial matches have the same fitness as a completely incorrect string. Only a perfect match is rewarded.

    (Yes, I read the code several times before daring to correct Dr. Felsenstein.)

    You didn’t correct him. That’s almost exactly what he wrote:

    The version (SS Weasel) that implements the single-step fitness function is not a Weasel, as far as I can see, because it does not reward any intermediate steps toward the target

  20. As long as we’re here, let me quibble a bit about terminology. In a model of an evolving population with discrete generations, the “fitness” is a quantity which is proportional to the contribution a newborn individual is expected to make to the newborns of the next generation. (There is relative fitness and absolute fitness — the above statement covers both of these).

    But if you have a quantity that is calculated for each newborn individual, and (let’s say) the probability of surviving an reproducing increases with it, but is not proportional to it, then we should not call it a “fitness”. In the genetic algorithms / evolutionary computation literature it is common to call such things “fitness”. So if you take these quantities and choose as survivors the individuals with highest values of the quantity, then the GA / EC people call that a fitness, but evolutionary biologists would never call those fitnesses. To me, being in the latter group, they should at best be thought of as fitness proxies.

    So when a Weasel computes a number of matches to the target, then picks the offspring that has the highest such number as the survivor, that number is not, strictly speaking, population-genetically thinking, a fitness. But it is a fitness-proxy.

  21. Patrick,

    Mung seems to be trying to word lawyer “cumulative selection”, to what end I have no idea.

    It appears to be a simple logic fail.

    Mung seems to think that if he can come up with a brain-dead program that a) qualifies as an example of cumulative selection while b) performing poorly at locating the target phrase, then he has shown that Weasel succeeds for reasons other than “power of cumulative selection”.

    Poor guy. His perennial nemesis, the Weasel, has bested him again.

  22. keiths,

    Remember the old “pick a number between 1 and X” game where you have N tries to guess correctly guided by “higher” or “lower”? There are multiple methods to set that up and they don’t all perform the same. I think the optimum strategy is always to pick the middle value of the remaining space not yet ruled out. You could of course just keep guessing. I don’t think that would count as “cumulative selection”, though.

  23. Richardthughes:
    keiths,

    Remember the old “pick a number between 1 and X” game where you have N tries to guess correctly guided by “higher” or “lower”? There are multiple methods to set that up and they don’t all perform the same. I think the optimum strategy is always to pick the middle value of the remaining space not yet ruled out. You could of course just keep guessing. I don’t think that would count as “cumulative selection”, though.

    They are related. The binary search method progressively restricts the area of the search space where the target is located. Cumulative selection moves into regions closer and closer to it. If it goes always uphill on a fitness surface it restricts the search to smaller and smaller sets, ones with fitness higher than the current position and adjacent to it. (Of course, unlike binary search, it can arrive at a local peak rather than the global peak).

Leave a Reply