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?
fitness == 28 ? fitness : 0It must be an exact match to the target (fitness = 28), else it is assigned a fitness of 0.
The proximity to the target must be exact.
Thus we have a target and a fitness function that rewards proximity to the target.
Therefore, this is an example of cumulative selection.
Shouldn’t it be assigned a fitness between 1 and 0, depending on the degree of match to the target sequence? Those closer the match, the closer to 1?
Well, keiths says an exact match doesn’t count, only proximity defined as excluding an exact match counts, but that seems wrong. If we disallow exact matches we’ll never hit the target!
Here we reward proximity including an exact match:
fitness > 0 ? 1 : 0
Does this perform any better than single-step selection?
Not according to keiths:
// Calculate a genome's fitness by determining the number of loci at which
// it matches the target.
int fitness(genome_t *genome) {
int matches = 0;
// scan the entire genome, counting the number of loci that match the target
for (int i=0; i < GENOME_LEN; i++) {
if (genome->locus[i] == target.locus[i]) ++matches;
}
return matches;
}
It it matches exactly it gets a fitness of 28, just like in my code.
Ahh okay, I just thought fitness was between 1 and 0, but you’re making the maximum fitness the number of characters in the target string.
In that case, a string that differs by 1 letter would have a fitness of 27, and if it differs by 2 letters 26 and so on.
I just wanted to make sure I that even if it does not match the target sequence completely, it is still assigned a fitness over 0 that correlates with how well it matches the target sequence.
I don’t understand coding very well. Does your program have pr site mutation rate and if so, what do you set it at?
I struggle with the language also, but i interpret the mutation rate to be two percent.
Okay, that’s fine for a program like that I think. You could probably even up it to something like 4 or 5% to speed things up a little and there’d still be some chance it’d perfectly match the target sequence.
It seems to be sorting the population and generating a new population by duplicating the member having the most matches to the target. I can’t tell if the code actually works, but that seem to be the intended behavior.
As I say, I’ve never programmed in this language and have no manual for it, but it seems to be equivalent to the Dawkins weasel.
generate a population of strings using randomly selected characters from a defined character set
for each string, apply a mutation (or not, based on the mutation rate) to each character. If the mutation is applied, change the character to a randomly generated character from the character set
3 find the string from the population of strings that has the most matches to the target string
4 replicate the population starting from the string having the most matches
5 iterate until the number of matches equals the number of characters in the target.
That’s a pretty crude definition. I’ve never written specs for a living.
Close. rand(100) will produce a number 0 – 99. So 1%.
Yes, the map method iterates over each member in the collection. and .01.
I am actually using arrays of 28 slots with one character in each slot. I convert the array to a string to display it.
Following keiths:
// A genome consists of an array of loci …
I learned to program in C. A string is just a character array. I’ve always thought of strings as character arrays.
All the professional coding I’ve done required me to step thought strings one character at a time, or accept input one character at a time. I guess that’s why I have trouble understanding buffer overflow errors. It never occurs to me that anyone would write code that didn’t allocate memory for a string and check to make sure input wasn’t exceeding the allocated array size.
Of course it works. 😉
As with the keiths Weasel, it has one survivor that is used to seed the next generation.
// number of survivors per generation…
#define NUM_SURVIVORS 1
Is it capable of finding the target? If you fine tune the fitness function. Sure. We can give the genome with the most matches the highest fitness score and then that genome will seed the next generation:
def fitness_function candidate
fitness = 0
candidate.each_index do |idx|
fitness += 1 if candidate[idx] == TARGET_PHRASE[idx]
end
fitness
end
217:MKTHINKS IT IS LIKE A WEASEL
218:MKTHINKS IT IS LIKE A WEASEL
219:MKTHINKS IT IS LIKE A WEASEL
220:MKTHINKS IT IS LIKE A WEASEL
221:MKTHINKS IT IS LIKE A WEASEL
222:MKTHINKS IT IS LIKE A WEASEL
223:MKTHINKS IT IS LIKE A WEASEL
224:MKTHINKS IT IS LIKE A WEASEL
225:MKTHINKS IT IS LIKE A WEASEL
226:METHINKS IT IS LIKE A WEASEL
It’s a Weasel!
Not something you have to worry about in Ruby.
D:\projects\weasel>irb
irb(main):001:0> an_array = []
=> []
irb(main):002:0> 5000.times {an_array.push(1)}
=> 5000
irb(main):003:0> an_array.size
=> 5000
irb(main):004:0> exit
D:\projects\weasel>
Given how simple it is to code a GA / Weasel program people must be absolutely flabbergasted at my inability to do so before now.
😀
Weasel patching
With Ruby you can do things like this:
class Array
alias_method :each_locus, :each_index
end
def fitness_function candidate
fitness = 0
candidate.each_locus do |locus|
fitness += 1 if candidate[locus] == TARGET_PHRASE[locus]
end
fitness
end
I’m only flabbergasted at the questions you asked about it. Particularly questions about latching.
We probably have a different definition of latching.
I can’t test your program, and I don’t know the language.
So here are my questions and queries.
What did you intend the program to do? Can you write out the specs in the same way I did, possibly phrased better or more accurately?
What does the program do when running?
How would you test it to ensure it does what you intended?
These are the kinds of questions you asked some time ago, so I assume they apply to your program as well as ours.
What do you think about cumulative selection? Does the program progress, producing strings that are progressively closer to the target?
Is there any conceptual problem with replacing a static target with a moving target?
Is there any conceptual problem with replacing a single static target with a function that simply returns a relative value?
You forgot: Is the SS Weasel a ship in the 3rd Reich atlantic fleet?
Sry, couldn’t resist.
🙂
petrushka, Ruby has to be one of the easiest languages of all time to install and learn. If you are interested I can help you out.
Over in the Cumulative Selection Explained! thread walto asked a question about single-step selection and cumulative selection.
So I set out to give us a starting point. A version of Weasel implemented using single-step selection which incorporates the following:
.
I thought walto asked a reasonable question that deserves to be answered. I think my program has entities that “reproduce” and “the results of one sieving process are fed into a subsequent sieving…” and “The end-product of one generation of selection is the starting point for the next generation of selection, and so on for many generations.”
According to Dawkins himself that’s cumulative selection.
By the way, notice that Dawkins description says nothing about targets or proximity to targets, contra keiths.
Mung,
Where “fine tuning the fitness function” means “taking out the idiotic Mung part”.
Mung:
Dawkins:
Mung fail.
What a waste of time you are, Mung.
What’s the score? On you vs keiths? I assume you are keeping track.
It just keeps on running and running and running. We’re talking about my single-step selection version right?
What do you think about cumulative selection?
From what I’ve seen so far, the concept is purely subjective. It lacks quantification and is thus untestable.
Does the program progress, producing strings that are progressively closer to the target?
No idea. It might. Is that what is required for cumulative selection? I can tell you one thing, it doesn’t latch. And keiths says a target isn’t needed [when he isn’t saying a target is required].
These are the kinds of questions you asked some time ago, so I assume they apply to your program as well as ours.
And I thought you weren’t paying attention.
How would you test it to ensure it does what you intended?
It depends.
Is there any conceptual problem with replacing a static target with a moving target?
No. Does that help or hinder when trying to demonstrate the power of cumulative selection? Perhaps a moving target Weasel will be next up, now that I finally have the hang of this Weasel programming.
Is there any conceptual problem with replacing a single static target with a function that simply returns a relative value?
Relative to what? I could generate a fitness value randomly.
Are you saying the program in the OP is not a GA that uses single-step selection?
What’s idiotic about that, that Dawkins didn’t think of it first?
Skunk v. Weasel? Sounds right to me. I’m writing a GA to decide whether to keep track so I don’t have to decide whether to keep track.
All you need do, keiths, is give honest answers to the best of your ability.
Must the program always choose the phrase which most resembles the target phrase?
a.) If not, does that disqualify it from being a version of Weasel?
b.) If not, does that disqualify it from being an example of cumulative selection?
Try not to contradict yourself.
Mung,
If you run the program 10 times, how many steps on average does it take to reach its target phrase?
Are we talking about my single-step selection Weasel as given in the OP?
It has yet to reach the target phrase on any run. How many generations ought I allow for it to find the target phrase before we reject the hypothesis of cumulative selection?
Is that the only way of deciding that cumulative selection is in operation, that it reaches the target phrase in some finite number of generations?
If we assume an infinite population size, and generate each member of the population randomly, won’t we get an infinite number of matches?
Single-step selection seems to be no barrier to evolution, nor to cumulative selection, but that probably needs further investigation. 🙂
I’ve finally posted the code for a GA, one that I wrote on my own, and keiths calls it a waste of time, lol!
From the OP:
Sheesh. So he quote-mines Dawkins instead.
Mung,
If I understand your code correctly it has no selective fitness unless the phrase is matched exactly to the target.
My understanding is that Dawkins weasel would select the closest fit to the target.
Based on numerous discussions at TSZ would reality be a sentence about 120 characters long with billions of variations that would be a possible selection?
On second thought, do you think a 28 character single target with fitness defined as an exact fit is a very conservative emulation of evolution? This seems like an easier problem then 120 characters with 100 billion possible fits. 27^120/27^11 is 81 orders of magnitude more difficult.
I guess it all depends if Szostak is right, Axe is right or they both are right based on the protein function selected?
This is true. It is single-step selection. It implements what I understand Dawkins to mean by single-step selection.
Again true. I was not attempting to mimic Dawkins.
Some time back I wrote a Binary Weasel program in which the genome consisted of a series of binary digits and the phenotype consisted of the characters derivable from those binary digits. It never did converge on the target in any way that I could see.
Mung,
Based on your program, how many trials would you need for a reasonable chance of convergence?
The Binary Weasel program?
Assume a Unicode character set of 16 bits per character.
ASCII ‘A’ through ‘Z’ plus SPACE is 27 of H’FFFF. 27/65536.
You’re probably better at the math than I am. If we have 28 positions with .01 chance of mutation, and if mutated a 27/65536 chance of even being a selectable character, what must the size of my population be in order to even give “cumulative selection” a fighting chance?
http://iwanttolearnruby.com/
Has anyone claimed that a weasel-like program will demonstrate the power of cumulative selection with every possible fitness function?
Here’s what I said on that:
Mung has set up a fitness(-proxy) function that does not have this smoothness property. Then Mung considers that Mung’s program does not demonstrate the power of cumulative selection.
Where does Mung get the idea that it should, with every possible fitness function? Mung’s function is a needle-in-a-haystack fitness. Long known to be a particulary bad case.
Joe, do you understand the concept of single-step selection?
colewd,
Mung foolishly believes that if he can concoct a scenario in which cumulative selection fails to converge on the target in a reasonable amount of time, then he has somehow weakened the case that Weasel’s success demonstrates the power of cumulative selection.
Hence his desire to use inane fitness functions such as the one you pointed out:
Another fitness function he mentions is one in which every phrase has a fitness of one, except for those that mismatch the target at every location, which have a fitness of zero.
What is the point of these asinine fitness functions? Well, Mung is engaged in abject definition lawyering, hoping that he can find some scheme that technically qualifies as “cumulative selection” but nevertheless fails to locate the target in a reasonable time. In this case he is trying to find a fitness function that satisfies the criterion “rewards proximity to the target” while still causing the program to fail.
What he is too dim to realize is that his entire project is predicated on a simple logic error. No one has claimed that cumulative selection always succeeds. So even if schemes using those idiotic fitness functions actually did qualify as “cumulative selection”, their failure to find the target wouldn’t show what Mung wants it to show.
If were smarter, he would have realized that you don’t need to concoct Mungish fitness functions in order to cause cumulative selection to fail. You can do it via much simpler interventions, like setting the mutation rate to an extremely small value.
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.*
It’s gotta sting. The list of Mung’s Weasel-related failures just keeps growing, and all the while he hasn’t been able to inflict as much as a scratch on Weasel itself.
*ETA: I see that Joe makes the same point here:
It is not a phrase in use in population genetics or quantitative genetics. I see that Dawkins used it:
So the case you used in your program was the one which Dawkins said was not illustrating cumulative selection. And I guess you’re showing him right about that.
This is golden.
Why is it not immediately obvious to everyone, that if you only and exclusively reward increased fitness to the string if it matches the target phrase by 100%, then obviously it will not climb towards it and can ONLY hit the target by blind luck?
Was that really something that needed to be tested?
Isn’t it obvious then, that there is no cumulative selection going on?
Amazing.
Or extremely high. With a 28 letter phrase, and a pr letter mutation rate of 15%, it would pretty much always mutate too much to ever reach the target phrase.
These aren’t things that need to be “tested” so they can shatter our minds. We can work this out in our heads from the basics, the results are not surprising.
Obviously if you’re selecting towards the same phrase with a smooth hill to climb, the chance of convergence is one hundred percent. Interestingly, this is why convergence happens in nature. You’ll note how both fish and dolphins have that typical hydrodynamic torpedo-like shape with a pointy nose and long slim body. That’s an example of convergence and there’s a perfectly good, sensible explanation for it through natural selection.
I think you wanted to ask a different question that had something to do with convergence and the inference of common descent. Right? In other words what you thought you were showing with that question has nothing to do with Mung’s program or WEASEL-like programs demonstrating how cumulative selection works in general.
Rumraket,
Depends on what you mean by cumulative … !
There’s an odd use of ‘proximity’ there too. You are only in proximity to the target if you are sitting on it … ! Not sure why the phrase is evaluated bytewise if the fitness is then either 28 or nothing.
I think Mung could usefully set this program running with no iteration count and give it 100% of CPU, ideally on the same computer as used to post here.
I’d be interested in the results of that experiment.
I’ve worked with people in the past who were a net loss to productivity. In these internet discussions those sorts of people seem more common.
It does seem that a great deal of effort has been expended exploring questions that no one is interested in.
Back when everyone was discussing keiths implementation, tom English pointed out the behavior of these programs could be described by a simple bit of algebra.