Doggies are Better than Weasels
Over at the Panda’s Thumb, Dave Thomas has posted the results of another computer simulation of natural selection, this time applied to the classical “Traveling Salesman” problem. No, that isn’t the lead-in to an old dirty joke, it’s a classical problem in optimization. The basic idea is to calculate the shortest possible route for a traveling salesman to follow when visiting more than three cities (i.e. sales territories). Clearly, when there are only two cities, the solution is obvious to anyone with a knowledge of Euclidian geometry: a straight line connecting the two cities. However, as more cities are added, the number of possible solutions expands exponentially, making calculations of optimal pathways extraordinarily difficult.
This is where Dave Thomas (and a dish of soap bubbles) comes in. In his post at http://www.pandasthumb.org/archives/2006/07/target_target_w_1.html#more , Thomas first shows the classical solution to a five-node traveling salesman problem (TSP), as demonstrated by the Swiss mathematician Jakob Steiner (see http://en.wikipedia.org/wiki/Jakob_Steiner ). He then illustrates the optimal solution using a soap film generator, which uses free-standing posts and soap films to generate the optimal solution.
Thomas then goes on to formulate a “solution engine” for higher-level Steiner problems (i.e with more than five asymmetrically placed nodes), using natural selection operating on a computer-generated “TSP solver.” The results are truly astonishing: although the theoretical number of possible solutions is fantastically large, the TSP solver using simple natural selection (call it the NS_TSPS) found several optimal solutions with amazing speed. The same thing happened when Thomas tested the computer-generated solutions using soap films. Indeed, he was able to show that the NS_TSPS was actually more efficient at finding solutions than the soap film generator, a result that surprised him (and most of the commentators on the Thumb). One of the soap-film solutions took the shape of a “doggie,” a solution that the NS_TSPS didn’t find. Thomas was able to show that, although the soap-film solution was stable, it was actually sub-optimal to an alternative solution generated by the NS_TSPS (hence the title of this post)
Why is all of this important, in the context of our discussion of Dawkins’ The Blind Watchmaker? Because, unlike Dawkins’ WEASEL program, which used a pre-specified “target,” thereby opening his model to accusations that it simply “found” a pre-specified outcome (and was therefore actually an example of “intelligent design”), the NS_TSPS had no pre-specified solution at all, and found the optimal solutions the same way natural selection “finds” them in the wild: by simple trial and error, combined with preservation of partially successful outcomes.
In other words, the objections that some of us had to Dawkins’ WEASEL program have been addressed in Thomas’ NS_TSPS, and natural selection has been shown once again to be all that is necessary to “find” an optimal solution to a “problem,” even in the absence of a pre-specified outcome.
This is important to the ongoing discussion in our course for several reasons:
• It decisively undercuts the objections commonly voiced by advocates of ID, that all simulations of natural selection are actually simulating ID, as they all include pre-specified “target” outcomes.
• It shows the extraordinary (and somewhat counterintuitive) power of natural selection to “find” adaptive optima, even in the absence of pre-specified solutions.
• It reinforces a finding that has increasingly been coming out of research into computerized “genetic algorithms”: that selection processes that incorporate non-directed natural selection can find solutions to problems that are highly resistent to more “classical” targeted computation.
• It demonstrates that the common assertion by ID theorists that ID theory is logically necessary as an alternative to evolutionary theory, since the latter has failed to demonstrate empirically that it can solve such optimization problems in real time, is empirically false. That is, ID theory isn’t necessary to explain adaptation, even in cases where the computation of adaptive optima appears to be beyond the capability of any real-time computing system.
And this, in turn, emphasizes the point that I have made in several other posts to this blog: that rather than ID theory being a logically necessary alternative to evolutionary theory, it is a logically unnecessary addition to standard evolutionary theory, and one that furthermore is not supported by the empirical evidence.
There are other simulations of evolution by natural selection that are immune to the common objections voiced by ID theorists. To learn more about the most powerful one developed to date, go to: http://dllab.caltech.edu/avida/.
Rabia, thanks for the excellent summary.
I have one question and I realize it may be difficult to answer. You wrote
It shows the extraordinary (and somewhat counterintuitive) power of natural selection to “find” adaptive optima
What do you find “extraordinary” or “counterintuitive” about the ability of natural selection to “find” adaptive optima?
For myself, the finding is neither “extraordinary” nor “counterintuitive.”
I’m not bagging on the experiment — it appears to have been well designed and executed — but does it not simply (elegantly) confirm what is blanking obvious to 21st century biologists?
Comment by Susan Percell — July 6, 2006 @ 1:33 pm
The whole concept of ‘evolutionary algorithms’ has been done a major disservice by the claims and arguments by various ID proponents who confuse concepts of fitness function etc.
Pandasthumb has done some excellent work in rectifying this situation, starting with Dave Thomas’s expose, followed by Mark Perakh providing chapter 11 from the book Why Intelligent Design Fails: The Scientific Critique of the New Creationism in his contribution There Is a Free Lunch After All
In earlier postings on PT I have shown how contrary to claims from Dembski, random search almost trivially finds ‘optimal solutions’ under the NFL theorem, further undermining the relevancy of the No Free Lunch (NFL) theorems on ID.
In the past Wesley Elsberry with his algorithm room argument has effectively dismantled Dembski’s thesis about algorithms and shown that algorithms indeed can generate complex specified information, leaving Dembski with the concept of apparent and actual complex specified information and no way to distinguish between the two.
Comment by PvM — July 6, 2006 @ 1:34 pm
Sarah:
This post was by Allen MacNeill (i.e. me), not Rabia.
Comment by Allen MacNeill — July 6, 2006 @ 1:49 pm
And the thing that is initially “counterintuitive” about finding optima in the classical Traveling Salesman Problem is that the number of possible solutions is so fantastically high (for problems with greater than five nodes). Despite this, natural selection can “find” an optimum solution in a surprisingly short time (”surprising” given the number of possible solutions), thereby indicating that natural selection can “find” adaptive optima in nature in essentially the same way that Darwin, Sewell Wright, and other evolutionary biologists have proposed that it can.
Comment by Allen MacNeill — July 6, 2006 @ 1:52 pm
Sarah:
This post was by Allen MacNeill (i.e. me), not Rabia.
Oh, sorry about that. And thanks for your answer. I remain unmoved personally but maybe it’s just because I’m tired after the long weekend. ;) The power of methods modeled on natural selection for identifying and optimizing solutions to problems seems well-established to me in 2006, to say the least. Obviously, some folks remain unconvinced by the results of experiments such as Dave Thomas’ but I believe that it is not for lack of understanding that most of those folks remain unconvinced.
Oh, were you a fan of the TV show Real People? I wish I had Sarah Percell’s legs. ;) Sadly, I’m not even related (well, not very closely related anyway).
Comment by Susan Percell — July 6, 2006 @ 2:18 pm
Unfortunately (or perhaps fortunately) we don’t have television at home, and I haven’t watched it for almost 15 years (I get nauseous easily), and so never saw “Real People” (hmm, makes for an interesting pun…)
And, as for me, I’m most attracted to minds ;-)
Comment by Allen MacNeill — July 6, 2006 @ 2:42 pm
I’m going to take issue with one word that Professor MacNeill used: “optimum”. He wrote
I dislike viewing evolution as somehow finding “optimum” solutions, in the sense of necessarily finding the global peak in a fitness space. Evolution finds satisficing solutions in Herbert Simon’s sense of the word — solutions that are ‘good enough’, that are local optima. As the old story goes, when you and I are being chased by a bear I don’t have to outrun the bear, I only have to outrun you.The second GA I wrote 20 years ago had two different selective environments to which the critters were exposed in alternate generations. To (what should not have been but was) my surprise, the population split into two ’species’, one ’species’ performing fairly well in environment A and pretty lousy in environment B, the other species performing fairly well in environment B and poorly in enviroment A. Neither species was at a global optimum in either environment, but both did well enough to survive through time. The process of evolution by random mutation and selection via differential probability of reproduction automatically balances an array of competing constraints to find satisficing solutions in a given selective environment. With the exception of the 0.5% of runs that produced the (provably) optimal Steiner solution, the various MacGyvers that Thomas’ GA found are not optimal, they’re satisficing.
RBH
Comment by Richard B. Hoppe — July 6, 2006 @ 8:12 pm
Allen —
I haven’t had the time to look at this particular simulation, but I think you have mischaracterized the ID response to genetic algorithms in general. I don’t think it is fair at all to take ID objections to the “Weasel” simulation and generalize them to be the only objections to evolution simulations.
Specifically, when you say “It decisively undercuts the objections commonly voiced by advocates of ID, that all simulations of natural selection are actually simulating ID, as they all include pre-specified “target” outcomes.”
Correct me if I am wrong, but I have _never_ heard anyone say that this is characteristic of _all_ such simulations.
There are two things that I would note in the simulation:
1) The choice of symbols for representing the problem space
2) The actual size of the search space itself
Dembski, for instance, has only claimed that such algorithms will not work when the search space is above the UPB of 500 bits per jump.
But most importantly, I think the issue is that the symbols and quantities that are being used are directly applicable to the problem space. If atelic evolution is true, then variation should be applied just as much to the support structure (including the copying mechanisms, methods of feeding, etc.) as to the problem itself, since we are trying to model an atelic generative function. The fact that the symbols used in the search space are directly related to the problem is what is the dead giveaway, and the reason why ID’ers don’t have a problem with small-scale evolution but do have problems with large-scale evolution. Why would an organism have a search space structured in a way such as to find a solution to the problem at hand, unless it had been programmed with likely problem scenarios and the methods of search space structuring to account for them? As the problems get bigger, the difficulties increase exponentially. If you do not constrain the search space, then your algorithm simply will not find the solution. This is an exercise in a highly constrained search space.
I think this is what one genetic algorithm specialist meant when he said:
Comment by Jonathan Bartlett — July 6, 2006 @ 11:02 pm
Abiotic Optimization: Compliments to Dave Thomas for an elegant “solution” to the Travelling Salesman Problem (TSP). This applies abiotic energy minimization, using the physical chemistry of surfaces. (I.e., the minimizing surface energy or “surface tension” of soap films.) Adrian Bejan Shape and Structure, from Engineering to Nature (2000) Cambridge University Press ISBN 0-521-79049-2, similarly shows how abiotic systems form optimal structures. E.g., water flowing under gravity forms an energy minimizing tree structure.
Biotic Optimization: Bejan finds biotic systems also form energy minimizing tree structures. E.g., lungs, arteries, and veins. He attributes this to “evolution” - but without giving any evidence. Biotic systems use regulatory structures with complex feedback mechanisms with high genomic information content, in contrast to dampened hydraulic flow in gravity force field with low information content.
Genetic Algorithms: Genetic recombination is very efficient at mixing alleles and “pseudogenes” to give variations in genomic expression and distributions of properties in populations. The strength of “Genetic Algorithms” (GA) are that they use this efficient method of seeding multi-dimensional vector space coupled with a local optimization method minimization to find local minima and comparing them to find hte global optimum. A GA is locally relatively slow compared to steepest descent methods, but its seeding method is robust if finding the global optimum.
Unwarranted extrapolation Microevolution is easily demonstrated. However projecting macroevolution to homo sapiens starting with abiogenesis is like measuring the relative flow rates of some macromolecules, comparing the crawling rates of earthworms, and from that projecting a winning dynasty of horses that win every triple crown for 3000 years. Thomas and Bejan attribute incredible creative powers to Random Mutation & Natural Selection without addressing the realities of Population Genetics, let alone generation of very large amounts of information. For the detailed models see geneticist John C. Sanford, Genetic Entropy & The Mystery of the Genome (2005) Ivan Press, Elim Pub. Lima, New York, ISBN 1-59919-002-8. Summary details to follow.
Comment by David L. Hagen — July 6, 2006 @ 11:06 pm
Also, for Avida, see these two papers by Royal Truman, and this response from the UCSD IDEA club.
Comment by Jonathan Bartlett — July 6, 2006 @ 11:34 pm
Jonathan Bartlett suggested
Truman’s paper didn’t improve in its final draft.RBH
Comment by Richard B. Hoppe — July 7, 2006 @ 1:35 am
I managed to louse up the formatting of the immediately preceding post, but I think it’s clear who said what. The middle quote box shouldn’t be a quote box.
RBH
Comment by Richard B. Hoppe — July 7, 2006 @ 1:38 am
Possibly because the problem at hand is navigation of the organism’s search space?
Comment by MartinM — July 7, 2006 @ 9:26 am
“Possibly because the problem at hand is navigation of the organism’s search space?”
Unfortunately, this makes the problem more difficult, not less. The search space of possible search spaces is as large or larger than the original search space, yet it is still unstructured.
This is similar to the epistemological “frame problem”. How does the organism, in the absence of pre-existing information to structure the search space, even determine what values might be usefully changed in the search?
Comment by Jonathan Bartlett — July 7, 2006 @ 10:58 am
Avida has had a history of being a buggy program, and I’m happy to admit I was responsble for correcting a flaw in one of their source files (a #include file) for revision 1.6.
Eric Anderson has a good discussion here at ISCID:
Bits and Byte and biology
RBH referred to a discussion with Royal Truman in early 2004, but the following is a later thread where both Royal Truman and I participated with RBH in a second round. See: Truman, Cordova, RBH, and others on Avida
Natural Selection was a creationist conception promoted primarily by Edward Blythe just before Darwin. It is a mechanism for solving problems, not a universal strategy for creating complex designs.
Furthermore, for it to work effectively on interesting problems the feedback mechanisms must be programmed (as in designed).
And finally, it can be mathematically demonstrated that NS or any such algorithm cannot solve a wide range of problems including large scale irreducible complexity. For example, there is no genetic algorithm that can solve your password any better than a fundamentally random or sequential search (with maybe some heuristics added).
And to set the record straight, Avida did not really solve the problem of IC through co-option, it merely assmed it was solvable, defined the simulation in a way that captured that assumption in their software. Thus the Avida researchers merely restated the conclusion they set out to prove: in other words, circular reasoning.
Salvador
Comment by Salvador T. Cordova, IDEA GMU — July 7, 2006 @ 12:30 pm
We are not searching the ’space of possible search spaces.’
It doesn’t have to. The organism doesn’t have to do anything except live, breed and die. Values in the population will be changed; if those changes are useful, they will tend to be kept.
This is a remarkably simple premise.
Comment by MartinM — July 7, 2006 @ 12:50 pm
Well, yes, in the same sense that modelling fluid dynamics proves that physics is designed …
Ahem…
And, no, programs like Avida are not examples of “circular reasoning”.
Essentially you’re saying that since programs are programmed, you can’t write programs that model things in nature that aren’t designed, which is hooey.
Comment by Don Baccus — July 7, 2006 @ 12:50 pm
Sal
Sal equivocate between a problem with the include file and it being buggy. Sal made some claims about Avida which were shown to be fallacious. To claim that Avida is buggy just plainly is an attempt to trivialize its relevance to show the vacuity of intelligent design’s claims.
Sal then creates and attacks the usual strawman
And finally, it can be mathematically demonstrated that NS or any such algorithm cannot solve a wide range of problems including large scale irreducible complexity.
Which of course does not mean that NS cannot solve wide range of problems including irreducible complexity. It merely shows that there are some limitations to the algorithm but does little to show that NS cannot explain the complexity in the genome. In fact it has been shown how NS can explain IC systems as well as complexity in the genome. And of course, it also shows how ID’s focus on selection as the sole evolutionary mechanism, is another red herring.
Avida is a thorn in the sides of those who argue, erroneously, that algorithms like NS cannot explain IC systems and/or complexity. Which explains the attempts to downplay its relevance. Once again, ID tries to hide in the shadows of our ignorance, rendering it scientifically vacuous.
Comment by Pimothy-PvM — July 7, 2006 @ 1:03 pm
The organism doesn’t have to do anything except live, breed and die. Values in the population will be changed; if those changes are useful, they will tend to be kept.
This is a remarkably simple premise.
I agree. The more interesting question is: who doesn’t and what do those people have in common?
Comment by Susan Percell — July 7, 2006 @ 1:25 pm
Salvador wrote
The source code is publicly available. Point specifically to the part of the source code that “captured the assumption in their software” or withdraw the canard.RBH
Comment by Richard B. Hoppe — July 7, 2006 @ 1:59 pm
Why? They admit to it in their paper:
Comment by Jonathan Bartlett — July 7, 2006 @ 2:30 pm
How does one tell Avida that a feature is selectively advantaged? Answer: put it in the parameter file.
NO calculation is done whether such a feed back loop is even feasible in physical reality. Just assmume a value which will help one arrive at the conclusion one wishes to assert.
One could give affix as much selective advantage to any feature until one gets the results one wants. Is that empirical sceince? It barely qualifies as theoretical science.
I invite readers to look at how Avida models the genome. Does it look like anything in real biology? Can it be demostrated that something so decoupled from reality (like Avida) can give valid statements beyond merely re-asserting traditional tautologies?
Here is the more recent tautology: “if co-option is possible, co-option is possible” care of Avida.
Salvador
Comment by Salvador T. Cordova, IDEA GMU — July 7, 2006 @ 2:51 pm
Jonathan Bartlett wrote:
“They admit to it in their paper”
Admit to what? That their model, like natural selection in the wild, simply builds on previously existing adaptations? You have deliberately evaded pointing out how the Avida software had a pre-ordained end state built into it. Not surprising, since it did not.
If you wish to assert something to the contrary, simply copy and paste from the software listing (it’s at the link that Richard Hoppe provided, above), and let us all see for ourselves if your assertion is true. If you cannot do this, we must perforce assume that you either fundamentally misunderstand how the software carries out its functions, or you are deliberately trying to mislead the readers of this forum.
Comment by Allen MacNeill — July 7, 2006 @ 2:52 pm
Mr. Bartlett, you need to read Sal’s claim and RBH’s response more carefully. Then point to the part in the code which “captures the assumption” that “irreducible complexity” can be achieved through co-option.
Try to avoid making a vapid statement along the lines of “Just because you can select for antibiotic-resistant bacteria doesn’t prove that bacteria can evolve antibiotic resistance because the design of the experiment captures the assumption that bacteria can evolve antibiotic resistance.”
Comment by Susan Percell — July 7, 2006 @ 3:20 pm
Strawman. They never claim to be precisely modelling “real biology”.
Comment by Don Baccus — July 7, 2006 @ 3:27 pm
How does one tell Avida that a feature is selectively advantaged? Answer: put it in the parameter file.
Are you suggesting that models of natural selection must function without selection? Please pardon me if I don’t take you seriously.
NO calculation is done whether such a feed back loop is even feasible in physical reality. Just assmume a value which will help one arrive at the conclusion one wishes to assert.
Meanwhile, many creationists assert that the existence of such feedback in natural selection as so obvious that they refer to it as tautology.
Clearly, there is no pleasing them, and there is no limit to the depth of the intellectual sewer one must swim to maintain the ID position.
Comment by ivy privy — July 7, 2006 @ 3:46 pm
Having myself now violated the ground rules for this forum, despite my best intentions, this thread is now closed. Any new comments posted to it will be deleted.
Next time let’s try to do a little better.
Comment by Allen MacNeill — July 7, 2006 @ 4:59 pm