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
- Have I successfully coded a genetic algorithm?
-
Is this a version of the Weasel program?
-
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?
Read it again, Mung.
And this:
Your ass has been kicked and rekicked by Weasel. Another anti-Weasel thread of yours has ended in failure. When will you learn?
What essential characteristic is that?
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.
Do we agree that Dawkins’ Weasel demonstrates the power of cumulative selection?
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.
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.
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?
It demonstrates cumulative selection, by Dawkins’ definition.
Now please answer the question. What essential characteristic of cumulative selection does Dawkins’ definition not include?
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.
The power.
So does my program, by Dawkins’ definition.
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?
So? The Dawkins Weasel program says nothing about biological evolution.
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
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.
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.
The only thing left is for Mung to admit defeat — a defeat that is glaringly obvious to those of us who understand this stuff.
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?
No, I answered it directly.
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.
Mung seems to be trying to word lawyer “cumulative selection”, to what end I have no idea.
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.
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.
You didn’t correct him. That’s almost exactly what he wrote:
Apologies. I often post a comment, and then reread it and then edit it to correct misspellings, misspeakings, and misthinkings.
No worries, I’m glad we ended up agreeing.
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.
Patrick,
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.
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).