Design Challenge Results: “Evolution is Smarter than You Are”

| 164 Comments

They came for a contest that might someday be viewed as a pivotal moment in the eternal conflict between Darwin and Design.

On one side were the Intelligent Designers. They came from California and Alabama, New Mexico and England, Finland and the Netherlands, and from all around the world. They came from academia, and from industry, and from the armed services. They came armed with computer spreadsheets, home-made programs, graph paper and calculators. They applied trigonometry and calculus, intuition and insight, knowledge of minimal soap films and surface tension, database optimizing algorithms and random searches, and other techniques available only to Intelligent Designers. And they strived to answer the tricky question “What is the Steiner Tree (smallest possible network of straight line segments connecting six given points) for the network shown in “Take the Design Challenge!”

smalGrid.gif

On the other side were Evolutionary (or Genetic) Algorithms, in which herds of digital organisms were bred over many generations. Each organism was a string of numbers and letters, which were “transcribed” by fixed rules as representing some of the billions upon billions of possible candidate networks for the given problem. Those organisms whose lengths were smaller gained a slightly better chance at being a parent of one of the organisms of the next generation, and mutations of the strings were allowed to happen occasionally. In this process, no trigonometry or calculus was required. No information about characteristics of Steiner Trees was necessary. But, as the strings competed with each other, marvelous and unexpected designs began to appear.

critters.gif

Although most of the Intelligent Designers were not members of the “Intelligent Design” movement, which had been officially invited to respond, the ID community did indeed weigh in, via the efforts of Salvador Cordova, one of the IDers running the show at William Dembski’s blog Uncommon Descent.

So, what is the Answer? Did Salvador do better than Darwin? Did our team of Intelligent Designers find the True Steiner, or did they, like the evolutionary algorithm, find “MacGyver” (not-quite-perfect-but-extremely-functional) solutions also?

Readers, let’s enter the Design Room and meet our Winners!

Let’s waste no time in meeting some of the entries that were closest to the actual Steiner Tree for the given six points.

One of these was generated by an assistant professor of mathematics and computer science at a major state university, and the other was generated by the Genetic Algorithm I discussed back in July.

design1.gif

design2.gif

The interesting question now is, how can the Intelligently Designed answer be distinguished from the Evolved answer? Neither design is the exact Steiner solution, because one of our Designers might have rounded off too soon in his calculation, or perhaps mis-typed something somewhere along the line. If someone had access to the exact solution, they might be tempted to rule anything else out as “not designed.” But that’s not fair, according to Jonathan Wells’s new book, The Pig Ignorant Guide Politically Incorrect Guide to Darwinism and Intelligent Design, where on page 87 (Chapter 8), Wells writes

Nor does intelligence imply perfection. Some Darwinists criticize intelligent design on the grounds that some features of the natural world could have been made better. In other words, they argue that if something is not optimal, it is not designed. But things can be designed without being optimally designed. An automobile that is constructed in such a way that its fuel tank explodes whenever another vehicle bumps it from behind is badly designed, but it is designed nevertheless.

Before moving on to our other Winners, I’m issuing a Second Challenge, again open to all: using whatever ID theory you need (Explanatory Filter, Design Inference, whatever), show how this theory can be applied to the above two solutions to determine which was actually designed (e.g. “real” Complex Specified Information (CSI)), and which was evolved (and thus in possession of only the “appearance” of CSI).

Anyone can enter, but unlike the previous challenge, all contestants are asked to show their work. Again, e-mail your responses me at nmsrdaveATswcp.com (please replace the AT with an @), and do not post them as comments on this or other blogs. This new contest will be open for as long as needed (i.e. until the ID community makes a formal response), as it might take a couple of years for the top ID theorists to crack the case.

Let’s move on to the the Hall of Fame, and see what our industrious, hard-working Intelligent Designers came up with. It turns out that there are actually two perfect Steiner Trees possible: in one, the hexagonal grid is twisted counter-clockwise, and in the other, clockwise. Both Steiner Solutions are rotationally symmetric: like the Queen of Spades, they look the same if you spin them by 180 degrees. In addition to finding both of these solutions, the Genetic Algorithm (GA) production run I completed before issuing the challenge (300 simulations of populations of 1000 competing for 2000 generations each) found numerous other shapes, ten of which I’ve collected as official “MacGyver” solutions. I’ve tried to pick the MacGyvers to represent the various topologies (shapes) possible, but may have missed some. Many of our Intelligent Designers independently derived MacGyver solutions. Almost all of these were also found in the evolutionary simulation (the only ones not so appearing involved the overall shape above, but with flat horizontal segments instead of tilted ones). Interestingly, the Genetic Algorithm managed to find some interesting designs overlooked by all of the human contestants.

And the Winners Are… Please - if I’ve made any mistakes in the following, do let me know and I’ll make corrections. There were so many entries, it became hard to keep track of them all!

The Exact Steiner Tree

steiner.gif

Kudos to George Atkinson, Bram de Beer, Paul Flocken, Virgil Keys, Alex Labram, Mike McCants, Ray Spurlin and Kim Van der Linde for nailing it, and showing us that the answer to this tricky problem can indeed be obtained via Intelligent Design!

All of these contestants came up with answers at or very close to the actual minimum length, 1586.53 units.

Congrats also to Kari Tikkanen for getting very close with the basic network, but with horizontal lines for the two long sideways-going segments; this length is also excellent (about 1591 units). Paul Flocken also designed this answer, but also kept after it until he acheived the true Steiner above.

Congrats also to those who simply visualized what the solution should be, qualitatively. That’s actually the hardest part of the problem, and kudos go to Bryan, Wes Elsberry, Dave Havlicek, Myron Souris, and Roy Thearle.

Additionally, Julian Onions also found the true Steiner, but did so with his own home-brewed Genetic Algorithm, thus providing independent confirmation that evolutionary processes can produce Designs.

While several Intelligent Designers found one or the other Steiner, it’s of interest to note the Genetic Algorithm found both. GAsteiner1.gif GAsteiner2.gif

First MacGyver

GA_Mac1.gif My first calculations for this curious shape led me to think it was the Second MacGyver, when in fact it was the First. My apologies to those contestants whom I confused with this error.

Kudos for finding this solution go to Roy Thearle, Ray Spurlin, Duncan Buell, Kevin Vicklund, Matthew Vonk, and Salvador Cordova (our official IDM respondent). At a length of 1596.3 units, this shape is only 0.6% longer than the formal Steiner solution!

It is of interest to note that Salvador’s first response was simply a drive-by URL drop on August 15, 2006 at 08:59 AM. Then, Salvador derived the “double bowtie” (Tenth MacGyver) over at UD on August 15, 2006 at 6:31 pm.

Cordova found a qualitative version of the above solution (First MacGyver), at UD on August 15, 2006 at 11:12 pm. After four more days of effort, Sal finally achieved the First MacGyver (and all four versions, too) at UD on August 19, 2006 at 5:04 pm.

While I appreciate his participation, this of course leads to some interesting new questions for Mr. Cordova. The first is, why did Salvador go the conventional route, finding web pages that discussed Steiner Trees or Fermat Points, and using trigonometry and algebra, like our other Designers? Why didn’t Salvador instead simply go get the answer from the Fortran listing of my genetic algorithm, as he said he could do in his Panda Food post:

Here is one of the many places where Dave sneaks the answer in: Dave Thomas’s Code Bluff

This is especially ironic because Cordova claims that my Steiner GA is just “theatrics,” and equivalent to his so-called “Genetic Algorithm” for summing integers. Although Salvador insisted that “The solution was never explicitly stored anywhere” in his summing algorithm, I was able to show exactly how Cordova “front-loaded” his algorithm with the specific solution desired. I did not simply go out and look up the formula N(N+1)/2 in a book - I reverse engineered Cordova’s Code to see how his answer was sneaked in. So, if I’m sneaking in the answer(s) with the Steiner GA, exactly where is that front-loading being performed?

Another question. Salvador, if we gave you a tee shirt with a bullseye on it, and told you to wear it so that you could find and shoot yourself in a game of paintball, would you be still be able to hit the Target?

My last question for Mr. Cordova is: what is it going to be like having to go to Bill Dembksi and admit that you’ve learned the hard way of the true meaning of what Daniel Dennett terms Leslie Orgel’s Second Law: “Evolution is smarter than you are”? Even after a week’s worth of effort, you still couldn’t find the correct Answer. You were close, but it’s Charlie Darwin (along with some very Intelligent Designers) who got the cigar. I predict there’ll be some ‘splainin’ to do backstage at Uncommon Descent.

Second MacGyver GA_Mac2.gif

Unlike the First MacGyver, the Second MacGyver has eye-pleasing symmetry, and was engineered by several of our industrious Intelligent Designers. At a length of 1619.7 units, it is but 2.1% longer than the optimal Tree. Kudos to Ron Bear, Matt Brauer, Duncan Buell, Reed Cartwright, Otto Froehlich, I.R. Pen, John Shipman, Lance Stewart, and Kevin Vicklund..

Third MacGyver GA_Mac3.gif Only Darwinian processes found this optimal form of curious shape, weighing in at around 2.3% longer than the formal Steiner. However, Andrew McClure ran a Random Search algorithm for 24 hours, and found a topologically-correct (but severely distorted) version of the Third MacGyver on the 3,191,313th iteration.

Fourth MacGyver GA_Mac4.gif Again, only the Genetic Algorithm found this odd shape, coming in at 3.4% longer than the best solution.

Fiifth MacGyver GA_Mac5.gif This pretty bilaterally-symmetric design was found by the GA, and also by Kevin Vicklund, and is 4.2% longer than the ideal tree.

Sixth MacGyver GA_Mac6.gif Only the GA found this artistic rotationally-symmetric shape, at 5.3% longer than the official solution.

Seventh MacGyver GA_Mac7.gif Again, only the GA found this odd shape, at 5.7% longer than the optimum.

Eighth MacGyver GA_Mac8.gif This solution was derived by Reed Cartwright and Kevin Vicklund, and is 7.2% longer than the formal answer. There are several equivalent networks, forming an M or W instead of an S, and all with length 1700. A horizontal line through three verticals would also yield the same length (kudos Kim Johnson. Many of these fit the “Traveling Salesman Problem” class of solutions (i.e. having no internal “Steiner Points” for making connections).

Ninth MacGyver GA_Mac9.gif

Again, only the GA found this curious tree, at 13.5% longer than the Steiner.

Tenth MacGyver GA_Mac10.gif

This elegant design was found by Kevin Vicklund, who, while not getting the Steiner itself, is commended for finding five different MacGyvers. Evolution may be smarter than Kevin, but Kevin is doing a great job catching up, and is hereby named the Master of MacGyvers for this contest! Credit also to Salvador Cordova for finding this shape as his first serious attempt, as was mentioned previously.

I got into the six-point problem by trying to find the network that could produce the Double Bowtie as its Steiner Solution. Without giving the matter a great deal of thought, I started a simulation to look at the six-point problem, figuring that I might get lucky and snag a Double Bowtie or two from the run. But, when I sat down to review the solutions, the Double Bowtie was nowhere in sight. In fact, to get the image of the Double Bowtie shown above, I had to deduce its DNA pattern and feed it directly into my plotter routine. I had to chuckle at myself when I realized that at 1839.2 units in length (almost 16% longer than the optimal solution), the Double Bowtie would always be out-competed by shorter, tougher MacGyvers.

However, looking over the simulation results, I noticed that the best answers indeed came from a mutated version of the Double Bowtie, in which the four segments connecting the middle two points (2 and 5) could be replaced by only three segments in the shape of a dog-leg, and that this could be realized by tilting both Bowties at a slight angle, either clockwise or counter-clockwise. And so I learned that Evolution is smarter than me, too. Once I stopped chuckling, I realized that this was an excellent example of a problem with no obvious answer, and a good candidate for the Design Challenge, which followed shortly thereafter.

Honorable Mention

Kim Johnson derived “The Asterisk,” in which two long diagonals and one vertical all meet in the center of the figure, forming an asterisk shape. This has length 2009 units.

And Rupert Morrish sent in this whimsical answer: ID6nodeGrid.gif

CONCLUSION

In The Pig Ignorant Guide Politically Incorrect Guide to Darwinism and Intelligent Design, Wells writes

Ferry passengers entering Victoria Harbor in Canada are greeted by a bank covered with flowers that spell out “WELCOME TO VICTORIA” in large letters. Everyone who sees the greeting knows immediately that it was intelligently designed.

Likewise, anyone who comes across one of the Steiner or MacGyver designs shown in the Design Room would probably infer design, especially if they knew of the effort required to derive such designs. But, given that these “designs” can also be found simply by breeding herds of alphanumeric strings, it becomes clear that evolutionary processes can also produce the appearance of design.

To those Designers who found “MacGyvers” instead of the official Solution - pat yourself on the back. You have helped to show that the McGyver solutions are Complex Specified Information in their own right.

Expect to see more of the typical ID/creationist reactions to these results. We will hear (again) that the GA won’t run if program lines are switched or mangled randomly, as if this means anything. I mean, really - if all the oxygen atoms in the world were suddenly replaced with sulphur atoms, wouldn’t Life cease immediately? And the point is…?

When I showed this algorithm to William Dembski in 2001, he dismissed it as mere “frontloading” of the answer via the GA’s fitness function. But what such “frontloading” really entails is the erroneous belief that simply Asking a Question is sufficient to produce the Answer. We all know from personal experience that not all Questions have obvious Answers.

And, we’ve learned this past week that answers to the question “What is the Steiner Tree for a given network?” are anything but obvious. Thanks to all of the many contest participants who sent in their designs. You have participated in a unique experiment that puts Darwin and Design to the test under precisely controlled conditions. I appreciate and applaud your earnest efforts!

P.S. Contestants, if you are feeling a need for some new puzzles to engage the ol’ brainpan, check out the Pirate Chest Challenge over at NMSR.

164 Comments

Yeah, an evolutionary biologist working in intelligent design.… This problem was quite easily to do with an excel spread sheet, and realizing that the problem can be reduced to half a problem as the starting point is symmetric. It would become rapidly impossible to solve it in such a way when the symmetry is broken, or when the number of line elements is increasing.

Mr. Thomas!

Kudos to you! This series of posts, for me, was spellbinding. I’ll admit that I await, with baited breath, the response by Salvador. I hereby predict that Salvador will attempt to dismantle your code and show it doesn’t work when a particular part is removed. This, of course, will be his evidence that you frontloaded an answer. This avoids him actually having to prove (show) where the answer is and demonstrating that you have frontloaded the code.

He has already stated that the code wouldn’t exist without you, therefore the natural process that it is designed to demonstrate must be intelligently designed. Even to a rookie like me, this argument is ridiculous. Your code attempts to copy an observed natural phenomena (RM +NS). According to his logic any program that simulates a observed natural phenomena, like the law of gravity, demonstrates the law of gravity is intelligently designed.

Well done!

Kim said:

This problem was quite easily to do with an excel spread sheet, and realizing that the problem can be reduced to half a problem as the starting point is symmetric.

I am not following. Isn’t the exact Steiner solution asymmetric?

NNNEEERRRDDDSSS!!!!!!!

ofro Wrote:

I am not following. Isn’t the exact Steiner solution asymmetric?

Well, I came to the exact value using symmetry, so no, not in this case. Which is of course logical as the starting point is symmetric.

ofro Wrote:

Isn’t the exact Steiner solution asymmetric?

It is symmetric under a 180 rotation around (400,150), the “center” of the six points given.

If you assume (prove?) that then the problem reduces to a four-point one. (3 original, e.g. the two left and the top-middle, plus the “center”.)

Well, I don’t know if the true Steiner Tree is symmetric (though it’s probably a safe assumption), but the symmetry (or lack thereof) of a given solution is (I think) a big clue as to whether or not that solution was designed by a person, as opposed to a GA.

Excellent posting. Sal is often quick to make assertions but often very slow to support them in any manner, exhibiting the typical scientifical vacuity of Intelligent Design. As for Wells… Sigh, it seems his latest book is not much better than his ill fated Icons…

Ian Menzies wrote

Well, I don’t know if the true Steiner Tree is symmetric (though it’s probably a safe assumption), but the symmetry (or lack thereof) of a given solution is (I think) a big clue as to whether or not that solution was designed by a person, as opposed to a GA.

The True Steiner is rotationally symmetric, like a playing card, as noted above.

Symmetry is nice, but is found in many MacGyvers, as well as the actual Steiner itself (see the Second, Fifth, Sixth, Eighth and Tenth MacGyvers for examples).

Dave

ofro Wrote:

I am not following. Isn’t the exact Steiner solution asymmetric?

No, as near as I can tell with the Mark I Eyeball, the exact Steiner solution exhibits odd symmetry. That is, you can rotate it 180 degrees and it will look the same. Most people think only of even symmetry (also known as mirror symmetry) when symmetry is discussed.

I admit, I did not formally submit all of the solution families I considered, mainly because I already knew that a shorter solution existed.

The ones I considered but did not formally submit were the 3rd, 7th, and 9th (or variations thereof). One thing of note is that the 5th solution family actually consists of 4 unique solutions and a total of 12 solutions, IIRC.

I also visualized the Steiner Solution (by twisting the 2nd), but couldn’t figure out a way to calculate the actual points using graph paper, pencil, and simple geometry and trigonometry (note, I didn’t even use a straightedge!). My problem? Too many variables. My solution would have been to create some 120 degree Y’s and arrange them on the page until they all lined up - a rather Darwinian process.

Anyway, I’m going to pop in the first season of MacGyver this week to celebrate.

Thanks, Dave, for having provided such an amusing way for wasting part of my weekend! :)

If anyone is curious, the random search program I wrote is at:

http://vote.grumpybumpers.com/tornado.txt

And a second script for turning its results into animated GIFs is at:

http://vote.grumpybumpers.com/gif-tornado.txt

I figured that as long as we were having a contest between evolution and design, it would be fun to submit a solution on behalf of the proverbial “Tornado in a Junkyard” which serves as a straw man of evolution in so many creationist arguments. So I wrote a program which was as close as I could figure to the “random search” algorithm which, in Dembski’s writings about the “no free lunch” theorems, we are given the impression that evolution is incapable of performing better than at solving problems. The program repeatedly generates entirely random attempts at a Steiner solution using a method of construction and “fitness function” similar to Thomas’ FORTRAN evolution program, keeping a running record of the best solution it has found so far as it goes. The program is also written in Perl, which itself tends to resemble a tornado in a junkyard.

You can see the progress of the program in this animated GIF, which has one frame for every time the random search found a new minimal proposed solution:

http://vote.grumpybumpers.com/tgif2.gif

The final frame shows the best proposed steiner solution the tornado program ever found. (I’ve still got it running, actually, but it never did find a solution better than that one.) This “solution” is 1674.3 units long, which incidentally is poorer performance than Thomas’ evolutionary algorithm achieved either overall or for the specific graph topology that the tornado solution represents– even though Thomas’ genetic program only ran for about 200 generations to find that solution, and the tornado search has been running for over a full day. This should of course be no surprise to anyone with the slightest amount of familiarity with algorithms. Whether it would be a surprise to a reader of Dembski’s “no free lunch” is another question :)

Dave, are you going to release the new code?

Also, do we get a chance to see soap film solutions?

It should be noted that I submitted both symmetric and asymmetric solutions. Symmetry is not a reliable indicator of intelligence in this case.

Dave, thanks for an intriguing and illuminating puzzle.

I found the tenth MacGyver early on when attempting to solve the problem by reduction - two four node trees. As a designer, I realized quickly that removing just one of the connections to either center point would result in a significant reduction in line length. I would expect evolution to find this solution earlier on, as it has no built in bias towards symmetry, as many of us humans do. Of course with pressure to reduce total line length, it would also be discarded soon after in favor of better answers. It did in fact lead me to the first MacGyver solution and ultimately to the actual answer.

Regarding symmetry, the actual Steiner solution can be flipped vertically about the horizontal centerline with no change in total line length. The diagram above seems to indicate differently. Likewise, the first MacGyver can be flipped about either the horizontal centerline or the vertical centerline yielding 4 equivalent solutions. I wonder if in Dave’s genetic code they could interbreed or would they be an example of speciation?

It is point symmetry, also resultng in rotational symmetry. What is important, is that if you know that single point (in the middle between the mid points), you only have to calculate the distances of one halve to get to the answer.

Kevin Vicklund wrote

Dave, are you going to release the new code?

Sure, why not! I’ve placed the code on PT, here, putting the date as way back in July so as not to clutter up the PT main page. (But it might confuse time-travellers!)

Also, do we get a chance to see soap film solutions?

I haven’t made any for the 6-point problem. None of the contestants reported trying that either. My guess is that Salvador doesn’t like going to the Lab - it sure would have been an easy way to derive the Solution.

It should be noted that I submitted both symmetric and asymmetric solutions. Symmetry is not a reliable indicator of intelligence in this case.

Agreed!

Dave

Dave,

Congratulations! An absolutely superb and challenging experiment. And funny too. ;-)

Marshall

Dave Thomas: This was well done, indeed! I encourage making comparisons between GA and RA(Random Algorithm) by the number of generations multiplied by the number of individuals versus the number of random attempts for a solution. Not only does this seem ‘fair’, but it is enough to demonstration how quickly GA develops a ‘good enough’ solution in comparison to RA’s stumbling in the dark…

Dave, would you please provide a very careful, concise and clear list of exactly which point or points in the evolution/creation debate this demonstration was created to address?

I was browsing the UD weblog and from comments I saw there you run the very real danger that your GA will run into the same misinterpretation/ misrepresentation problems as Dawkins’ “Methinks it is Like a Weasel” algorithm: namely, that people will attempt to claim that it is supposed to prove points, or simulate situations, that you never intended.

The problem with this is:

1) It is easy for opponents to obscure the points you are making by bringing in irrelevant scenarios. 2) If an opponent can show that your GA is simplistic or unrealistic for their artificial scenario, then they can dismiss all of your demonstration without addressing the specific points you make (essentially using your demonstration as their straw man).

I am not sure I understand why it is fallacious to build the “Answer” into the fitness function. If you’re level of “fitness” is defined as the extant at which you match the phrase “WILLIAM DEMBSKI IS A BOOB”, then isn’t it appropriate to save that phrase as a constant somewhere and compare strings at each generation in order to judge your level of fitness?

Frank, the idea is to show that a dumb algorithm can come up with a specific, hard-to-find solution. IDers say that Dawkins’s WEASEL program is cheating because the answer is built into the program, which of course it is. Dave’s program addresses that complaint.

Weka, Frank, this post is a continuation of a thread started earlier this summer, Target? TARGET? We don’t need no stinkin’ Target!

The purpose of the “Target” post was simply to show that Genetic Algorithms can produce elaborate designs without anything like the actual form of those designs being fed into the fitness test.

As explained there, IDers and creationists alike have all latched onto Dawkins’ “Weasel” algorithm as evidence that all genetic algorithms need to have the final answer snuck into the fitness test. You’ll find several references of exactly that happening in July’s “Target” post. It’s not just creationists, but ID stalwarts like Meyer and Dembski too.

So the “strawman” I’m going after is the undeserved “guilt by association” linkage of any and all GA’s with target-specific simulations like “Weasel.”

The second major aim of this work is to directly address the ID claims that any novelty produced in a Genetic Algorithm is “frontloaded” in the algorithm itself. If such “frontloading” was being done in my Steiner GA, then anyone looking at the source code should be able to determine where the algorithm will go. Not one person from the ID community stepped up to demonstrate this.

And the third aim was to provide a Test for the detection of “real” versus “apparent” CSI. If Intelligent Design Theorists can indeed identify when something has or has not been “designed,” as they claim they can, then they should get cracking to decide which of the two networks shown above (just below the fold) was produced by a human Intelligent Designer (a college computer sci prof, by the way), and which was produced by simulated mutation and natural selection on a population of strings over many generations.

I hope that helps.

Dave

Well done, Dave.

But I think the IDer’s complaint that the Steiner solution is prebuilt is to some extent valid. There exists a unique global minimum (but not necessarily a unique configuration of the tree) for the problem. Thus, the GA will always tend towards that solution.

May I propose a defeater to the “front-loading” argument? Allow your metric to vary subtly per generation of your GA. One simple way to extend it is to vary the exponent of your distance metric according to, say, a Gaussian distribution, centered about 2. In other words |x-y| = sum (xi-yi)^p, where p is a random variable with mean of 2. You can further complicate the problem by introducing uncertainty in the locations of the terminal points.

Now, there is no fixed landscape for which a unique fitness value describes all global minima. Would the GA still tend towards the exact SMT? I suspect it would… or perhaps additional behaviors might manifest, such as the GA alternating between configurations that tend to be robust for extremal cases.

Whoo! I found the first MacGyver, but I never sent it in because I wasn’t able to figure out the length exactly.

Dave, I am a software engineer and am very interested in playing with the code. You posted SteinerGAdlg.cpp code, but without the header files and resources it is not easy to recreate, and being the lazy guy that I am, I am not willing to spend the few days it would take to reverse engineer the code. Is there any way for me to get the complete code? Either way, thanks for listening.

Tulle wrote

Dave, I am a software engineer and am very interested in playing with the code. You posted SteinerGAdlg.cpp code, but without the header files and resources it is not easy to recreate, and being the lazy guy that I am, I am not willing to spend the few days it would take to reverse engineer the code. Is there any way for me to get the complete code? Either way, thanks for listening.

Not out of the question, but I would be reluctant to release the entire code in its present form. It’s got some non-standard stuff, such as writing the best of every nth generation off to a text file in folder C:\dt\text for subsequent review of the results of an all-night run in just a few minutes. But, if you don’t have that folder on your box, it Bombs. When I get it more user-friendly (for example, a File button to let you choose an output file name if desired), I might be willing to let it out the door. It does currently have all sorts of nice GUI features, like reading/writing problem geometries, editing and/or mouse-digitizing same, etc., but there are still too many undocumented features for me to let it out the door. Empty nest syndrome? Maybe. But the C++ listing covers everything needed for the GA itself, so you could certainly try to implement some of that in your own testbed, as Julian Onions did with his.

Give me a week or two to ponder/clean up/etc.

Dave

Please forgive me. I just finished reading the “Target? TARGET? We don’t need no stinkin’ target!” post, including the explanations you quoted from John Bracht, and while I appreciate that you are going through all the trouble to jump through the hoops that the ID’ists are throwing at you (I’m truly impressed by all of this), I still cannot understand what their complaint is.

It seems to me like they want to remove anything resembling a fitness function from the program. But if you do that, then all you have is randomness, without anything simulating natural selection. Am I erecting a straw man here, or are they that stupid? Of course, in order to simulate Evolution, you MUST have some function that is capable of SELECTING those organisms which are the “fittest.” Complaining about the 5-point Steiner program because it, “[selects] for networks that (1) connect all five points, and (2) have shortest path-length” seems, to me, like complaining about Alaska because it selects for organisms that (1) are white, and (2) have fur and layers of fat to keep them warm.

I don’t even fully understand why targeted GA’s are a problem, even after Dawkin’s explanation of it. I’m not saying they’re NOT a problem; just that I can’t grasp why.

Hmmm. No trackback, no triumphalist crowing?

Where’s the brilliant engineering squad at UD?

Anything to say, Sal? Anything at all? Or are your thoughts no more profound than the sound I hear, which is the proverbial crickets chirping?

I’ll bet your pocket protectors are overstuffed. Goddamned nerds.

Lurker Wrote:

But I think the IDer’s complaint that the Steiner solution is prebuilt is to some extent valid. There exists a unique global minimum (but not necessarily a unique configuration of the tree) for the problem. Thus, the GA will always tend towards that solution.

It is trivial that the GA will *functionally* tend towards the formal solution. But in this case, the “function” is simply to be short, i.e. to save energy. Could you show that the GA will also *structurally* tend towards the formal solution? I don’t think so. Instead, the MacGyvers show great diversity both in the detailed structure of the solution (“phenotype”) *and* in the respective “DNA”. Even when static, the fitness landscape in this demonstration is hardly one giant hill.

P.S. The “spin” of subatomic particles is a fundamental physical attribute, distinct from the fundamental physical attribute of charge. Electrons and positrons both have spin of 1/2.

For the 6-node problem discussed here, there are indeed two unique Steiner solutions. Each is rotationally symmetric (like a playing card), but each has different handedness.

OK, fair point, I didn’t think that one through properly. Would be interesting to figure out some way to characterise the Steiner points of an arbitrary network - I have a sneaking suspicion that there’s some sort of number-theoretic way of handling this.

Re “Electrons don’t left and right sides, so mirror-imaging them wouldn’t change anything … certainly not their charge.”

Not right/left, true. But I don’t know if they might have geometric distinctions (from positrons) in some other dimension (not one of the four we can detect directly). I don’t know enough physics to judge that offhand.

Henry

Henry:

“But I don’t know if they might have geometric distinctions (from positrons) in some other dimension (not one of the four we can detect directly).”

According to string theory they have, and some of them may be large (brane worlds). But I doubt a rotation affects this.

Spin is basically a topological effect with no left/right problem, if I understand correctly. (See Popper’s comment.) But there are P (and CP) violations, so parity has a small effect from geometry. A parity transformation is flipping all coordinates and that is AFAIK possible by rotations in a higher dimension. But it wasn’t done here.

Actually, I wonder if he would starve. Are proteins from right-handed aminoacids just undigestable or are they downright toxic? If so, even touching a biological material (like an apple) could have some unpleasant effects…

Of course, the story was written by H.G. Wells, who could know nothing about the assymetry of living world - I think.

They are certainly indigestible. They may also be anything else. A stereoisomer can have any chemical properties any other molecule can, relatively unrelated (biologically, their general properties will be similar).

Thalidomide, for instance, is a powerful, safe anti-nausea drug, but it’s stereoisomer causes nasty birth defects.

Maybe slightly off-topic here, but since we’re talking about genetic algorithms (apologies if posted before):

http://www.demo.cs.brandeis.edu/gol[…]s/UsNews.pdf

…[Brandeis University computer scientist Jordan Pollack] and mechanical engineer Hod Lipson run the Golem Project, a colony of machines that evolve and give birth to other machines without human guidance.”

Wonder what a cool name for their next generation project would be…hmm…oh, how about “SkyNet”? Hey, that’s a cool name!

I’m not real familiar with Steiner trees, so my question is how was the exact solution determined? Is there some type of general way to do it? How can you be sure that your best solution actually was the best solution, and that with a little more playing you couldn’t get something with an even shorter length than your 1586.53?

Syntax Error: not well-formed (invalid token) at line 1, column 54, byte 54 at /usr/local/lib/perl5/site_perl/5.12.3/mach/XML/Parser.pm line 187

Hi Dave,

Do you know of any place to find sample mutation algorithms for GAs?

It looks like your code hardcodes probabilities for certain mutations, then mutates one(?) locus at a time.

I’m trying to put together a simple GA-based program that takes a set of input bits and manipulates them into a set of (user-defined target) output bits using only NAND operators.

Not sure exactly how the “DNA” is going to look yet, but if a mutation can only replace one locus at a time, it’s going to be impossible for the GA to co-opt “groups” of operations that might serve a generally useful purpose [e.g., (a NAND a) NAND (b NAND b), equivalent to (a OR b)]. Unless I allow the reproduction mechanism to mutate, which is a bit more work than I want to do right now…

Anyway…any resources you can think of that would help me with this?

Syntax Error: not well-formed (invalid token) at line 11, column 9, byte 566 at /usr/local/lib/perl5/site_perl/5.12.3/mach/XML/Parser.pm line 187

Dave Thomas wrote:

In other words, consilience works for me.

Good enough for me, too. Just to clarify - my original e-mail wasn’t meant to be hostile at all, it’s just that the couple Steiner series posts I’ve read of yours are extremely interesting, and piqued my curiosity.

Dave,

You inspired me to develop a genetic algorithm engine to solve the Steiner Problem you described. I went through your three articles, making copious notes, then spent an afternoon building the core functionality. I tried it out on the six node challenge problem and consistently got solutions with a segment length more than 400 longer than the Steiner solution.

Over the course of the past week I’ve spent an hour or two every day adding to my engine, implementing more sophisticated crossover, trying alternative selection techniques, changing the encoding of variable node positions from standard binary to Gray code, and running test after test. Still, my evolved solutions remained stubbornly 30% longer than yours.

I was getting concerned. Had you, no doubt unknowingly, introduced information about the solution in your encoding of the problem? Was this a potential source of embarrassment for The Panda’s Thumb? Did I have an ethical obligation to publish my results?

Before contacting you with these questions, I went back once more to the original articles. It turns out that I’d written down the wrong value in one section of my notes. I have been hacking furiously in an attempt to get the fitness of my solution to the six node challenge problem down to that of the five node example you’d provided. In fact, my engine had been generating Steiner solutions and MacGyvers all along, even in its most naive implementation.

The code is available if anyone is interested in having a look. I used a simple binary string rather than your more complex encoding. My first version allowed the number of variable nodes to mutate, but as you also reported, this leads to local optima with no variable nodes.

Thanks for the interesting puzzle.

Regards,

Patrick

Dave Thomas Wrote:

As regards “global” versus “local,” I don’t have the foggiest notion of what you’re referring to. In the GA, an organism is represented by a DNA string, period.

OK, I get it now. The Steiner Solution itself is the Global Minimum (for length), while the numerous MacGyvers represent Local Minima. Indeed, there can be large gulfs between the DNA of organisms parked at local minima. The double bowtie (MacGyver #10) is genetically much different from the actual Steiner solutions, wherein two bowties are twisted and mutated to form the central dog-leg junction-of-bowties. That’s a “macromutation,” I guess.

Dizzy, the program allows both a number of organisms to mutate per generation (typically 50 of 1000), and also a number of mutations per organism (usually three per creature). Thus, it’s not just single-locus mutations; each creature that is to be mutated is hit three times, not just once.

Jeff, no hostility was detected. I was just trying to make the point that we’ve collectively gotten the real solution to the given problem.

Patrick, excellent work! That’s a third independent confirmation.

I’m closing comments on this post, but stay tuned for a follow-up post, “Genetic Algorithms for Uncommonly Dense Software Engineers.”

Thanks for a great discussion! Dave

About this Entry

This page contains a single entry by Dave Thomas published on August 21, 2006 10:45 AM.

Hold the presses: Collins is being used was the previous entry in this blog.

Live discussion at IslamOnline.net is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.

Categories

Archives

Author Archives

Powered by Movable Type 4.361

Site Meter