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?
Mung is definition lawyering. Not a useful activity.
walto,
Mung has bamboozled you.
We can easily demonstrate the power of cumulative selection, and that was true long before Mung started this thread.
For example, my Weasel program allows selection to be turned on or off. That can make the difference between a run that converges in seconds versus one that runs indefinitely and wouldn’t be expected to succeed if it ran for a billion years. The program is the same. The parameters are the same. The only difference is whether selection is enabled.
Here’s my description of what Mung is trying in this thread:
Mung has failed again, to no one’s surprise.
keiths:
walto:
Um, no. You wrote:
You missed Allan’s joke, which had nothing to do with dissing Mung’s CPU.
It’s a game played many times before. Whatever is provided will not suit, and if it does then in a couple of months it’ll be forgotten about.
In any case, I’ve already answered Mung as to how cumulative selection allows the TSP to be solved with good solutions and arbitrary targets. .
Mung,
Walto,
Mung’s failure to understand means that his demands are nonsensical. Every solution to the TSP is a ‘target’. It’s just that some targets are shorter then others.
If you think that the failure to provide something absurd is significant then Mung has you fooled.
And I’ve already coded such – the random solution finder. It generates solutions to the TSP without regard to length, only that they are a complete path. Perhaps it does not qualify as a GA but a few simple changes would fix that.
If Mung had something significant to say on GAs et al he’d write a paper or propose something significant that was not to do with WEASEL, a trivial pedagogical example from decades ago.
Mung, the TSP is a well studied problem. Why don’t you use the science of Intelligent Design to find solutions?
The irony is that Mung’s word games would have no place in the world of actual scientific publishing.
Hey, Mung, you ever had any papers published?
Me? No, never. But then again I’m not attempting to destroy the very foundations of a discipline like you seem to be attempting to do (badly).
I didn’t put it as well as I might have perhaps, but it’s clear from the above that YOU obviously didn’t get what *I* meant by “dissing Mung’s CPU.” (You really are quite dense sometimes.)
I definitely jumped in without knowing the (no doubt vast) history here. And I’m also very much out of my wheelhouse. I thought, though, that it might be useful to get the sense of someone like me on the state of the debate–even if it’s based only on a snapshot, and seen with astigmatism.
My remarks should absolutely be taken with a grain of salt–as I’m sure they will be.
TSP is an ID killer because it is a problem better addressed by evolutionary algorithms than by traditional computational approaches.
It is a real problem in the real world. Solutions have commercial value. Corporations use GAs every day to plan delivery routs.
There are no targets, only solutions that are better than other solutions. Sort of like many things in life.
Without actually touching keiths’ head, I offer the Steiner Network as an example.
If you want one that not only doesn’t have an explicit target but has a constantly evolving fitness function then ev is a contender.
If you want one that has no explicit target and no explicit fitness function, Tierra is your huckleberry.
By Dawkins definition (The Blind Watchmaker, page 45):
“The essential difference between single-step selection and cumulative selection is this. In single-step selection the entities selected or sorted, pebbles or whateverthay are, are sorted once and for all. 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. The end-product of one genration of selection is the starting point for the next generation of selection, and so on for many generations.”
it’s hard to think of a GA that doesn’t demonstrate cumulative selection.
walto:
Which was…?
Patrick,
Thank you for not touching my head. I was still asleep.
And for some examples closer to home, see Rich’s math genome threads.
No mention of how these programs demonstrate the power of cumulative selection. just claims that they do. Is that intentional?
GA’s have been a traditional computational approach for years petrushka.
Re-read Dawkins’ definition of cumulative selection and you should understand.
Mung:
Jesus, Mung:
Solutions = Targets.
If every potential solution is a solution where’s the demonstration of the power of cumulative selection in that?
Let’s say the algorithm finds increasingly “better” solutions. That may be an indication of cumulative selection in action.
But that means defining “better” and “worse” and ranking and favoring and comparison to some ideal. IOW, targets.
A program that is just aimlessly mucking about is not going to demonstrate the power of cumulative selection. There must be an aim, a goal, a purpose, an end. Teleology. Even if you don’t know that you have obtained the best solution [as in Weasel], it’s still there as an ideal.
That is apparently the source of your error. Evolution finds solutions to the problem of surviving and reproducing without any target. Some EAs model that.
Not to some ideal, to each other in the current environment. No target.
keiths,
Are you saying that if a program converges on a target it is using cumulative selection to do so? And if it does not converge on a target it is not using cumulative selection? Because other people here clearly disagree with you, if that’s what you’re saying.
How would you know the program “wouldn’t be expected to succeed if it ran for a billion years?” Evolution takes place over billions of years. Supposedly it uses cumulative selection to find the best solutions.
Yes, if you set up a Weasel program “just right” you can demonstrate the power of cumulative selection.
Given those conditions, how do you demonstrate the power of cumulative selection? Faith?
I’m asking for objective empirical evidence. What are it’s units. How do you measure it? Is cumulative selection something that cannot be quantified?
Say we take Weasel as an exemplar. How would you define and measure cumulative selection in a Weasel program in such a way that we could determine, say, that Weasel Program 1 better demonstrates the power of cumulative selection than Weasel Program 2?
Mung,
No. If you want to know what I’m saying, read my comments. This one is quite clear:
Mung:
You calculate it.
And…?
That is just brain dead stupid, mung.
A target is not the same thing as a selection function.
Is any Weasel program that allows selection to be turned on demonstrating cumulative selection? I ask this because (again) one of the Dawkins quotes above suggests that selection is cumulative just in case it reiterates in successive generations (hence, it accumulates). Is that all that is meant by “cumulative” here?
I’d have thought that something more was meant–but I could be wrong.
Is it really that difficult to answer those?
Is it easy to answer strawman questions?
Let mung provide an operational definition of cumulative selection, and then we can answer it.
Stop the Lucy/football shit.
walto,
The issue has already been settled, so those questions are pointless and irrelevant.
What part of my demonstration eludes you or fails to convince you?
This is a good read, I think I mentioned it before: http://pandasthumb.org/archives/2006/07/target-target-w-1.html
TSP is something I find interesting.
You’re mixing apples and oranges. Look at Dawkins’ explanation again:
“The essential difference between single-step selection and cumulative selection is this. In single-step selection the entities selected or sorted, pebbles or whateverthay are, are sorted once and for all. 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. The end-product of one genration of selection is the starting point for the next generation of selection, and so on for many generations.”
Cumulative selection occurs as long as there is differential reproductive success (“selection or sorting”), regardless of whether or not there is an explicit or implicit target.
Using Dawkins’ definition, cumulative selection is an observed process. If you have a series of populations related by differential reproductive success, you’re observing cumulative selection.
It’s clear that you could easily have figured that out for yourself. What’s your actual argument here?
That’s not responsive to my question. If those questions hve been answered already, can you provide a link to actual answers?
So is sequential single step selection necessarily cumulative selection? (this is a simple yes or no thing, I think.)
Why not call it all or nothing selection?
The relevant question for any GA is, does it reinforce mutation sized increments in whatever the selection function evaluates?
A metaphorical way of putting that is, does the selection function “see” individual mutations.
I’m not sure I agree. Cumulative selection can take place when the fitness function operates at the virtual phenotype level, not just the genotype level.
Perhaps a problem expressing myself.
If a gene change makes no change visible to the selection function, it is by definition neutral. In Dawkins weasel, you could have this in a case where you have simultaneous changes in several genes, making a net gain or loss.
But nitpicking aside, a single step function seems to merit the term all or nothing, whereas evolution seems to happen by small, incremental changes.
Over in another thread:
Now you know how I feel. BlinkenWeasel.
walto seems to think it is you and Patrick who have been bamboozled.
Let’s take a trip back down memory lane…
And yes, I’m still waiting for someone to tell me how to test for “the power of cumulative selection.”
How about if I write a Weasel program that has an API. What would the API need to have to allow another program to tap in and check to see where the current power level is?
Perhaps an analogy is in order. I’ll assume we’re all familiar with electrical power.
You can demonstrate the power of electricity by sticking your tongue in a socket (not recommended). You can stick your tongue across the leads of a nine volt battery. There is a definite and discernible difference.
The power of electricity can be quantified and measured. We can compare two electrical sources.
Surely the power of cumulative selection is even more powerful than the power of electricity. I mean, just look around at the living world and see what the power of cumulative selection has wrought! But no one knows how to measure it.
We can look around at the living world and see what natural selection has wrought. And we can measure fitness differences between phenotypes and between genotypes, with suitably hard work in suitably tractable biological systems.
Is that how we measure the power of cumulative selection, by looking at fitness differences?
Mung,
No, you aren’t:
Mung:
You can run Weasel with cumulative selection and see it converge within seconds. You can run it without cumulative selection, changing nothing else, and see it spin its wheels indefinitely. There is a definite and discernible difference.
The power of cumulative selection can be quantified and measured. We can run two Weasel scenarios that differ in nothing but whether selection is enabled, and measure the time (or generations) required to reach the target.
You have your “objective evidence”, Mung.
You’ve lost another round against Weasel.
That seems to me a kind of burden tennis, and I don’t really know whose serve it is. It just seems to this outsider that if some person or group insists that there is cumulative evolution [ETA: I meant to write “selection” there] and that it is powerful in producing increased fitnesses, they ought to be able to say what THEY mean.
I’m about as far from a theist as it is possible to be, and I’ve asked, I think five times now, whether cumulative selection is nothing but a matter of iterative single-step selections, as one of the Dawkins quotes above seems to indicate, and nobody will fucking answer me. That doesn’t exactly inspire confidence.
If Mung is full of shit, as I assume he is quite likely to be, I think one who believes in the aforesaid power could simply indicate what THEY mean by CS, what a decent test for it is in a simulation, and why mung’s attempted reductio is therefore full of shit. But I’m not hearing that. Could I have missed a good answer to these questions? Certainly. Was it in Patrick’s last post? I’m not sure–if so, he wasn’t clear enough to pierce my fog.
So somebody explain this to me. Slowly. Starting with this: Is cumulative selection nothing but single-step selection, generation after generation. Is that sort of “accumulation” of selections by definition cumulative selection, or is something else required?
Thank you in advance.
Mung,
walto also says this:
They absolutely should be. I’m just giving my two-bit impressions and asking extremely elementary questions. That’s it. My opinion is as close to worthless as it’s possible to be without having negative value.
See, this is precisely the ambiguity I’m complaining about. Is cumulative selection the same as selection simpliciter or isn’t it? If I turn selection on, have I thereby turned cumulative selection on?
I’m sure you realize that some people will argue that remark is question-begging. I agree with you that they are kooks, but that isn’t an argument.
Yes, walto, cumulative selection is iterative. That’s what makes it cumulative.
In Weasel, for example, you select the fittest offspring from each generation and allow them to reproduce while denying that privilege to the others. That’s the selection part.
Then you repeat the process for their offspring, and for their offspring’s offspring, and so on. Beneficial mutations can accumulate because of this. That’s the cumulative part.
It’s a hill-climbing process in which the surviving genotypes, generation by generation, climb the slopes of the fitness landscape toward peaks, global or local.
Mung’s gambit in this thread was to create brain-dead fitness landscapes that lacked climbable slopes, thinking that this would somehow weaken the case for the power of cumulative selection in biological evolution.
It doesn’t, because no one is claiming that cumulative selection succeeds in every instance.
Imagine an alternate universe in which Mung were intelligent. In such a universe, Mung would realize that to cast doubt on unguided biological evolution, he would need to show that the fitness landscapes in question lack climbable slopes. And if he were intelligent, he would realize that he can’t.
I think, based on the available evidence, that it’s reasonable to think that a selection function selects for something.
If you don’t want to call it a target it’s just because you’re word-lawyering!
🙂
It’s not the selection that makes it cumulative, it’s the iteration. And here I thought it is the accumulation that made it cumulative. Perhaps Patrick and keiths are right and I don’t actually understand cumulative selection.
So in the Weasel program more and more letters that match a specific letter at a specific position in the target phrase accumulate in the candidate “genome.” But it’s not the accumulation relative to the target that is characteristic of cumulative selection, it’s just the iteration that makes it cumulative.
If I were walto, I wouldn’t buy what you’re selling.
We don’t know whether this is true or not.
What we do know, is that in the keiths implementation of Weasel, in which we find the following bit of code:
// number of survivors per generation (must be less than POP_SIZE)
#define NUM_SURVIVORS 1
There is no “they,” there is only “it.” There is one survivor, and that single survivor must produce POP_SIZE number of offspring. So we’re not talking sexual reproduction here, are we. And this is biologically realistic how?
ETA: Every generation leaves only one single offspring and that one single offspring has enough reproductive capacity to restore the original population number. Realistic or not?
I would pay a small sum to watch Mung try to outsmart a box of rocks.
The problem isn’t the lack of selection. The problem is the selection function has no definition of a goal.
If I jump in a taxi and say get me as far away from here as possible, I do not have a destination.