Thursday, July 06, 2006

Doggies are Better than Weasels



AUTHOR: Dave Thomas

SOURCE: Target? We don't need no stinking target!

COMMENTARY: Allen MacNeill

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, Thomas first shows the classical solution to a five-node traveling salesman problem (TSP), as demonstrated by the Swiss mathematician 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 the ongoing debate over design in nature, as exemplified by Richard Dawkins' book 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 about design in nature 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.

FOR FURTHER READING:

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, check out Avida.

--Allen

Labels: , , , ,

2 Comments:

At 7/06/2006 04:50:00 PM, Anonymous Dave Thomas said...

Thanks for the kind words, Prof. MacNeill.

I'm not so sure that what I did was exactly like the traditional Traveling Salesman Problem (TSP), which does not allow the extra "variable" nodes I used to develop networks for solving Steiner's problem, as far as I know. (If that's incorrect, let me know!)

Now, one of the 'MacGyver' networks that evolved from the brew had no extra nodes, but only segments between the 5 "cities," and as such could be considered a solution to the TSP for those nodes.

The important point is that neither genetic algorithm (TSP GA for 'fixed' nodes only, or the Steiner GA for fixed + variable nodes) requires specification of a "target" of the actual solution; rather, the environment itself influences which solutions are found, through selection, mutation, and reproduction over an extended time.

Thanks again, & regards from New Mexico,
Dave

 
At 10/24/2006 05:49:00 AM, Blogger BC8 said...

Interesting blog.

I did have one comment. The algorithm is not a solution to the "travelling salesman" problem. The travelling salesman problem is to find the shortest route through all the points (i.e. draw a *single* line through all points - just think about connecting all the dots with a pen, but you aren't allowed to pickup the pen until all dots have been reached).

You can think about Dave Thomas' algorithm as finding the shortest combined length of *one or more* lines which connect all points. It's sort of like connecting all the cities together with roads while trying to lay as little pavement as possible.

 

Post a Comment

Links to this post:

Create a Link

<< Home