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?
Yes, Google says:
https://developers.google.com/optimization/routing/tsp
You can use google maps to solve the TSP!
That is not a target. It is the behavior of the selection algorithm. One can Humpty-Dumpty this, but behavior of a program is not a target.
As I said, one can add an arbitrary halting condition, but the program will run indefinitely without a halting condition.
It really is conceptually equivalent to LTEE.
A simple Dawkins algorithm can reach a point wher fitness never increases.
A TSP program evaluating thousands of nodes will never, in the life of the universe, reach a point where fitness cannot increase.
Yes, that’s sort of what I was trying to get at. The program can be run with and without that behaviour, but each time it outputs solutions to the TSP.
What do you object to in Dawkins’ definition?
It amazes me that atheists are so afraid of common English words. The recent history of this site is one case after another of constantly trying to run from simple definitions.
I can understand the frustration
It’s almost as if all of language is conspiring against you guys. 😉
peace
no the target is the shortest possible length a solution can have
peace
Then you have established that such programs do not have targets, because that value is not coded in the program.
It is often unknown what the shortest possible length a solution can have. Hence it cannot be a target – how can the unknown be a target? How can you know when you have hit that target? If you decide to stop on a particular solution, how do you know the next one along would not have been shorter?
fmm, after studying programming now for almost a year you should be able to write a simple solver for the TSP. Why don’t you do so?
http://francisshanahan.com/tsa/tsaGAworkers.htm
Sorry, but the program works fine without knowing that value, and even if it knows th value, it will never reach it. It doesn’t need to know anything at all about goals.
Richard Dawkins’s Weasel Program Is Bad
😀
They hate targets, but they need them. Like teleology in general.
So? Has someone here claimed that Lenski’s cultures demonstrate the power of cumulative selection?
And it’s absurd to think that some value must be hard-coded into a proram for there to be any target.
If every candidate solution is a solution then every candidate target is a target and Dawkins’s Weasel program tells us nothing at all about cumulative selection.
And if TSP have nothing to tell us about the power of cumulative selection they are irrelevant to the subject under discussion.
How is the power of cumulative selection demonstrated in TSP programs? If you cannot say how then the whole line is just a red herring.
See walto, how easy it is to dismiss my argument, because everyone simply knows that I am wrong, lol.
Mung,
Seems to me you are arguing about the efficacy and relevance of computer models. I’d suggest it’s a case of good enough or better models of whatever you want to model.
How does the programmer sneak in the target in?
Mung:
That’s right. And after explaining it to you a dozen or so times, we start to lose interest.
“But Dawkins waves off these shortcoming by saying the little program is merely for illustrative purposes and suggesting that more sophisticated programs will be designed soon enough that properly mimic natural selection while still illustrating how wonderfully productive the evolutionary process can be.
Three decades later, we’re still waiting.”
No, they’re not still waiting. What they wanted has been provided countless times. Best example I know of is Avida.
They are deliberate liars on evolutionnews.
You can demonstrate the power of cumulative selection both WITH and WITHOUT targets.
So no, it is plain false to say it tells us nothing at all about cumulative selection.
By showing that fitness iteratively increases over generations. Because there’s a hill to climb. That’s what cumulative selection is, climbing hills in the fitness landscape.
How many times must we answer this question? How many times will you ignore it?
Nobody NEEDS targets to show how cumulative selection works. There are no targets, for example, in BoxCar2D. Yet BoxCar2D still manages to capture the effect of cumulative selection.
Programs with targets are made because they are comparatively easy to make. It doesn’t take a lot of code, you don’t have to program a simulated environment.
Yes. Targets are just very simple stand-ins for the environment. We do not have the computational resources to emulate biochemistry and ecosystems.
What even the simplest GAs model is the effects of differential rates of reproductive success.
It has cumulative selection. It’s called an “example”. There is selection, because the GA prefers shorter solutions, and ir is cumulative, because it gets shorter and shorter ones, ultimately finding solutions much shorter than random ones.
What part of “example” don’t you understand?
That’s the claim.
Yet people can’t even explain how to do so with a simple program that has a single target, much less one that has multiple targets, or no targets at all.
If there’s only one hill? Can we call that a target? If there’s more than one hill, can we call those targets? And if there are no hills/targets?
A simple hill climbing algorithm is all that’s needed?
Avida has a target or target and uses hill-climbing?
How can we tell that fitness is is iteratively increasing over generations?
Is there a minimum number of generations? A maximum?
Is there a minimum fitness? A maximum? How do we measure the fitness?
If fitness declines is that uncumulative selection? If fitness stops increasing is there no longer cumulative selection? How do you know that fitness is no longer increasing?
This comment from more than a week ago still applies:
Mung, evolution, either real or simulated, is cumulative because it starts each generation from the result of the previous generation.
You can take, say a GA that finds routes in a TSP, and make it noncumulative by simply, after each generation of selection, resetting the population to the original initial population. We would save the best solution found in all those generations of noncumulative selection. We would compare those to the solutions found by allowing selection to be cumulative.
The power would be shown by the results of a bet we would have with you, with you betting that the result of cumulative selection is not better than noncumulative selection.
That way we would avoid wasting time on fussing about language of specifications and formal definitions.
Sure we can, and have done. Dawkins WEASEL is one such program. So is yours.
Sure we can. If there are multiple targets, you just evaluate the “fit” of the organism to each of the targets. The best matchs to any one of the targets is copied to the next generation.
If there’s no target, you need to start doing actual simulations of the organisms in an environment and have them compete in some way. Like in the BoxCar2D program. Here the fitness is not how well a string matches another target-sequence, rather the fitness of the “organism” is how far the car can make it in the landscape before stopping. So there’s no set target.
You can make even more complicated simulations where even the process of reproduction and metabolism is simulated, so there’s actual competition to produce more offspring that consumes limited resources. That would be the Avida program.
No. Targets are something you set up beforehand and then try to hit as accurately as possible.
There can be hills without them being set up beforehand with the intent of hitting them.
Only if they were deliberately set up so something is trying to hit them.
If there are no hills cumulative selection is impotent. If there are no targets there are no targets. There can still be hills without there being targets.
To show the power of cumulative selection, yes.
By observation. For example, in your own program, compare the sequences at arbitrary generations and see the degree of match to the target phrase.
Yes there’s a minimum: 0.
There is no maximum.
Depends on how the program works. For example in your own program, the fitness is the number of sites that matchs to the target phrase. So the minimum fitness is 0, since there can be a string with 0 matches.
Depends on how the program works. For example in your own program, the fitness is the number of sites that matchs to the target phrase. So the maximum fitness is 28, since there can be a string with no more than 28 matches, because the target phrase is 28 sites in length.
Depends on how the program works. For example in your own program, the fitness is the number of sites that matchs to the target phrase. So we just count the number of matches.
Fitness can decline while cumulative selection is in operation, but that would entail selection isn’t strong enough to overcome whatever force it is that works against it.
There can still be cumulative selection when fitness stops increasing, but that would just imply you’ve reached the peak of the local hill. In your program, for example, you would have reached the target sequence.
By determining an arbitrary length of generations over which you measure fitness at various intervals. Obviously if selection is slow enough, you might actually be in one of those situations where it looks like there is no increase, but the number of generations between fitness increases is too great for you to detect it in the amount of time you used.
Thanks for that extremely clear statement of what cumulativity is and what a test of it amounts to.
It’s been explained to you repeatedly. Here’s Dawkins’ definition 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 is observed in his Weasel program, with its target, and in other EAs like those that evolve solutions to the traveling salesman problem, without targets.
Do you find this definition unsatisfactory for some reason?
Objective empirical evidence, Patrick. Do you have any?
Objective empirical evidence. Quantification. Testability.
Is it an operational definition, and if not, why not?
Examine the code in the OP. Does it fail as an example of single step selection? If it fails as an example of single step selection, why so?
What does that even mean? Sorted once and for all? How do we test for “sorted once and for all”?
I think it’s sufficiently detailed to be useful:
“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.”
You can step through the vast majority of EAs, including Weasel and its variants, generation by generation and determine that each successive generation builds upon the previous one, with changes driven by selection pressures. That meets Dawkins’ definition of cumulative selection.
Do you disagree?
Patrick: Thanks for the Dawkins quote. It is entirely consistent with my statement (above) that
Starting each generation from the results of the previous one is of course a basic property of organisms that reproduce.
Cumulative change is a better term, since selection can imply truncation or differential selection. According to Moran and company, truncation accounts for more change at the molecular level than selection.
I believe keiths supported this by allowing the software user to set a minimal criterion for survival, but no particular goal.
Yes, I disagree. The “definition” you cite fails to capture an essential characteristic of cumulative selection. If we use that definition of cumulative selection the Weasel program is irrelevant. Do you disagree?
The Weasel program adds some other element to cumulative selection that is not reflected in that definition. Can you tell us what that is, Patrick?
If that’s all that cumulative selection means, what was the point of the Weasel program?
Does my SS Weasel program NOT start each generation from the results of the previous one?
Mung, to Joe:
To demonstrate the power of cumulative selection.
I addressed that already:
And:
And as Joe asks:
You don’t need a Weasel program for that. After all, “starting each generation from the results of the previous one is of course a basic property of organisms that reproduce.”
No, you didn’t. Here’s the question 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?
Christ, Mung.
Your “SS Weasel” doesn’t demonstrate the power of cumulative selection. Weasel does.
The answer is yes. Weasel-like programs demonstrate the power of cumulative selection else they are not Weasel-like. Even the keiths Drift-Weasel is Weasel-like.
According to the definition given by Richard Dawkins [as quoted by Patrick and endorsed by Joe F.], my program implements cumulative selection. If you think otherwise, please say why.
Now if you agree my program does in fact implement cumulative selection according to the definition given by Richard Dawkins [as quoted by Patrick and endorsed by Joe F.] but you think this is not sufficient to “demonstrate the power of cumulative selection,” then you are in fact agreeing with me, for taht is exactly what I have said.