Evolution Icon Evolution
Intelligent Design Icon Intelligent Design

Steiner Wars: An Exchange with Dave Thomas

Over on Panda’s Thumb, Dave Thomas has written a post, “Target? TARGET? We STILL don’t need no stinkin’ Target!” He responds there to my discussion of his Steiner tree evolution simulation in my papers “Digital Irreducible Complexity” (written solely by myself) and “Climbing the Steiner Tree” (written with Dr. Robert Marks and Dr. William Dembski). He attempts to argue that his simulation falsifies irreducible complexity, and that my papers are nonsense. He is, in fact, incorrect.

Before getting to that, what is a Steiner tree? To visualize a Steiner tree, think about a collection of cities. All of the cities need to be connected by a road network. However, we want to connect the cities using the fewest miles of road possible. We could build roads directly from one city to another. However, the optimal solution (the one that requires building the fewest miles of road) will often require building interchanges outside of the cities. Thomas’s simulation takes a collection of cities and evolves the road network. It does not usually find the optimal road network, but it does typically find one that works “well enough.”

In both of my papers, I argued that Thomas’s model does not evolve an irreducibly complex system. Thomas disagrees:

True Steiner solutions are not only Irreducibly Complex, they have Complex Specified Information, as they are specific solutions of an NP-hard math problem. But Ewert simply discards the requirement that the network be minimal length, and substitutes a far easier problem, Minimum Spanning Trees. Since random chance selections can happen upon Minimal Spanning Trees fairly easily, Ewert says the solutions are thus trivial, and thus not really “irreducibly complex” as per Behe’s concept.

Firstly, as I have repeatedly stated, specified complexity requires the calculation of probability according to the mechanism hypothesized to be in operation. Complex Specified Information is merely defined as at least 500 bits of specified complexity. Under Thomas’s simulation, the optimal solution evolves 0.5 percent of the time. This is fewer than 8 bits of specified complexity. Consequently, the Steiner tree is not an example of Complex Specified Information. Thomas appears to be saying that it would have a large amount of specified complexity under a uniform random hypothesis, which would be true. However, that is irrelevant.

Secondly, it simply is not true that I’ve substituted an easier problem. There is nothing in either paper that comes even close to an attempt to justify or make such a substitution. My discussion of irreducible complexity for these algorithms does not pertain to the minimum spanning tree at all. Our paper “Climbing the Steiner Tree” discusses the minimum spanning tree; however, it is used as a baseline for success, not a replacement. Later, we’ll look at this point in more detail.

Thirdly, of course I discard the requirement that the network be of a minimal length in the context of irreducible complexity. Irreducible complexity is defined in terms of whether not a system “effectively ceases to function.” Irreducible complexity does not care how optimal a system is. It does not matter how short the road network is. Irreducible complexity is only concerned about whether or not it works at all. So, what matters for irreducible complexity is not how easy it is to obtain the optimal Steiner tree, but any connecting network. Since obtaining a connected road network by chance is relatively probable, it is not an example of irreducible complexity.

Throughout my discussion, I refer to networks as Steiner trees despite the fact that they are not in fact the solution to the Steiner tree problem. The Steiner tree problem asks for the shortest network, and so any non-optimal network is not the solution. Throughout my papers, I refer to possible solutions as Steiner trees whether or not they are optimal. When referring specifically to the optimal Steiner tree, I describe it as such explicitly. Thomas appears to insist that only the optimal solution is properly described as a Steiner tree.

However, my usage is consistent with the literature. It is common to describe the optimal Steiner tree as the optimal or minimal Steiner tree, and refer to various non-optimal Steiner trees simply as Steiner trees. As a sample, see how the term is used in the following papers:

  1. Jesus M, Jesus S, Márquez A. Steiner Trees Optimization using Genetic Algorithms. 2004.

  2. Ding S, Ishii N. An online genetic algorithm for dynamic Steiner tree problem. 2000 26th Annual Conference of the IEEE Industrial Electronics Society IECON 2000 2000 IEEE International Conference on Industrial Electronics, Control and Instrumentation 21st Century Technologies and Industrial Opportunities (Cat No00CH37141). IEEE; pp. 812-817.

  3. Julstrom BA. A scalable genetic algorithm for the rectilinear Steiner problem. Proceedings of the 2002 Congress on Evolutionary Computation CEC’02 (Cat No02TH8600). IEEE; 2002. pp. 1169-1173.

Thomas claims that I’ve replaced the difficult Steiner tree problem with the relatively easy minimum spanning tree problem. The two problems are similar, and can be visualized as building a road network among a group of cities. However, in the minimum spanning tree problem, all roads must go directly from one city to another, as there are no interchanges outside of those cities. This restriction makes the problem much easier to solve, as there is no question of where to locate the interchanges.

Why does Thomas argue that I’ve replaced the problem? Firstly, he complains that I didn’t explicitly discuss or show one of the non-optimal Steiner trees:

First, EDM’s Figure 3 completely omits the “Best MacGyver” shape with a length of 1217; in fact, this key solution appears nowhere in EDM 2012, with the exception of an un-labeled graph point in their Figure 4.

The solution in question is the second best solution, but that is no reason that I had to discuss or show it. It is the runner-up solution, and in my estimation simply not important enough to discuss.

Thomas quotes me later in the paper:

One of these solutions mentioned by Thomas [20] is the minimum spanning tree solution presented above; the other two solutions he mentions are more expensive.

Thomas’s objections here are correct, because this is a typographical error. It should have said “another two solutions” instead of “the other two solutions.” My intention was to reference two particular solutions that were worse than the minimum spanning tree, not the entirety of solutions mentioned by Thomas.

Thomas states:

I have annotated their diagram with stick figures showing the horizontal coordinates (lengths, with 1212 being the Steiner solution) and MacGyver (NON-STEINER) solutions they are discussing, as well as the elephant in the Room: the actual Steiner Solution itself, which was omitted completely from EDM’s Figure 4!

Thomas is correct that the optimal solution is missing. This was due to a bug that was discovered shortly after publication. I have published an erratum with corrected figures. The corrected figure does, in fact, contain the optimal solution.

Even granting these legitimate flaws, it is difficult to see how Thomas can draw the conclusion that my paper attempts to minimize the importance of interchanges. My Figure 3 shows three potential solutions to the Steiner tree problem, two of which use interchanges. Numerous instances of interchange using solutions are represented in Figure 4. One of the major points of the paper is that Thomas introduced a bias into the algorithm to increase the number of interchanges. Interchanges are everywhere in my paper, and claiming that I am somehow attempting to minimize their importance is unsupportable.

In fact, I argued something close to the opposite of what Thomas attributes to me. I did not argue that we can treat the Steiner tree problem as simply a minimum spanning tree problem. I discussed the minimum spanning tree to establish a threshold for success. I argued that any Steiner tree solution that is worse than or equal to the cost of the minimum spanning tree is essentially worthless. It the process of evolution manages to produce such a solution, it is considered unsuccessful. The only way to beat the minimum spanning tree solution is to use interchanges. Thomas’s algorithm does beat the minimum spanning tree solution much of the time, and those are the times I studied in my paper. My paper did not dismiss interchanges, and only cares about finding the minimum spanning tree. In my paper I embraced interchanges and rejected solutions that do not use them.

Thomas also states:

They make a big point of how my algorithm pre-located interchanges more in the center, and that this was introducing “active information.” What they overlooked, however, was that this was a feature of the slow FORTRAN version only, and was removed (as quite un-necessary) in the much faster C++ version.

We did not overlook this point. We explicitly mention it in the paper in a section dedicated to discussing the differences between the C++ and FORTRAN versions. But that’s really irrelevant. Because we were studying the FORTRAN version, the specifics of other variations of the algorithm are beside the point. Yes, it was not strictly necessary for the success of the algorithm, but we showed that in the paper. The paper shows the performance with and without this restriction. It shows that while not failing without the restriction, it does make the algorithm much less likely to succeed. Additionally, this was only one of the points we made. We also pointed out that he biased the algorithm toward including more interchanges, introduced a selection skew, and picked an ideal form of crossover. Thomas simply ignores the other points, focusing on the one particular point he changed in the C++ version.

Thomas’s critique fails. He does raise a couple of legitimate flaws. However, he focuses on raising nonsense objections and offering unsupportable misreadings of my papers. Thomas has not demonstrated the evolution of irreducible complexity. He has not demonstrated the natural production of complex specified information. He has not demonstrated a genetic algorithm that can produce large amounts of active information without teleology. Thomas’s efforts notwithstanding, our conclusions stand.

Image credit: Rama (Own work) [CeCILL or CC BY-SA 2.0 fr], via Wikimedia Commons.

Winston Ewert

Senior Fellow, Senior Research Scientist, Software Engineer
Winston Ewert is a software engineer and intelligent design researcher. He received his PhD from Baylor University in electrical and computer engineering. He specializes in computer simulations of evolution, genomic design patterns, and information theory. A Google alum, he is a Senior Research Scientist at Biologic Institute and a Senior Fellow of the Bradley Center for Natural and Artificial Intelligence.



__k-reviewComputational SciencesResearchscienceViews