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?
Suppose I have an archery tournament and award prizes according to distance shot. Do my competitors have a target?
If it is selection for it has a goal. You can’t select for something without selecting for something.
So? More word-lawyering.
You have a goal, to get far away from your present destination. If we take you literally, your goal is to get as far away as possible. If your taxi driver happens to be the founder of SpaceX you might have a better chance than if your taxi driver doesn’t even own the taxi and is low on cash to buy gas.
Now take this into Weasel world.
Say you want to get as far away from “METHINKS IT IS LIKE A WEASEL” as possible. Surely we could code a GA for this. #WeaselPhobia
Would it demonstrate the power of cumulative selection?
Who cares? How does that demonstrate the power of cumulative selection?
keiths,
Thanks. That’s helpful. I just want to make sure that ANY sort of selection procedure that accumulates in the manner you describe is thus correctly called an example of cumulative selection. There doesn’t need to be, for example several type of parallel selections going on simultaneously?
And I guess I should ask, if there IS parallel selection occurring in a single generation, is it correct to also call the results of those multiple selections cumulative? Or does the accumulation HAVE to be serial?
Dude. I do exactly that here at TSZ all the time! Would you pay to see me code a GA in which Mung outsmarts a box of rocks?
You never said i couldn’t code a GA, right? Never implied I couldn’t? Never said I was afraid to? You never said i couldn’t code a Weasel program, right? Never implied I couldn’t? Never said I was afraid to?
None of that nonsense, right?
walto,
I’m not sure what you mean by “parallel selection”. Could you give concrete examples? A scenario with parallel selection, and one without?
Haha. I have regular bowel movements. 🙂
Don’t mind keiths, who had just said prior to this that it is the iterative bit that makes it cumulative. He hopes you won’t notice.
If you get a mutation that is beneficial it might spread through the population. But then again it might not. If it does not, where is the accumulation in that?
Does Weasel ensure that “beneficial” mutations spread? Does Weasel ensure that “beneficial” mutations accumulate? What model is it using to ensure thsoe two elements?
And so Mung loses to the box of rocks.
At least he has regular bowel movements, which is something the box of rocks can’t claim.
Go Mung!
Mung,
Depends on your definition of “as far away as possible”.
If you’re talking about a phrase that mismatches at every character position, then it wouldn’t be a very convincing demonstration of the power of cumulative selection. A completely random phrase has a better than one third chance of meeting that criterion, no selection needed. With a population of 10, initialized randomly, you’d have a better than 98% chance of finding a “winning” phrase in the very first generation.
Given what you have said, I don’t know that when I run your Weasel program without selection that I am running it without cumulative selection. How would I know that? How could I test your claim?
So if it converges on the target within seconds that is how we demonstrate the power of cumulative selection? So the measure of cumulative selection is in seconds?
How did you determine that it was spinning its wheels indefinitely? How many seconds must past to establish indefiniteness?
You do understand, don’t you, that my single-step Weasel could actually find the target. We cannot predict in advance how many attempts it would take. Is that what you mean by indefinite?
If you can’t define a precise number of seconds it takes your program to find the target, isn’t your program indefinite?
You can’t possibly know that a box of rocks does not have regular bowel movements.
Have you observed every single box of rocks?
Have you observed every single box of rocks long enough to conclusively establish that they do not have a regular bowel movement?
If you claim to know what a box of rocks can claim and what a box of rocks cannot claim I think it follows you must be a box of rocks.
Talk to petrushka. He is the one playing evil definitional word-lawyering games.
So really, all that’s needed to “demonstrate the power of cumulative selection” is a hill climbing algorithm?
global peak = target
local peak = target
Need something to drive the genotypes toward higher peaks. All we need now is guided evolution!
Then stop.
Sadly absent is how we can know that this demonstrates the power of cumulative selection. If keiths turns off selection, then cumulative selection is turned off. Trust keiths!
I want a measure. A test. A way to verify. You know, science.
How do I know he has turned off selection? What measure do I have to tell me that selection is on or off? I should take his word for it?
Really, people, this is not that hard.
Re-read walto’s comments and you should understand.
Is Dawkins the authority on cumulative selection?
All hail Dawkins!
walto, if it is not possible to demonstrate the power of cumulative selection it is not possible that you exist. But you exist. Therefore it is it is possible to demonstrate the power of cumulative selection.
Yup. Targets. That’s what you need if you need to demonstrate the power of cumulative selection.
Mung,
It certainly has you stumped.
Try to imagine what an intelligent, competent person would do to determine whether ENABLE_SELECTION — a parameter in my code — does what the name implies.
How could cumulative selection fail to succeed?
How is this possibility that cumulative selection fails to succeed incorporated into the Weasel algorithm?
Brain dead fitness landscapes? No wonder atheism favors the brain dead.
May I offer an alternative?
DISABLES_CUMULATIVE_SELECTION
But how would anyone know. We have no way of testing your claims.
Mung,
Speak for yourself. You aren’t bright enough to figure it out, but that doesn’t mean that everyone else isn’t.
People who actually understand this stuff can see not only that cumulative selection is powerful, as Weasel and other programs demonstrate — they can also see why it works.
The fact that one particular internet dipshit doesn’t get it is not a cause for concern. Stupid people gonna be stupid.
Mung,
Who’s ‘we’? phoodoo and you?
Maybe what I said makes no sense, but I was thinking about several qualities being “fitness enhancing” (if that’s a term), like say, speed, strength, and fecundity or attractiveness. As survival chances are improved by all of those at once, I was wondering if cumulative selection can be said to take place in a single generation.
it works except when it doesn’t then it fails. That goes for cumulative selection just as it goes for the Aether.
It’s all science, you would not understand
peace
Fail to succeed would imply that the selection process fails to adapt the “organism” and it therefore goes extinct. Or with a target-weasel, fails to reach the target in the alloted time, or just never reaches it regardless of how much time it is given.
At an abstract level applicable to (I think) all instances of cumulative selection, the mutation rate might be too high or too low, or the number of permutations at individual sites might be too great(as in the alphabet has too many possibilities), or the fitness increase associated with a beneficial mutation might be too low to beat drift.
Those are just some quick ones I could come up with on the spot.
Length of sequence plus mutation rate vs time.
I think we should make up a list of what would be needed to satisfy Mung. Here are some things we mught need:
A. A formal definition of “cumulative selection”
B. A formal definition of effectiveness
C. A formal specification of a Weasel.
D. Formal testing of all existing Weasels including logical proof of correctness of those prograns.
E. Empirical validation of all models as correct descriptions of reality.
I’m sure I’ve left a few things out here — maybe a formal definition of reality? A formal definition of life?
That’s obviously too much. But let me ask you, Joe. If you were a doubter yourself, what would YOU require of those creating simulations of cumulative selection? I don’t know if mung would be satisfied with your criteria, but I probably would.
For my own part, if I’m looking for a demonstration of how cumulative selection works , what I would want is a definition of cumulative selection, and a demonstration that meets that definition. Both of these have been provided.
You can then pose questions such as “how would it work without a target?” And then one can explain that and make a new demonstration that does not have a target.
I really don’t get why this thread is still beating this dead horse. Cumulative selection works with and without targets, it is much much more efficient than junkyard tornadoes. What else is there to keep arguing about?
Thanks, OMagain. That was both interesting and instructive.
Rumraket,
Nothing. This is just a face-saving exercise on Mung’s part.
This thread was yet another failed attack on Weasel. Mung thinks his retreat will be less ignominious if he can say something like “Yeah, but they couldn’t tell me what the units of cumulative selection are”, as if that mattered.
I would ask mung to operationalize his doubts. Let him provide operational definitions of the terms.
From another thread:
In what sense does the GA posted in the OP of this thread not work?
Let me ask you something, keiths.
Say I stuck a line in my code, as shown in the OP:
ENABLE_SELECTION
And someone can then set it to TRUE or FALSE:
ENABLE_SELECTION = TRUE
or
ENABLE_SELECTION = FALSE
And ENABLE_SELECTION = TRUE causes the program in the OP to run just as it does currently, where selection is single-step selection.
Do you now see why you aren’t really addressing the question? Not all selection brings about CUMULATIVE_SELECTION.
Or do you think Dawkins just messed up when he called it single step selection, you know, because there is no actual selection going on?
Are you a trained and licensed mind-reader?
If you have no way to quantify cumulative selection just say say.
If you have no way to measure cumulative selection just say say.
Is the power of cumulative selection like the power of the Holy Spirit? If you see it, you know it, if you’re bright enough?
Yes, Joe, the Weasel program is supposed to demonstrate the power of cumulative selection. So we would want to know what cumulative selection is and how to quantify its power. You know, do actual science!
Of course, Dawkins might have been on a rhetorical kick. Preaching to the converted and all that.
Such as?
You want me to provide an operational definition of cumulative selection, something which Dawkins himself did not do?
keiths claims to have demonstrated the power of cumulative selection through a program he wrote. Did he give an operational definition of cumulative selection? So you want me to do what both Dawkins and keiths have failed to do?
Patrick wrote a Weasel program too. Do you think it demonstrates the power of cumulative selection? What was his operational definition? So you want me to do what Dawkins and keiths and Patrick have failed to do?
Will I win a prize?
Has anyone explained why TSP does not have targets?
It depends on what you mean by a target. A genetic algorithm trying to find short solutions to a TSP of course has some function that computes the length of any proposed route.
But it does not have within it a list of those routes that are desired. The information specifying in detail which are the better routes is not found in advance and stored in the program. This latter information is what I mean by the “target”.
If you want to call the shortness of the length of the route a “target” then go ahead, it’s a free country, but that is not what most TSZ commenters mean by “target”.
Why not? It sure sounds like a target to me. Is there some aversion to the idea of targets by “TSZ commenters”.
Is it possibly because target implies intention and intention implies design?
peace
There is no knowable shortest trip, so no way to have a halting condition.
And no good alternative way to know the shortest rout.
There may be a computable lower limit to trip length, but no practical way to find A trip that gives you this shortest possible trip. In commercial applications you run the program for the available time.
Exactly. Why this eludes so many people confuses me.
Bingo.
Why should one not use it that way? Perfectly good usage, IMO.
As Joe F. explained, there are targets and there are targets. You are free to use the term any (reasonably clear) way you like. What you may not do is take someone’s clear usage to mean something it does not mean.
fmm,
No, it’s precisely because of people like you with agendas. Who take words used in one sense and say ‘ah, it implies intention and intention implies design’ as if that’s meaningful.
If your only victories are Mung-eqsue word lawyering victories, then all the more sad for you.
It’s also a favourite tactic of Sal Cordova, to claim that some research is ‘unwitting’ support for ID. If length of a solution to the TSP is a target, and ‘targets’ imply intention then by jove you’ve hit upon proof of god!
Or not. But carry on. I realize it’s beyond you to understand what’s going on here and the fact that language is complex. But, tee-hee, targets require intention and they used the word target. Giggle Giggle.
One can Humpty Dumpty this, but in a weasel program, a target implies a halting condition. When the value X is computed, the program stops.
Word lawyering is trolling.
There is no value expected in TSP that says the program is done and has computed the answer.
TSP programmers compete with maps of ten thousand stops. There is no known way to compute the best route, only increasingly better routes.
I could be wrong about this, but I believe there is a way to compute the minimum possible value, in which case you could halt when some arbitrary percentage of this value is reached.
Mung could have — if inclined to engage in constructive dialog — asserted that this is a target.
But that kind of target is a requirement of a specific kind of competition. It is not necessary for the program to run. Lenski’s cultures continue to evolve without targets.
But to answer your question, no, it’s not because target implies intention and intention implies design.
Why? Well, we can see that clearly.
For each possible solution to a given TSP each ‘target’ is simply the length of the solution. Therefore there is a lower bound (the shortest solution) and an upper bound (the longest solutions).
Therefore the ‘target’ is simply any one of any of the possible solutions to a given TSP. Nothing differentiates them apart from their length. To call these ‘targets’ is like saying multiplication implies intention and intention implies design. We know that 2*2 will result in some number, and it will be a number. Are all the integers targets therefore?
So if all possible solutions are also targets what does it actually add to say that ‘target’ implies intention and intention implies design? There is nothing special or different about any particular ‘target’. If they are all targets, then target is the wrong word, as you are not picking out any specific target from the others. Unless you start to compare them by length.
But, oh, wait, only designers can compare things by length! Yes, by jove, you’ve done it again! Proven ID/your particular god because target implies intention and intention implies design.
Nice Beavis and Mung-head reference.
As part of writing a GA to solve the TSP you must have a way to generate the initial solutions. Simply running the program without the selection aspect allows solutions to evolve without regard to any particular target length. A TSP solver does not need a ‘target’ to generate solutions, but if you give it one it will certainly move towards that ‘target’. And here target is something like ‘better solutions are shorter’.
fmm,
Bees solve the TSP in their everyday life.
http://www.qmul.ac.uk/media/news/items/se/38864.html
Do bees have intention?