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?
I take it that Mung is attempting a reductio here. So one question is whether you have the same disdain for Dawkins’ CPU.
He keeps asking people to tell him precisely what they’d want for a test, and what success or failure would look like. Can you do that? That seems to me the ensible way of shutting him up–if that’s the goal.
That is incorrect. I’ve clearly stated that I think the Dawkins Weasel program demonstrates the power of cumulative selection.
keiths, please consider that misleading others is not conducive to the goals of this site, even if it’s done deliberately.
Is it your position that the fitness function in the OP fails to implement single-step selection or is it your position that a fitness function that implements single-step selection is inane?
I’ve had two runs going for many hours now which do exactly that. 🙂
I’m not a mind reader. If it’s not enough that the fitness function reward proximity then you should say so and we could skip over all the inanity.
Again, this is incorrect.
The target may be constantly changing. The GA may never reach the target. neither of these mean that cumulative selection is not in operation. Pause and read that again, please.
You are not following along and it seems to be leading you to misrepresent my argument to others. Please stop.
Of course, that brings up a question which I asked you in the past. Your answer was?
I know, right!?
I agree!
Obvious in a subjective psychological sense? Absolutely.
Can “the power of cumulative selection” be demonstrated in an objective scientific way, or is it a matter for faith?
LMAO. Good one!
Is that all that’s required to demonstrate the power of cumulative selection? A simple hill-climbing algorithm?
Wouldn’t it be amazing if nature consisted of smooth hills with targets at the top and a function to direct the genomes of living organisms to the tops of those hills?
Yes, yes it is.
Has it taken you this long to realize?
I would call it obvious in an objective, logical sense. But then I guess I’m making certain assumptions about the intelligence of my interlocutor.
I do concede it is entirely possible it is not obvious to you.
Yes it can.
No, it is not. I would reject any principle that requires faith.
What would be really amazing is if you could demonstrate that people like Larry Moran or Jerry Coyne or even Dawkins have ever suggested that nature has smooth, easy to climb hills.
Cool. My suspicion is that they get somewhat towards the target phrase but can’t get past it because already discovered matching letters simply mutate again.
but elsewhere,
Mung, meet Mung. Maybe Mung can persuade Mung.
Precisely.
We have the Dawkins Weasel program which is designed to produce the result it does. It would probably fail to find the target phrase in far more scenarios than those in which it successfully finds the target phrase. Assume for the sake of argument that cumulative selection is still in operation in those scenarios. How would we know?
Or should we just declare that it is so and go home.
Also, I’ve coded a GA, I’ve coded a Weasel program, I’ve posted my code, and now people can finally shut up about that and perhaps focus on more interesting matters.
How close would they need to get for us to be reasonably sure that cumulative selection is in operation?
ETA: You keep feeding into the meme that a target is required.
…Or Bernie Madoff, or OJ Simpson, or Richard Nixon..
keiths:
Mung, now:
Mung, then:
Yes, keiths, anyone can quote-mine. Some are better at it than others.
Mung then:
Mung then:
Obviously those statements make no sense if Weasel does not demonstrate the power of cumulative selection.
So keiths is not following along, again, and that just isn’t my fault.
Keep it up, keiths, and I will put you on ignore. There is absolutely no reason for me to continue to read anything you write if I can’t believe you are posting in good faith.
More word lawyering from Mung.
“Oh, I’m not questioning the power of cumulative selection. All I’m saying is that perhaps the power of cumulative selection is just an artifact of the design of the program. Humans think they see something that’s not really there. Like the shape of a weasel in a cloud. But I’m not questioning the power of cumulative selection.”
I disagree that one needs a target. One needs a fitness function, and one can then ask whether the simulated evolution increases the fitness. Fitness may or may not be a fitness-proxy function that measures distance to a target.
Cumulative selection succeeds in increasing this fitness if it finds higher fitnesses than one would find simply drawing genotypes at random from the space, or wandering by random mutation with no selection.
Fitness functions considerably smoother than needle-in-a-haystack functions or white-noise functions should be common in nature, simply owing to the laws of physics, as I have noted many times here.
I’ve said this loads, but ALL the target does in Weasel is provide a differential among variant genotypes for the likelihood of reproduction. Comparison to a target does that, but it does not need comparison to a target to do that.
One could provide a fitness regime in which higher numeric values were rewarded more than lower. This does not make infinity a target. A biological analogue might be running speed. Of course there are countervailing trade-offs, also subject to selection. The optimum speed is discovered, not chosen.
Joe, I think that’s intentional on his part. He’s intending his program as a reductio of the concept of testable cumulative selection.
That’s what fitness is. Higher values are proportionately more rewarded. The “fitness” values in the examples here are actually fitness-proxy values, not fitnesses.
Mung,
Let’s cut to the chase. What spooks you about Weasel is that it bolsters the case for unguided biological evolution. You are looking for ways to undermine that case.
Your fixation with targets (as in the comment Joe quoted above) is an example. Biological evolution has no specified targets. If you could show that cumulative selection requires such targets, then you could argue that it is irrelevant to biology and that Weasel therefore demonstrates nothing of relevance to biological evolution.
Hence your attempts to portray cumulative selection as requiring a target, as in your previous OP:
This is just Mungish confusion. Weasel has a target, and so its fitness function rewards proximity to that target. That does not mean that cumulative selection requires a target, as is obvious to those of us who actually understand the concept. The target and the proximity-rewarding fitness function are characteristics of Weasel, not of cumulative selection generally.
Another example was your challenge regarding what would happen if we changed Weasel’s target phrase in the middle of a run. Biological evolution operates in changing fitness landscapes, so if you could somehow show that cumulative selection was thwarted by such changes, you could argue that it’s insufficient as a selective mechanism for biological evolution.
But as anyone who understands Weasel could predict, it simply starts tracking toward the new target, and I even provided a feature in my Weasel that allows you to experiment with this. Your weird single-character latching program, by contrast, can’t handle changes to the target phrase, because any characters it has already latched are latched for good.
Since the target gambit failed, you are now dicking around with weird fitness functions that are designed to impede convergence while still (you hope) qualifying as instances of cumulative selection. As Joe and I have pointed out, that tactic also fails.
Your list of Weasel-related failures just grows longer and longer. What gambit will you try next?
Joe Felsenstein,
True enough – though that is a coincidental fact in the running speed example – up to a point. Some organisms must be too fast for their own good …
I’d originally worded it the other way round, lower values gaining greater reward which ‘doesn’t make zero a target’, rather than ‘infinity’, and not thinking of a biological analogue at all.
Looking at how close something gets to a target is not how we determine that cumulative selection is in operation.
In so far as we are dealing with a computer program, we just look at the code.
No, I simply assume we are talking about the program you wrote, not what an all-applicable definition of cumulative selection would be.
Does any one know what is happening at Uncommondescent.com? I register there and put comments about Intelligent Design but my comments never show on the cite.
ThIs site is full of people who can’t post at UD.
walto,
If so, it fails.
It’s quite easy to test the effects of cumulative selection in Weasel. My code allows you to run with selection turned on or off, and to toggle it mid-run if you desire.
keiths:
Rumraket:
Mung:
Rumraket:
Yes, and this is the sort of scenario in which latching makes all the difference.
With the mutation rate at 80% and latching enabled, my program hits the target phrase after 12 generations or so. That’s fewer generations than there are characters in the target phrase.
With latching off, it runs for tens of thousands of generations without achieving even a 50% match to the target (14 out of 28 characters).
Because the mutation rate is so high, the program can quickly achieve a match at any particular character position. That’s why the latching case converges so quickly. But with latching off, a match at any particular position tends to get mutated before the rest of the phrase “catches up” with it and achieves match.
Allan:
walto:
Since no one has explained the joke to walto, I guess I’ll volunteer.
walto,
Allan is not dissing Mung’s CPU.
The joke is that by dedicating 100% of his CPU’s time to running his useless program, which never converges, he would be preventing himself from posting here — a useful outcome in Allan’s view. And in mine.
That’s odd. I wrote a GA with the same genome format and it converged just fine.
Do it the hard way.
Patrick,
At least one difference is that Mung’s program apparently used a character space of size 2^16, while yours was 2^7.
I modified mine to use 16 bits per character instead of 7. With a population size of 1000, mutation rate of 0.02, and tournament selection, it converged on the first run in 2045 generations. This included crossover. When I turned that off it converged in 3042 generations.
With 7 bits per character it typically converges in 20 to 30 generations.
Already been through that one. 🙂
155076285:RYRQOIKKFPQSZZBLPVMTCKGHAYEA
155076286:DJTKATKPZMJUZSXFOU A OKKYCU
155076287:MMAV LFR OOXTKXZFVRSA BPJ A
155076288:MKOTBE WCPEAPXLCCJE Z NYSZKL
155076289:JCIGOYVN RTMQGMHRPENZKDIANVW
155076290:GILFJYQSLTLLESXJLMENHOLJVD L
155076291:ABTAQOKVDFU MZNDCHIIPOWGMRZD
155076292:KVAFNNFYMUTRNNOYJHTCMDGPHSXL
155076293:NKVLIPCUSDIRQSNYOYLFATVOHYYI
155076294:OOIPNEKZDHRFCH LPBD BFRPMZUZ
155076295:AR NCBJNCOT IVNJGYDTBCWC HED
155076296:RERDDVBWKHJ ISYQVXYM FW HLEN
155076297:YJLHXYJUUVKOQRJWBKDXAUWRLEBP
155076298:CFHLYOCYUCJ IN JPAE DNHRLTCO
155076299:LBHZSTIWIHTVZOVWIAT JAITA HT
That’s a lot of generations without a Weasel.
414870140:DYZWOR TDWK LMZYMCRHZ VFAXNY
414870141:RNDBWGNVCHYWHQWCQ EYQPXQCEML
414870142:CALXIBSTANXYSWJ ILECMAMELJHG
414870143:GRONAKKSABMKVSQCXHKLFALPABTG
414870144:VJZBGVVINWHAGPZ I YKHQGDAFHQ
414870145:QTUHIOFJPVNMBIQTKRTC QWLEKAI
414870146:VEWKNOJGWFIYIXDTEHDYB ZEURNF
414870147:SARCBCAOQPQHIH GQRLBQOWRZURH
414870148:TSEWEVFTCXV NJYRVROIAOCYXJYX
414870149:ISAZOSKGRJTXCNGPWRKGFNPJSTCL
414870150:KMJZOPRGVKTLKHHPIBX KKHDTPEE
414870151: QYTLOYXRHXLIILLVKZAGP MAFYM
414870152:XLVFBGKEVFLIHSZMWQUENSLHJWAB
414870153:SGIBZLAPDXCYKARMB MLAYEYEVPS
414870154:AGJIHNXECRMYNGXGAPUYI COCUCP
414870155:MIACWZGOSPA HYEJERKJJXLV OQE
414870156: RRAUEDARIY GPGGXDFYO SLXXNL
414870157:MVOPDSNG FZONYJBYGFJTKQMB LZ
414870158:XYTPKPPJOJRHBTYXNIVAOWSNECLN
That’s even more generations without a Weasel.
So?
Sorry, I had to stop those runs prematurely. They were hindering my ability to post here at TSZ. No doubt if I had just let them run on long enough a lucky Weasel would have emerged.
I bet somehow, under the covers, cumulative selection was hard at work and just needed more time. Or a larger population. or a smaller one. Or a greater mutation rate, or a smaller one. Or a different fitness function, or a smaller search space, or… or …
So I have a target and a fitness function that rewards proximity to the target. So now what’s your excuse?
Are you like Rumraket, you have to see the code to tell whether it uses cumulative selection?
keiths, perhaps you and Patrick could put your heads together and come up with a GA that demonstrates the power of cumulative selection without any target or targets or without a fitness function that rewards proximity to a target or targets.
For extra credit share your secrets with the rest of us so we can code along with you in a language of our choice.
Try not to code it as a search of a search space where a solution can be found in the search space. You know, try to make it look like it was not intelligently designed.
Mung, what is the target in the travelling salesman scenario?
Asked and answered at least twice now petrushka.
Why not talk your buddies Patrick and keiths into coding a GA that solves traveling salesman problems that have no targets.
ETA: Don’t be surprised if the first question I ask them is, what are you solving for? Or, what is the problem you are trying to solve? Or, what would a solution look like.
I got that, thanks. I think you missed my point.
If it has been answered why are you still asking your stupid fucking question?
A travelling salesman solver is a GA with no target. There’s your answer.
OK, let me give the ignorant layman’s perspective here:
I have to admit I’m kind of disappointed with the evo guys on this thread. Mung is making fun of the notion of cumulative evolution. He says you can’t either define it or provide the parameters for a good test for it. Just blow him up already–if you can.
OTOH, I THINK, though I’m hardly an expert, that y’all are doing a bit better with joe coder on the other thread. I mean, I haven’t seen what I’d take to be a complete decimation of his position, but he seems to me to be fudging to a significant extent. I give him credit for his industry, however. Again, I’d think a simple refutation would be possible, and that keiths is hovering near one, but–again, by my admittedly dim lights–it’s not at the point yet where he should be running away with his tail between his legs. I would like to see Joe Coder back up the claims he’s made to rumraket regarding the “widely accepted/standard” definitions of various terms he’s using. If that’s true, it ought to be easy to provide the back-up–much easier, in fact, than a bunch of other stuff he’s provided upon questioning.
Back on this thread, though, the situation is worse. By not providing the criteria Mung says you can’t provide, you’re letting him kind of dance on your heads. I don’t like that…..