Review: Climbing the Steiner Tree

Overview

Winston Ewert, William Dembski, and Robert J. Marks II have made available a paper titled Climbing the Steiner Tree — Sources of Active Information in a Genetic Algorithm for Solving the Euclidean Steiner Tree Problem wherein they claim to have identified sources of “active information” in a genetic algorithm used to find solutions to a Steiner problem. The problem referenced in this paper was originally described by Dave Thomas on the Panda’s Thumb almost six years ago. I developed a GA to solve the problem that Dave posed as a challenge a few weeks later, as did a number of other people.

This paper suffers from numerous flaws, starting with a fundamental mischaracterization of the purpose of Thomas’s solution and including general misunderstanding of genetic algorithms, misapplication of the No Free Lunch theorems, spurious claims about “active information”, and incorrect and unsupported assertions regarding the impact of certain GA implementation details.

Targets

Right from the abstract, this paper mischaracterizes Thomas’s intentions:

In particular, the success of such search algorithms is said to show that intelligent design has no scientific value.

Thomas never claimed that GAs showed that ID has no scientific value. His goal was simply to demonstrate the fact that GAs don’t need explicit targets.

(As an aside, it is true that ID has no scientific value but that is because ID proponents explain no empirical observations, articulate no scientific theory, and make no testable predictions. ID is simply a vacuous argument from incredulity.)

The authors of this paper do appear to grudgingly recognize that typical GAs are not like Richard Dawkins’ well known Weasel program:

Nevertheless, many simulations do not contain a fully articulated solution hidden behind lines of code that can be readily reconstructed by inspecting the program without running it.

Speaking of weasels, this phrasing does have the mustelid nature. The authors could have been more forthright and simply noted that most GAs specify only the problem and a fitness function of some sort. The solution is completely unknown to the programmer in most cases.

Even this rhetorical squirming, though, is insufficient for the authors who add a caveat immediately:

Rather, its code is front-loaded with specialized information for how to find that solution. Instead of the explicit answer, the means by which the eventual product can be found is front-loaded.

The authors are inadvertently correct here. The evolutionary mechanisms being modeled by the GA (“the means by which the eventual product can be found”) are indeed useful in finding solutions to some problems.

Properties of Genetic Algorithms

There are several statements in the paper that suggests the authors have some fundamental misunderstandings of genetic algorithms and the observed phenomena on which they are based. As early as page 2, for example, is this:

The Darwinist claim is that no such assistance is required. Rather, natural selection is innately capable of solving any biological problem that it faces.

No “Darwinist” (a term that reflects ID’s creationist roots) claims this. Extinction is known to happen.

Another, from page 4:

This genome is of a fixed length, always containing the coordinates and connections for the maximum number of interchanges. This simplifies the genetic algorithm because it not [sic] necessary to implement deletion or insertion mutations.

While the design of a GA engine is somewhat simplified by limiting genomes to a fixed length, such a constraint doesn’t prevent modeling insertions and deletions. Further, the lack of insertion and deletion mutations actually makes finding a solution more difficult by limiting the number of evolutionary mechanisms that can be brought to bear.

On page 5 we find:

Does the genetic algorithm have the ability to solve the problem given only a description of the same?

This question demonstrates a profound confusion about what is being modeled. The authors almost seem to be suggesting that they expect a GA to find a solution without any feedback whatsoever. That would certainly fail to reflect the biological situation.

In fact, the fitness function is a description of the problem domain, corresponding to the environment of biological evolution. In that sense a GA does have the ability to solve some types of problems “given only a description of the same.”

No Free Lunch Theorems

No paper authored by Dembski would be complete without some mention, however gratuitous, of the No Free Lunch theorems:

Conservation of information theorems, such as the No Free Lunch Theorems, place limitations on the abilities of search algorithms. Any search algorithm uses resources to try to find its target. Different algorithms exist, but as long as they avoid searching the same place multiple times, given the same resources they will have the same average performance. As a result, excluding algorithms that visit the same place multiple times, no algorithm can be claimed to be superior to any other algorithm. At best, it can be superior over some subset of all fitness functions.

First, the NFL theorems have nothing to do with “conservation of information.” Dembski’s purported “Law of Conservation of Information” has been demonstrated to be bogus.

Second, this is a typical gross misapplication of the NFL theorems by Dembski et al. The NFL theorems say that averaged over all fitness landscapes, no search algorithm is superior to random search. Over a specific fitness landscape, however, some algorithms may well be significantly better than others. Given that GAs, like the natural systems on which they are based, operate within a single fitness landscape (albeit one that is constantly changing, particularly in the real world case), the NFL theorems are simply a red herring in this discussion.

Active Information

The authors define “active information” as:

I+ = -log2(p/q)

where p is probability of a “baseline” search finding a solution and q is the probability of the GA finding a solution.

A baseline search is typically taken to be a single random guess at the answer.

“Active information” is thus simply a comparison of the efficacy of a particular search algorithm to that of a random search using an equiprobable distribution. The term is misleading in that it doesn’t correspond to any commonly used definitions of “information” nor does it demonstrate the “active” involvement of any external actor.

In order to determine how Thomas’s GA compares to a random search algorithm, the authors ran a relatively large number of tests:

In what follows we will be comparing Thomas’s genetic algorithm to that of a random query search. Data on the performance of the search algorithm was obtained by Monte Carlo simulation. In the case of genetic algorithms, we ran 5615 distinct simulations, keeping track of how many times a particular cost was found. In the case of random query searches, we ran 11,228,106,000 random queries to determine the empirical probability distribution for the cost of a random solution. The actual performance of a random query search was calculated by using probability theory and this empirical distribution.

“Probability theory and this empirical distribution”? With over eleven billion data points, why did the authors not simply use the observed values?

The results reported on page 5 of the paper are surprising:

Figure 4 shows the performance of the genetic algorithm presented by Thomas as compared to a random query algorithm. For Thomas’s algorithm, each generation is run for 1000 generations giving a total of 2,000,000 queries or cost evaluations performed. That is, the algorithm considers two million distinct solutions and measures the cost of each solution. At the end of that process the best solution found during those queries is produced. The random query algorithm makes 2,000,000 random queries and reports the best of all of those queries. Figure 4 shows that obtaining a low cost solution to the Steiner tree problem is not as hard as it would at first appear.

The random query algorithm produces a cost of 1246 with probability slightly lower than 0.7.

The authors seem to be claiming that two million random searches will yield a reasonable solution to the Steiner problem nearly 70% of the time. That’s hard to reconcile with further details provided on the very next page:

Baseline for good and adequate thresholds.
We empirically estimated the probability of both the good and adequate thresholds by running Monte Carlo experiments that tested random solutions. 11,228,106,000 random queries were performed to obtain an empirical estimation of the probability of finding the target. The probabilities for finding the good and adequate targets were 1.7812e-09 and 1.9905e-07, respectively. The empirically determined probability for finding the optimal target was zero, because none of the random queries was successful in finding the target.

The 70% chance of success of the random search algorithm seems extremely high. The authors provide no details of their calculations or code, so I have attempted to replicate their findings based on the description provided and my own GA solution to the Steiner problem.

My Steiner solution is based on my GA engine that operates on binary strings. The number of bits required by the genome for the five node Steiner problem is 199. I use a tournement selection mechanism to populate the next generation:

  1. Select two genomes at random, making the most fit parent one
  2. Select two more genomes at random, making the most fit parent two
  3. Mate the two parents by crossing over at a single point to
    generate two offspring
  4. Mutate each of the offspring

My simulation routinely finds a near optimal solution with a fitness cost of 1220 or less using a population size of 1000 within 250 generations.

Each generation of my simulation therefore requires 4000 fitness evaluations, or one million in total for a typical run. Based on the results reported in this paper, I should find that nearly 70% of the time one million random genomes should contain at least one fairly good solution.

Here’s the code to create a million random genomes and return the most fit, using my implementation:

(let* ((genome-length (genome-length *five-point-problem*))
       (best-fitness
        (fitness *five-point-problem* (make-genome genome-length))))
  (format t "~A~%"
          (dotimes (i 10000 best-fitness)
            (let ((random-fitness
                   (fitness *five-point-problem* (make-genome genome-length))))
              (when (< random-fitness best-fitness)
                (setf best-fitness random-fitness))))))

My simulation adds a penalty of 2000 for solutions that don’t connect all fixed nodes. The results of running this forty times are:

4500.08   4394.203  4466.51   4707.275
4430.624  4690.22   4847.232  4833.6436
4889.9487 5147.8467 4929.9795 4677.0977
5248.128  4940.031  4542.566  4555.242
4993.9985 4707.127  4450.148  4792.4023
4647.6304 4800.055  5224.4985 4616.3096
5000.876  4788.144  4961.3896 4383.1436
4888.9614 4577.821  3791.8147 4739.0806
4846.8315 4572.504  4951.1255 4481.5996
4690.18   4426.3213 5097.7544 4948.6284

The best fitness found was 3791.8147, not remotely close to the optimum of 1212 or the 1220 routinely generated by the GA.

The authors of the paper do not provide a description of the algorithm they used or the code, so it is not possible to determine how to replicate their results. As demonstrated here, though, their claim that a collection of random strings, similar in size to the number of fitness calculations used by a GA, has a 70% likelihood of containing a near optiomal solution is not supported.

On page 6 of the paper, the authors plug this dubious value into some poorly explained forumlae and claim to thereby have derived “the integral cost of the solution produced by a search algorithm making 2,000,000 random queries.” This section could use considerably more justification, to say the least.

Ultimately, aside from demonstrating a distinct lack of rigor on the part of the authors, this topic is as much of a red herring as the No Free Lunch theorems. At most, when calculated carefully, “active information” is nothing more than an indication of how a particular algorithm performs relative to an equiprobable random search in a particular fitness landscape. Despite the misleading name applied to this concept, it does not indicate that any information was provided to the non-random algorithm, actively or otherwise.

Implementation Details

Beginning on page 7 the authors discuss implementation details that, they claim, provide information about the solution to Thomas’s GA.

Interestingly, this is very similar to an approach that Dembski used unsuccessfully a few years ago. When discussing Thomas Schneider’s ev simulation, Dembski noticed an implementation detail related to tie breaking. He claimed that:

Schneider is here fine-tuning his evolutionary algorithm to obtain the results he wants. All such fine-tuning amounts to investigator interference smuggling in complex specified information.

Schneider put Dembski’s claim to the test. The result was “For the condition where both organisms survive a tie, the ev program still produces the same graph as previously published, given the same parameters, demonstrating that the code was not significantly altered.”

One might think that Dembski would have learned from that experience to test his claims before making them public. One would be incorrect.

“Effect of count of interchanges”

The authors claim that having an explicit count of the number of non-fixed nodes in the virtual genome “shifts the distribution of solutions.” They also note that Thomas’s code ensures that a minimum number of non-fixed nodes (“interchanges”) are present.

My implementation contains no such explicit count nor does it specify any minimum number of non-fixed nodes, yet it routinely converges on an optimal or near-optimal solution.

“Effect of restricted initialization”

According to the authors, Thomas’s code restricts the initial location of non-fixed nodes to a smaller area than the full 1000×1000 grid allowed by the simulation. Again, my implementation has no such restriction and yet it routinely converges on an optimal or near-optimal solution.

“Effect of selection skew”

The authors begin this subsection with:

As noted, it is easy to obtain a solution with a score of 1246.

In fact, as demonstrated above, the claim that near-optimal genomes are common enough to be frequently present in collections of millions of random genomes is false.

The authors go on to discuss a “skew parameter” used in Thomas’s code. They make the claim, without any logical or empirical support, that:

Without the skew parameter there isn’t enough selective pressure to effectively separate scores of close value.

Not only is this unsupported, it is demonstrably false since my implementation contains no such parameter and yet readily distinguishes between “scores of close value.” This is easily seen when monitoring its progress generation by generation.

“Effects of crossover”

In this section the authors go to some effort to score an own goal. Rather than limiting themselves to the single point crossover implemented by Thomas, they also discuss two point crossover and, bizarrely, what they call “uniform” crossover. This variant, which consists of randomly picking an element from each parent string in order to generate a child string, would not be recognized as crossover by anyone familiar with GAs.

Be that as it may, they then provide a table of crossover related “active information” in Table 3. Precious little detail is provided on how these values were calculated.

The own goal is apparent when one steps back from the detailed, albeit odd, discussion and notes that crossover is observed in nature. The authors are essentially admitting that known evolutionary mechanisms can create “active information.”

Alternative Representations

On page 10 the authors raise their only pertinent point in the entire paper:

Crossover works well because of the way the genome is structured. The genome is built using a structure consisting of a list of locations as well as a connection map indicating which cities and interchanges are connected. However, the ways in which the genome could be structured are limited only by the developer’s creativity. A number of other possibilities also exist:

  • Every city and interchange could have a list of other
    cities/interchanges to which it is connected.
  • The genome could be a sequence of road segments specified by start and stop points
  • The genome could have been represented as a bitmap where each bit indicates whether or not an integral coordinate was on a road.

None of these methods were chosen, and none of them would seem to be useful representations. But they are rejected, not because something is intrinsically wrong with them, but because the developer uses his knowledge of the problem to come up with the best way to represent the solution. The programmer chooses the representation that he believes will be effective and part of that is choosing a representation that works well with crossover.

As with their other claims, the authors provide no suggestion that they implemented a fitness function using any alternative representation. In fact, I suspect that a GA could successfully operate on any of the three alternatives. Despite the authors’ incorrect reasoning, though, this is an interesting point.

When I implemented my solution to the Steiner problem I wasn’t thinking in terms of a fitness function that could easily be traversed by point mutations and crossover. I simply wrote down the first binary format that came to mind — my primary concern was my own ability to decipher it. That aside, the authors make a claim that is almost correct:

The crossover and genome structure work together. As such, their selection by the developer constitutes the use of prior knowledge about the problem in order to help identify better solutions.

Even if the fitness landscape were deliberately chosen to be easily traversed by the subset of known evolutionary mechanisms modeled by the GA, this would not be a way of smuggling in information about any possible solution. No additional information about the problem or the particular solution would be provided. Such a deliberate choice would simply be modeling a landscape that, like what we observe in nature, has characteristics that make known evolutionary mechanisms effective search techniques.

When modeling evolution as a search (which has its own issues outside the scope of this discussion), what the No Free Lunch theorems tell us, contra Dembski, is that the evolutionary mechanisms we implement will be far more effective at finding a solution in some types of fitness landscapes than in others. Because we observe these mechanisms working in the real world, it is a reasonable inference that the incredibly complex and ever changing fitness landscape we call reality is one of those in which those mechanisms are efficacious. If this were not the case, we would either observe other mechanisms or would not be here to observe at all.

Despite themselves, the authors are recognizing that even a small subset of the mechanisms we observe in the real world is more than capable of generating solutions that are highly fit in certain landscapes.

Summary

The authors completely fail to support their conclusion:

The claim is not that the solution found by a genetic algorithm is hidden inside the algorithm, but rather that the algorithm contains the necessary information sources in order to find a low probability target. This is because in order to develop a successful genetic algorithm, the developer makes many decisions based on knowledge of the problem he is attempting to solve. As such, information is derived from this prior knowledge of the search problem.

Every implementation detail alleged by the authors to smuggle in information about possible solutions is trivially shown to be unnecessary to the success of the GA. Whether they understand it themselves or not, all the authors have shown is that known evolutionary mechanisms are quite capable of generating solutions to problems that are not amenable to random search.

It is no surprise that this paper was published in BIO-Complexity, the Intelligent Design vanity website masquerading as a journal. Given the overall poor quality, particularly with respect to the authors’ failure to provide sufficient information to replicate their results and their further failure to subject any of their claims to testing, it is unlikely in the extreme that it would pass peer review in an actual scientific journal.

118 thoughts on “Review: Climbing the Steiner Tree

  1. In general, genetic algorithms work well unless the fitness surface is very rough and “jaggy”. Dembski and Marks’s “active information” is basically a measure of how smooth the fitness surface is when neighbors of a genotype are defined as those that can be reached by a single mutation.

    It is thus no big surprise that unless there is some of this “active information” genetic algorithms will not work well. They intend this to be part of an argument that a Designer put the “active information” there. But (as I and others have noted), the laws of physics seem to mandate a certain amount of smoothness of fitness surfaces. A mutation that affects one part of the organism often has little effect on other parts, and that helps keep the fitness surface smooth. A “white noise” fitness surface would be a big problem for natural selection, but it would require everything to interact strongly with everything else, and physics doesn’t work that way. My typing these words has not caused your roof to leak.

  2. Joe wrote “But (as I and others have noted), the laws of physics seem to mandate a certain amount of smoothness of fitness surfaces.”

    Yup. The universe is full of (local) gradients.

  3. Dembski’s argument simply has no merit. Part of me thinks that he must realise this.

    Irreducible Complexity (or, at least, the idea of unevolvable systems) could have some force, given the right data, but Specified Complexity is flawed at its heart.

  4. Joe Felsenstein:
    Dembski and Marks’s “active information” is basically a measure of how smooth the fitness surface is when neighbors of a genotype are defined as those that can be reached by a single mutation.

    That’s a very clean way of describing it. Nothing active, no information involved, and the more different types of mutations available, the more jagged a fitness landscape can be traversed.

  5. Interestingly, even simple things such as the various allotropes of carbon are “solutions to a problem,” namely, of finding a local minimum in potential energy of a configuration of condensing atoms or molecules consistent with temperature and pressure in the environment of these carbon atoms.

    That these various “solutions” appear at various temperatures and pressures with varying degrees of probability is a common underlying feature of all condensing matter.

    I have often suggested that ID/creationists make the egregious errors they do about biological systems because they don’t understand even the most basic high school level physics and chemistry. The misconceptions that Dembski et. al. continue to repeat are all founded in the notion that nothing interacts; that all atoms and molecules just sit around waiting for some intelligent entity to select them and place them in highly improbable arrangements.

    There are always matters of physics and chemistry that contribute to the “solutions” found in biological systems undergoing natural selection. And the “analog computer” soap bubble solutions to the Steiner Problem rely on the minimizing of the potential energy contained in the tensions in the spanning soap bubble surfaces.

    Soft matter systems, such as those making up biological organisms, exist within a very narrow energy range in which the thermal kinetic energies are comparable to the binding energies of many parts of these systems. This is what allows the systems to respond to changes in the average background forces of the total environment in which the system is immersed. If binding energies were too large relative to the thermal kinetic energies, nothing could change. If the thermal kinetic energies become larger than the binding energies, the systems come apart.

    The result of all this is that complex biological systems get to explore all sorts of nearby “solutions” as biasing pressures are placed on them by their environments. Just look at the billions life forms that exist or have existed on this planet and you see that lots of “solutions” have been found (and discarded). Whether or not any of these “solutions” will be repeated in the future may be unlikely, but the fact that “solutions” exist in such abundance means that there is almost always a nearby niche in which something can survive for a while.

  6. Behe’s argument seems you can’t get from AB to XY if AX and BY are fatal. Ignoring the possibility of passing through AC to XC to XY. In the simplest case.

  7. Patrick: That’s a very clean way of describing it.Nothing active, no information involved, and the more different types of mutations available, the more jagged a fitness landscape can be traversed.

    Or the smoother the fitness landscape becomes :)

    In other words, isn’t the fitness landscape topology defined in part by the types of mutations available?

  8. Elizabeth: Or the smoother the fitness landscape becomes :)

    In other words, isn’t the fitness landscape topography defined in part by the types of mutations available?

  9. Elizabeth: Or the smoother the fitness landscape becomes

    In other words, isn’t the fitness landscape topology defined in part by the types of mutations available?

    I’m reminded of the optical illusion that sometimes looks like a vase and sometimes like two people facing each other. ;-)

  10. Elizabeth: Patrick: That’s a very clean way of describing it.Nothing active, no information involved, and the more different types of mutations available, the more jagged a fitness landscape can be traversed.
    Or the smoother the fitness landscape becomes
    In other words, isn’t the fitness landscape topology defined in part by the types of mutations available?

    You hit the nail directly on the head.

    There is even a well-defined mathematical description of sampling a complex landscape, and it comes from the Fourier analysis of signal and image processing. It is called “dithering.”

    In the language of Fourier analysis, if a function that has a Fourier transform is shifted by a little bit x, the only change in its Fourier transform is to multiply it by a phase factor exp(ikx) where k is called a spatial frequency. The shift, x, produces a much larger shift in phase for higher spatial frequencies.

    If the shift, x, is a random variable, and the signal is summed, then the higher spatial frequencies are “washed out” because they tend to add more randomly than the lower spatial frequencies. This leaves the lower spatial frequencies pretty much intact, but the fine details in the image are blurred out.

    This is often referred to as “poor man’s low-pass filtering” in that it retains the gross, overall features of the image but smoothes out the fine details. It is often used to remove noise from a signal or image.

    This applies directly to the sampling of a landscape by random variations of an organism.

  11. Here is a little example of the “poor man’s low pass filtering” one can easily demonstrate. Look through a hedge at a distant object on the other side of the hedge. It is hard to make out the object.

    But if you move your eye along the line of the hedge while peering through it to the distant object, you see the object more clearly. It is the persistence of the distant image on the retina of the eye that makes this Fourier analysis apply. Another equivalent analysis uses what is called the convolution of the moving images of the hedge leaves and branches relative to the much slower movement of the image of the distant object.

    I use this technique when looking for oncoming cars as I approach an intersection with hedges blocking the view. I roll slowly by the hedges as I stare through them at the cross street.

  12. Elizabeth:
    Dembski’s argument simply has no merit.Part of me thinks that he must realise this.

    Irreducible Complexity(or, at least, the idea of unevolvable systems) could have some force, given the right data, but Specified Complexity is flawed at its heart.

    I hope we can discuss this in a separate thread. You were at one point reaqding your way through Dembski’s No Free Lunch chapter by chapter. When you reach the one about why natural selection cannot put Complex Specified Information into the genome, I’d be pleased to hear your thoughts on his argument. My own take, as I have written elsewhere, is that for simple model evolutionary systems, Complex Specified Information can be defined and is thus at least partly meaningful. However the Law of Conservation of Complex Specified Information (LCCSI) is both unproven, and in the form he presents it, not able to do the job of showing that natural selection cannot put CSI into the genome.

    But let’s not discuss it here — it needs a separate thread.

  13. Yes, it is true the GA does not need a specific target. The GA was written to do something. So when it does it, it does it by design.

    In “Evolving Inventions” there wasn’t any pre-specified target- meaning no one knew what the GA generated circuits would look like. All they knew is what the circuits had to do.

    So again the circuits arose by design.

    Another problem is there isn’t any “selection” in nature. Natural slection is a result. There isn’t a goal, just survival- whatever is good enough survives.

  14. Joe G:
    Yes, it is true the GA does not need a specific target. The GA was written to do something. So when it does it, it does it by design.

    In “Evolving Inventions” there wasn’t any pre-specified target- meaning no one knew what the GA generated circuits would look like. All they knew is what the circuits had to do.

    So again the circuits arose by design.

    Another problem is there isn’t any “selection” in nature. Natural slection is a result. There isn’t a goal, just survival- whatever is good enough survives.

    blowing my totem
    I inflated my crayons
    before my money

  15. Joe G: Scratching your scrotum
    You blew your crayon
    and your pimp beat you

    Oh the breaking taught!
    fie! drat! blowing playing suit.
    Suzuki cheats soon

  16. Patrick, you should send a more formal version of this to BIO-Complexity – perhaps they would publish it in a letters section.

  17. rhampton7:
    Patrick, you should send a more formal version of this to BIO-Complexity – perhaps they would publish it in a letters section.

    That would require a significant snarkectomy. I do wonder if they’d publish such a thing, though.

    Ideally one or more of the authors will come here to discuss the paper (and Dr. Felsenstein’s CSI related topics).

  18. Patrick,

    Some confusion here. When EDM say “The random query algorithm produces a cost of 1246 with probability slightly lower than 0.7.”, they are referring to the simplest solution, 5/6 outer perimeter segments, no internal junctions, etc. Looks like a letter “C” for the 5-city problem. If you look at EDM Figure 4, THEY NEVER ACHIEVE THE ACTUAL STEINER SOLUTION (1212 Length). More later, Dave

  19. Joe G:
    I posted a link to this over on UD…

    Very kind of you.
    No-one there interested in this subject dare come here, though.

  20. Yes, they realize that when a programmer writes a program to do something, and it does it, then it did it by design, not via natural selection.

    IOW they realize it is a waste of time trying to reason with people who say otherwise.

  21. DaveThomas:
    Patrick,

    Some confusion here. When EDM say “The random query algorithm produces a cost of 1246 with probability slightly lower than 0.7.”, they are referring to the simplest solution, 5/6 outer perimeter segments, no internal junctions, etc.Looks like a letter “C” for the 5-city problem.If you look at EDM Figure 4, THEY NEVER ACHIEVE THE ACTUAL STEINER SOLUTION (1212 Length). More later, Dave

    Their result with length 1246 is certainly nowhere near the 1212 actual solution or even the 1218 to 1220 my implementation routinely gets within 250 generations.

    What I wanted to emphasize in my response, though, is the authors’ claim on page 5 that “The random query algorithm produces a cost of 1246 with probability slightly lower than 0.7.” I read that as saying that almost 70% of the time a set of two million random genomes will contain at least one with a fitness of 1246 or better. That’s certainly not the case with my implementation, as I demonstrated. Have you tried to independently confirm their results with your version?

  22. Joe G:
    Yes, they realize that when a programmer writes a program to do something, and it does it, then it did it by design, not via natural selection.

    IOW they realize it is a waste of time trying to reason with people who say otherwise.

    So close! What they realize is the futility of making unsupported claims in an attempt to convert those whose contrary claims are already demonstrated, complete with source code!. They know they’ll be challenged to identify the answer hidden somewhere in the code, they know it’s not there, so they don’t bother to do more than stay in their ghetto making false claims and all agreeing not to test or challenge them.

  23. Even if the programmer uses randomness to produce the result?

    Because that’s the argument the Catholic Church makes in regards to the flawed assumption behind Intelligent Design and Atheism — that is, random mutations must be purposeless and a force outside of God’s Providence. Instead, the Church teaches that the range of freedom granted by random processes has a God given purpose that, none the less, can not on its own alter the prescribed plan.

    Given your hostility towards Evolutionism, it’s ironic that you believe randomness to be outside of God’s domain.

  24. Elizabeth, is there some reason that today this site is showing this thread (“Review: Climbing the Steiner Tree”) twice, once before and once after JoeG’s thread? The comments in those two nominally different threads seems to be the same..

    I suspect some kind of misconfiguration or WordPress bug.

  25. Joe Felsenstein: Elizabeth, is there some reason that today this site is showing this thread (“Review: Climbing the Steiner Tree”) twice, once before and once after JoeG’s thread? The comments in those two nominally different threads seems to be the same..I suspect some kind of misconfiguration or WordPress bug.

    I believe it has received a “sticky” to keep it at the top, as it is such a very good thread!

  26. Rich: I believe it has received a “sticky” to keep it at the top, as it is such a very good thread!

    I think it is not only “sticky”, it has replicated, although without becoming genetically different.

  27. Even if the programmer uses randomness to produce the result?

    Yes, even though that is not what happens with a GA.

  28. Patrick,

    Holy crap, I did some new runs, and those ID folks are doing some really strange stuff!

    Here’s my result just now for the 5-node problem, 5 million random sequences:

    And here are 2 million sequences at a pop, three times:

    It is clearly floundering badly, not getting close to the optimum Steiner (1212), and not even to the “Round-the-track” C-shaped solution (1246).

    I will have to check this out some more, Patrick! Those folks are trying to pull a fast one!
    Cheers, Dave

    P.S. I am using image tags. Not showing up in Preview. Here are the raw URLs to load the images at NMSR:
    http://www.nmsr.org/random5M.jpg
    http://www.nmsr.org/random2Ma.jpg
    http://www.nmsr.org/random2Mb.jpg
    http://www.nmsr.org/random2Mc.jpg

  29. Joe G:
    LoL! YOU are one of the reasons they will stay away- no way to reason with that “logic”…

    Yeah joe, the last thing IDiots want is to face their opponents out in the open. It must be a terribly empty feeling to have no evidence and no confidence in their position. It must also be a terribly empty feeling for you that they won’t come here and stand up for you and ID. You poor thing.

  30. LoL! Reality says that the last thing you evos want is to face ANY opponent out in the open. But that is because your position has absolutely nothing, and it shows.

    Also, unlike you evoTARD cowards, I do not need anyone to stroke me/ stand up for me. And I feel bad for all IDists and creationists that do come here because they have to deal with irrational thugs like you.

  31. DaveThomas:
    Patrick,

    Holy crap, I did some new runs, and those ID folks are doing some really strange stuff!

    Here’s my result just now for the 5-node problem, 5 million random sequences:

    And here are 2 million sequences at a pop, three times:

    It is clearly floundering badly, not getting close to the optimum Steiner (1212), and not even to the “Round-the-track” C-shaped solution (1246).

    I will have to check this out some more, Patrick! Those folks are trying to pull a fast one!

    It’s interesting to see that our results agree with each other and differ so significantly with those reported in the paper. I think I have Winston Ewert’s email around somewhere — if I can find it I’ll see if he’d be interested in joining the discussion here. Perhaps he’ll at least be willing to make his code available.

    (I’m making the hopefully not unwarranted assumption that the graduate student on the authors’ list did most of the hard work.)

  32. Your OP is full of nonsense, Patrick.

    1- Evos coined the term “Darwinism” which includes “Darwinists”

    2- Darwinists do make the claim that natural selection can solve just about any issue

    3- There isn’t anything in
    Does the genetic algorithm have the ability to solve the problem given only a description of the same?
    that implies there isn’t any feedback

    4- The paper says, right in it, that a GA does need a specific target- page 2

    5- You have no idea if insertions or deletions are blind and undirected

    the list could go on but I am sure you will ignore it just as IDists should ignore your post.

  33. The above quote shows that Thomas is under the misapprehension
    that intelligent design advocates claim that the actual answer is encoded into the algorithm. This is not in fact what intelligent design advocates claim, as will be shown later. Rather, we say that success is due to prior knowledge being exploited to produce active information in the search algorithm. Although the code does not include the actual Steiner shape, it does include a tuned algorithm for how to find the Steiner shape.

  34. Joe,

    The rule of this venue is that we should assume that other participants are acting in good faith. Based on your behavior here, I cannot rationally make that assumption. Accordingly, in order to honor our gracious hostess’s wishes, I will not be replying to you on this or any other topic.

    Sincerely,

    Patrick

  35. Joe,

    The rule of this venue is that we should assume that other participants are acting in good faith. Based on your behavior here, I cannot rationally make that assumption. Accordingly, in order to honor our gracious hostess’s wishes, I will not be replying to you on this or any other topic.

    Sincerely,

    Patrick

    (Lizzie — I tried to move this to Guano, but don’t seem to have the right privileges. My apologies for imposing on your time to do so.)

  36. LoL! Patrick, YOU are not acting in good faith. Your OP contains lies and errors. But somehow that doesn’t mean anything to you.

  37. As Patrick’s OP contains errors that are easily exposed- I have already exposed some- perhaps Patrick needs some of Elizabeth’s protection because his mother isn’t around to do so.

  38. Here’s the code to create a million random genomes and return the most fit, using my implementation:

    Patrick,

    You were intelligently designing the fitness function weren’t you?

    Dave Thomas,

    By the way, since I humored you on his earlier challenge, I have a chanllenge for you that you should accept in reciprocity. :-)

    I will donate $50 to the New Mexicans skeptic organization that you are a member of if you can write a GA which will converge on the complex specified informaiton string (a password if you will) that I have wrtitten explicitly on a sheet of paper. You have 2 months to solve it and publish your results.

    C’mon dave, I humored you, now it’s your tun. You’re officially challenged to describe it. You have no feed back mechanism to tell you if you’re getting warm. But the $50 should help your organization reproduce more Darwinists, so according to Darwinist logic, since it will make your organization more fit financially, it ought to imply a GA will find the solution on behalf of your organization. (I’ve heard such perverse reasoning before from Darwinists, that something necessarily evolved because it will make it more fit!).

    Think I’m being too hard. Numerous systems in a biological organism are like lock-and-key, password login systems. They are deeply coordinated. A random password is unlikely to hit a random login. There is no reason a GA would solve this unless it were trivial since there is no feedback mechanism and since password/login’s irreducibly complex.

    And since the absence of some proteins, like insulin or other critical proteins, will result in death — one shot at a solution is like what it might be in real life biology. :-) So you have one shot at a solution.

    I look forward to hearing from you. I humored you, now it’s your turn.

  39. stcordova: You were intelligently designing the fitness function weren’t you?

    What if the “code” to do that was the environment. Woudl the the fitness function still be intelligently designed?

    You can demonstrate this easily. Simply take some bacteria and spread them evenly over a differentiated environment. Some will be less fit in the environment they find themselves in then others.

    Where did the fitness function come from?

  40. Patrick wrote:

    . Rather, natural selection is innately capable of solving any biological problem that it faces.

    No “Darwinist” (a term that reflects ID’s creationist roots) claims this.

    So are you saying there ARE complex biological systesm which natural selection can’t create. :-)

    If you say, yes, then well, thanks for helping creationists.

    If you say no, then, on what basis do you make that claim except by assumption.

  41. Depends on what you mean by “ARE.”

    Potential or actual? Missed opportunities?

    Evolution can only move in steps the size of mutations and insertions.

    Can you name a specific event in the history of life that crosses an unbridgeable gap, citing the before and after, the time and place?

  42. stcordova:

    If you say, yes, then well, thanks for helping creationists.

    If you say no, then, on what basis do you make that claim except by assumption.

    Interestingly asymmetric standard, there. Agree with creationists and no further info required. Disagree, and you gotta justify it!

  43. stcordova
    By the way, since I humored you on his earlier challenge, I have a chanllenge for you that you should accept in reciprocity. :-)

    I will donate $50 to the New Mexicans skeptic organization that you are a member of if you can write a GA which will converge on the complex specified informaiton string (a password if you will) that I have wrtitten explicitly on a sheet of paper. You have 2 months to solve it and publish your results.

    C’mon dave, I humored you, now it’s your tun. You’re officially challenged to describe it. You have no feed back mechanism to tell you if you’re getting warm. But the $50 should help your organization reproduce more Darwinists, so according to Darwinist logic, since it will make your organization more fit financially, it ought to imply a GA will find the solution on behalf of your organization. (I’ve heard such perverse reasoning before from Darwinists, that something necessarily evolved because it will make it more fit!).

    Think I’m being too hard. Numerous systems in a biological organism are like lock-and-key, password login systems. They are deeply coordinated. A random password is unlikely to hit a random login. There is no reason a GA would solve this unless it were trivial since there is no feedback mechanism and since password/login’s irreducibly complex.

    And since the absence of some proteins, like insulin or other critical proteins, will result in death — one shot at a solution is like what it might be in real life biology. :-) So you have one shot at a solution.

    I look forward to hearing from you. I humored you, now it’s your turn.

    Sorry, Salvador, but I don’t think I’m interested in your “challenge.”

    It has NOTHING to do with “evolution”, after all.

    Recall what Dawkins himself said about his “Weasel” program back in 1986 (Blind Watchmaker

    Although the monkey/Shakespeare model is useful for explaining the distinction between single-step selection and cumulative selection, it is misleading in important ways. One of these is that, in each generation of selective ‘breeding’, the mutant ‘progeny’ phrases were judged according to the criterion of resemblance to a distant ideal target, the phrase METHINKS IT IS LIKE A WEASEL. Life isn’t like that. Evolution has no long-term goal. There is no long-distance target, no final perfection to serve as a criterion for selection, although human vanity cherishes the absurd notion that our species is the final goal of evolution. In real life, the criterion for selection is always short-term, either simple survival or, more generally, reproductive success.

    Show me anywhere in biology where life must adapt to a hidden phrase created by Sal Cordova.

    I have a secret message for you to decipher, if you wish. I am pointing at the screen and your post with one single finger. Guess which one it is!
    :D

  44. stcordova: Think I’m being too hard. Numerous systems in a biological organism are like lock-and-key, password login systems. They are deeply coordinated. A random password is unlikely to hit a random login.

    So apparently you would argue that the nucleons, nuclei, atoms, molecules, solids, crystals, polycrystals, and quasi-crystals are all “lock-and-key password login systems?”

    What about superconductivity and superfluidity? These are highly coordinated systems.

    Why do you apply this characterization to biological systems and not to other complex, highly coordinated systems? Specifically where along the line of increasing complexity of condensed matter does this kind of characterization of “lock-and-key password login systems” begin to apply?

    ID/creationism can’t even explain the existence of solids and liquids, let alone their behaviors and properties within various temperature ranges?

  45. The idea that a GA could converge on an isolated target like a lock combination or cryptogram exhibits a misunderstanding of evolution that is so deep and so profound that it can only be a black hole of misunderstanding, sucking in and dismembering all possibility of communication.

    At the very least it illustrates that you haven’t read or understood anything in these discussions regarding connectability of functional spaces.

  46. stcordova: I will donate $50 to the New Mexicans skeptic organization that you are a member of if you can write a GA which will converge on the complex specified informaiton string (a password if you will) that I have wrtitten explicitly on a sheet of paper. You have 2 months to solve it and publish your results.

    This could only be written by someone who either does not understand how a genetic algorithm works or is not interested in having a productive dialogue. Possibly both.

  47. stcordova: Patrick,

    You were intelligently designing the fitness function weren’t you?

    I’ll be happy to discuss this issue with you if you can explain how it applies to the errors I pointed out in the paper.

  48. stcordova:

    I will donate $50 to the New Mexicans skeptic organization that you are a member of if you can write a GA which will converge on the complex specified informaiton string (a password if you will) that I have wrtitten explicitly ona sheet of paper.

    You write this as though the term “complex specified information” has a referent in the real world. Whenever I have asked an ID proponent to define CSI with sufficient mathematical rigor to allow different individuals to calculate it for the same artifact and obtain the same result, I have not received an answer. Can you do so?

    In the context of this topic, what is the CSI of the bit string representing the optimal solution to the Steiner problem posed by Dave Thomas?

  49. Dave,

    Your programs don’t have anything to do with natural selection nor the modern synthesis.

    When a programmer writes a program to do something, and it does it, then it did so by design, Dave.

    ID says evolution proceeds by design, Dave- as in a GA/ GP

  50. stcordova:
    Patrick wrote:

    No “Darwinist” (a term that reflects ID’s creationist roots) claims this.

    So are you saying there ARE complex biological systesm which natural selection can’t create.

    If you say, yes, then well, thanks for helping creationists.

    If you say no, then, on what basis do you make that claim except by assumption.

    While I readily admit that I’m always working to improve as a writer, I don’t see how one could, in good faith, put those particular words in my mouth based on what I wrote. Here’s the full context of the line you quoted:

    There are several statements in the paper that suggests the authors have some fundamental misunderstandings of genetic algorithms and the observed phenomena on which they are based. As early as page 2, for example, is this:

    The Darwinist claim is that no such assistance is required. Rather, natural selection is innately capable of solving any biological problem that it faces.

    No “Darwinist” (a term that reflects ID’s creationist roots) claims this. Extinction is known to happen.

    Pointing out that species are known to go extinct is just one easy way of identifying the error with the authors’ claim. Some problems, significant ecological change for example, clearly aren’t solved by known evolutionary mechanisms, particularly under a time constraint.

    This statement is a baseless, clearly incorrect assertion, one of many errors in the paper.

  51. LoL! CSI only applies to that which can be broken down into bits. And all you do is see if it exists or not. IOW chalk up CSI as another ID term Patrick doesn’t understand.

  52. Some problems, significant ecological change for example, clearly aren’t solved by known evolutionary mechanisms, particularly under a time constraint.

    Evolution can only really solve the problem of making one runner faster than another when both are being chased by the tiger.

    Doesn’t do much good if there are two tigers.

    Species go extinct. So far, life hasn’t.

  53. Hmmm. The last time I checked, GAs do a great job on problems for which the ‘fitness landscape’ is reasonably smooth/continuous, and are, likewise, known to suck at problems for which the ‘fitness landscape’ is discontinuous — like, say, the one-vertical-spike-rising-out-of-a-zero-fitness-plane ‘fitness landscape’ which is the find this password problem Mr. Cordova proposes.
    Now, why did Mr. Cordova ask Dave to write a GA to solve a problem of exactly the sort which GAs are known to suck at? Mr. Cordova’s answer to this question could be instructive. I say ‘could be instructive’ because if Mr. Cordova’s past track record is at all indicative of his future behavior, the odds of Mr. Cordova answering that question are exceedingly low, if not zero. Did Mr. Cordova do this because he was ignorant of the operational characteristics of GAs, or did he do this because… how shall I put it… he was deploying a rhetorical gambit for some unspoken reason, or what?

    When faced with a commenter who quote-mines the people with whom he’s interacting, the most parsimonious explanation for that behavior is that said commenter is a deceitful son of a bitch. But our hostess’ ground rules prohibit that interpretation, so another explanation must be found. For purposes of discourse on this site, I believe the most parsimonous explanation among those which are allowed here is that quote-miners (and deceitful people in general, particularly those whose track records are filled with deceit) have severe intellectual deficits, perhaps due to brain damage.

  54. I will donate $50 to Sal’s favorite charity if he can name an even number prime greater than 2.

    Haven’t we been at this for decades? Is there no progress at all in the discussion?

  55. petrushka: Haven’t we been at this for decades? Is there no progress at all in the discussion?

    Progress in creationism, that’s an oxymoron.

  56. Sorry, Salvador, but I don’t think I’m interested in your “challenge.”

    Its not a matter of your interest, Dave, but returning a favor. You ASKED me to participate in your steiner problem. I obliged. You obviously are unwilling to reciprocate.

    Is it because you are uninterested or unable to meet the terms of the challenge? :-) Besides, you have a $50 incentive for the furtherance of your non-profit skeptic society.

    It seems to me the issue is not whether you are interested, but rather a GA is unable to solve the problem. Is that the case? :-) If that’s the case, say so.

    Given that I obliged you in the past at your request, you have to at least confess GA’s can’t solve most problems regarding a search.

    In any case, thanks for displaying your refusal to reciprocate. I suppose you don’t like it that I can pose a challenge for your GA’s which GA’s can’t solve. But you see, that’s the problem. You focus on problems which GA’s can solve and ignore the far larger set of problems which GA’s cannot solve.

    Is the complexity in biology something that biological GA’s can solve or not? Simply showing that the GA can solve a steiner problem is no proof GA’s can solve complexity in biology since I demonstrated, GA’s can’t solve a large class of search problems!

    Even supposing a GA can solve the problem, without the correct fitness function, without the continued operation of the GA (assumption of no extinction of the entire species), without replicators and genes (the assumption of OOL), etc. there is no evoution of complexity.

    Consider the case of Gammarus MInus. Real world GA’s destroyed eyes, they didn’t construct them. So why does one believe selection will select for complexity, when real world examples show that it does not (not the least of which are large examples of extinction and genetic deterioration).

    Your Steiner soluton can’t be generalized to all complexity in biology without great leaps of assumption. Assumption is fine, but it is not the same as fact. I provided a counterexample of systems which GA’s can’t solve.

    You seem disinterested, but the least you could do is say, “GA’s can’t solve many problems unless they have a target to converge on, either explicitly or implicitly described. We don’t know for a fact that biological GA’s can create the complexity we see in biology.”

    The target in the steiner problem was a representation of the physical solution. Unless the description of the constraints were provided (as in front-loaded) into the computer, the program would not converge on a representation of the real-world physics. You failed to point out, the intelligent designer of the code had to choose a correct fitness function, otherwise the GA would not converge on the desired target.

    Anyway, thanks for responding. It was informative.

  57. You seem disinterested, but the least you could do is say, “GA’s can’t solve many problems unless they have a target to converge on, either explicitly or implicitly described.

    You seem incapable of understanding what is being said.

    It is not the existence of the target that is at issue, but the characteristics of the landscape. GAs cannot find an isolated target.

    They can move a population to have more of some characteristic, but they do not need to know about targets or goals.

    If there is only one (yes or no) level of fitness, GAs are not useful.

  58. Patrick:

    known evolutionary mechanisms are quite capable of generating solutions to problems that are not amenable to random search.

    Not true. They are capable of generatings solutions for things they are capable of generating solutions for — a tautology. They are not capable of solving passwords or analogous IC systems without specialized information about the target.

    I gave an example of a search which an evolutionary algorithm won’t do very well. Biology is replete with signalling systems that are analogous to passwords, and lock-key systems. Even wiki-uses the lock-key analogy:

    http://en.wikipedia.org/wiki/Docking_(molecular)

    You can see, the GA needs a lot of computational horsepower to solve the docking problem. This is far more problematic than the steiner problem, and this level of complexity is relevant since at some point if our best computers and software can’t solve the docking problem, why should we expect biological GA’s to do better? In fact, the abundance of extinction and lack of evolving large numbers of new docking solutions suggest the GA’s in the real world didn’t create the lock-key systems in biology.

    I expect we might solve the docking problem with computational GA’s some day, but biology doesn’t work like a human made GA. Real biology destroys species and eyes and all sorts of other complexity. There aren’t real-time observations of real world biology building novelty as fast as it destroys it.

    Real world evolution is destructive not constructive.

  59. stcordova: Is it because you are uninterested or unable to meet the terms of the challenge?

    It may be beneficial and more productive for everybody involved if you would read the ENTIRE answer someone provides: Dave clearly told you why he is uninterested: your “challenge” has nothing to do with evolution.

    stcordova: It seems to me the issue is not whether you are interested, but rather a GA is unable to solve the problem.

    That may well be the case. But, as Dave pointed out, whether or not a GA would be able to solve the problem is uninteresting, because the problem is irrelevant to evolution.

    stcordova: You focus on problems which GA’s can solve and ignore the far larger set of problems which GA’s cannot solve.

    Of course. He focuses on problems that are relevant to evolution. You imply that it is somehow an issue for evolution that GAs can’t solve any and all manner of problems? How exactly is the abilitiy to solve any and all manner of problems in general, or your specific kind of problem in particular, relevant to evolution?

    stcordova: Even supposing a GA can solve the problem, [...] without the continued operation of the GA (assumption of no extinction of the entire species), [...] there is no evoution of complexity.

    Ummmm, yes. If a species goes extinct, there is no complexity evolving in it any more. There are no traits whatsoever evolving in this species anymore. Are you somehow under the impression that anyone here thinks that evolution occurs in the absence of extant specimens?

  60. stcordova: Its not a matter of your interest, Dave, but returning a favor. You ASKED me to participate in your steiner problem. I obliged. You obviously are unwilling to reciprocate.

    Yes, Dave should have known better.

  61. stcordova: I gave an example of a search which an evolutionary algorithm won’t do very well. Biology is replete with signalling systems that are analogous to passwords, and lock-key systems. Even wiki-uses the lock-key analogy:

    A scientist can read that Wiki example and understand the process and the metaphors used to describe it.

    An ID/creationist reads it literally without the slightest comprehension of the underlying chemistry and physics.

  62. olegt: John Holland, the father of genetic algorithms, thinks otherwise. Adaptation in Natural and Artificial Systems.

    This is the original book from the 70s about the theoretical basis for genetic-style adaptation, and the surprising parallels between evolution, gambling, and learning in general. foundational, clear, mathematical.

  63. stcordova: Real biology destroys species and eyes and all sorts of other complexity. There aren’t real-time observations of real world biology building novelty as fast as it destroys it.
    Real world evolution is destructive not constructive.

    This is a human projecting human aspirations and values onto nature. It is called animism. ID/creationism is a primitive throwback to those early times in the evolution of religion.

    Science has since learned about soft matter. There are no surprises here.

  64. Genetic algorithms are based on mimicking with a computer the processes and laws found in nature.

    But the impressions I get of the vast majority of ID/creationist camp followers is that they don’t comprehend even middle school science; even after some supposedly obtain a college degree.

    Here, for example, are science standards for the state of California.

    As a specific example, on page 136, under “Focus on Physical Sciences” we find some very basic concepts and terminology that are expected of eighth graders.

    I would suggest that most ID/creationist followers don’t know any of this material; nor have they had any of it reinforced with high school chemistry, physics, and biology.

    Even eighth graders are expected to know something about the states of matter. Implicit in that knowledge – and extended and reinforced in high school chemistry, physics, and biology – is the understanding that matter interacts with matter and condenses. Many elements and compounds can exist in solid, liquid, or gaseous states. Elements and compound have names. Elements and compounds have melting points and vaporization points.

    When one gets to chemistry and physics, one can find tables of the melting and vaporization temperatures of elements and compounds. Notice that elements and compounds are not called “water” when they melt. They go by their elemental or compound names. Eighth graders know this.

    This is basic middle school and high school knowledge; but it is knowledge not evident among ID/creationist followers. For a normal, curious student, this basic knowledge leads to questions about deeper properties and behaviors of matter and energy; like, “What are the underlying rules for the structure of matter?” But with ID/creationists, it just produces a blank stare and a series of snarky remarks like, “naturalism can’t explain anything.”

  65. Salvador,

    It’s certainly true that a GA cannot find a small target in a large informational void. Nor can any biological process. Nor can an intelligent designer.

    I posed essentially the same challenge as you on UD three years ago, except I was challenging the human readers to crack the password (actually to reverse a one-way hash — same principle). The point is that humans, just like nature, require “active information” to find solutions. The password example is a good illustration of the fact that Dembski’s “information accounting” framework is useless for distinguishing between intelligent and natural causes.

  66. stcordova:

    known evolutionary mechanisms are quite capable of generating solutions to problems that are not amenable to random search.

    Not true.

    My claim is clearly supported by the data and arguments in my original post and by the existence proof of my working code. Simple crossover and single point mutations converge on a solution that is not readily found by random search.

    If you disagree, please address the data and arguments presented.

  67. stcordova: Not true.They are capable of generatings solutions for things they are capable of generating solutions for — a tautology.They are not capable of solving passwords or analogous IC systems without specialized information about the target.

    I gave an example of a search which an evolutionary algorithm won’t do very well.Biology is replete with signalling systems that are analogous to passwords, and lock-key systems.Even wiki-uses the lock-key analogy:

    http://en.wikipedia.org/wiki/Docking_(molecular)

    You can see, the GA needs a lot of computational horsepower to solve the docking problem.This is far more problematic than the steiner problem, and this level of complexity is relevant since at some point if our best computers and software can’t solve the docking problem, why should we expect biological GA’s to do better?In fact, the abundance of extinction and lack of evolving large numbers of new docking solutions suggest the GA’s in the real world didn’t create the lock-key systems in biology.

    I expect we might solve the docking problem with computational GA’s some day, but biology doesn’t work like a human made GA.Real biology destroys species and eyes and all sorts of other complexity.There aren’t real-time observations of real world biology building novelty as fast as it destroys it.

    Real world evolution is destructive not constructive.

    Ah, so “Real world” evolution does occur but it only destroys things, eh? Gee whiz, your omnipotent, omniscient designer/creator god sure is a nice guy for designing/creating evolution so that it would only destroy things. That’s so loving and merciful.

    According to the other IDiots who accept that evolution occurs, “the designer” designed and programmed the ability to evolve into living things. They claim that “the designer” created, designed, and programmed complex specified information into living things and that it’s that programming that drives everything in living things, which of course would include survival success or failure (are you paying attention joe?).

    So, if evolution is driven by the programming (algorithm) that was designed, created, and installed by “the designer” (and either sometimes, regularly, or constantly tinkered with by “the designer” according to various IDiots), why is it that evolution only destroys but doesn’t construct? How can there be millions/billions of years of life and evolution if the programming was designed only to destroy? How can there be the diversity of life, and its long and diverse history, if “the designer’s” goal was and is to program only destruction into the evolutionary process of living things?

    Did your all knowing, all powerful designer/creator god ignorantly screw up the intentionally destructive programming, and is that how many living things have managed to survive and evolve successfully, or is your designer god just playing a long drawn out sadistic game with living things by letting some of them survive and evolve successfully for awhile until it decides to adjust the programming so that they die out, with the ultimate goal being the destruction of every living thing everywhere?

  68. Joe G:
    GAs are design mechanisms and having nothing to do with natural selection nor evolutionism.

    Even though your entire comment is just the usual nonsensical gibberish, I’ll take a stab at responding to it.

    I notice that you chose the word “evolutionism”. Why did you add “ism”? Why not just ‘evolution’?

    I seriously doubt that any evolutionary scientist would claim that GAs have anything to do with “evolutionism”. They just might claim that the GA programs they use in their computers help them to understand the processes of evolution though. :)

    YOU and some other IDiots are the ones who claim that all evolutionary processes themselves (in nature) are completely dependent on and driven by the alleged GAs that you claim were/are designed, created, and installed in living things and the whole universe by “the designer”, and some of you IDiots claim that those GAs are sometimes, regularly, or constantly tinkered with by “the designer”. In other words, according to you and some other IDiots, evolution has everything to do with GAs.

    So, since your comment about “evolutionism” is entirely irrelevant, you must have meant to say the word ‘evolution’ instead, which of course makes you look like the fool you are because YOU constantly claim that GAs are what drives evolution.

    Contradict yourself much?

    One more thing for now joe, going by your definitions, and since you accept that evolution occurs, you must be an evolutionist, which means that you practice “evolutionism”, and since you claim that “the designer” designed and installed necessary GAs in evolutionary processes, you’re actually saying that your “evolutionism” has everything to do with GAs.

    I’d suggest that you make up your mind but as “we” all know……

  69. stcordova: Its not a matter of your interest, Dave, but returning a favor.You ASKED me to participate in your steiner problem.I obliged. You obviously are unwilling to reciprocate.

    Is it because you are uninterested or unable to meet the terms of the challenge?:-)Besides, you have a $50 incentive for the furtherance of your non-profit skeptic society.

    It seems tome the issue is not whether you are interested, but rather a GA is unable to solve the problem.Is that the case? :-) If that’s the case, say so.

    Given that I obliged you in the past at your request, you have to at least confess GA’s can’t solve most problems regarding a search.[

    Nobody disputes this, Salvador. The No Free Lunch theorems are perfectly good theorems. Averaged over all problems, GAs will perform no better than chance.

    The issue is not whether GAs can solve all problems. They can’t, and, specifically, they can’t solve problems that exist in an unconnected fitness landscape, as yours does.

    On the other hand, if you were to give feedback to the algorithm as in “warmer… no colder… warmer again…” it probably could.

    Dembski is therefore absolutely right, but also absolutely irrelevant. The question is not “Can GAs solve any problem?” but “Can GAs solve the kinds of problems solved by biological populations”?

    In any case, thanks for displaying your refusal to reciprocate.I suppose you don’t like it that I can pose a challenge for your GA’s which GA’s can’t solve.But you see, that’s the problem. You focus on problems which GA’s can solve and ignore the far larger set of problems which GA’s cannot solve.

    And this is a demonstration of just how you have missed the point. We are all perfectly happy that you have posed a challenge for GAs which GAs can’t solve. We know there are far more problems that GAs can’t solve than problems that GAs can solve. The reason we “focus on problems which GAs can solve and ignore the far larger set of problems which GAs cannot solve” is that the problems that GAs can solve are precisely the kinds of problems that biological populations solve! I.e. problems in which the similar organism have similar fitness in similar enviroments. Your problem is not one of these, clearly. In a GA that attempted to solve your problem, all possible organisms except one would have identically awful fitness, while one would have perfect fitness. Clearly the GA would no better than random search for that problem.

    Is the complexity in biology something that biological GA’s can solve or not? Simply showing that the GA can solve a steiner problem is no proof GA’s can solve complexity in biology since I demonstrated, GA’s can’t solve a large class of search problems!

    GAs can solve problems where similar genotypes have similar fitness. This is true of the Steiner problem. It’s true of biology. It’s not true of your problem.

    Even supposing a GA can solve the problem, without the correct fitness function, without the continued operation of the GA (assumption of no extinction of the entire species), without replicators and genes (the assumption of OOL), etc. there is no evoution of complexity.

    This makes no sense.

    Consider the case of Gammarus MInus.Real world GA’s destroyed eyes, they didn’t construct them.So why does one believe selection will select for complexity, when real world examples show that it does not (not the least of which are large examples of extinction and genetic deterioration).

    Selection doesn’t “select for complexity”, at least not complexity in the sense in which you seem to be using the term (by definition, a selected solution will have “specified complexity”) i.e. a complex structure. Selection “selects for” reproductive success. In fact that’s tautological – “selection” simply is the phenomena whereby genotypes that tend to give rise to more reproductively successful phenotypes become more prevalent. If simplicity contributes to reproductive success then simplicity will be “selected for”. The simple solution may nonetheless have “specified complexity”, just as a row of 100* heads has “specified complexity” despite the fact that it is a far “simpler” sequence than a pattern of heads and tails.

    Indeed, Dembski’s informal description of a “specified” pattern is an “easily described” pattern. So I think you have fallen foul of an inadvertent equivocation here.

    Your Steiner soluton can’t be generalized to all complexity in biology without great leaps of assumption.Assumption is fine, but it is not the same as fact.I provided a counterexample of systems which GA’s can’t solve.

    Indeed you did. And I’m sure any of us could readily come up with thousands more. We could even point to the NFL theorems to demonstrate that they must vastly outnumber the systems that GAs can solve! You are preaching to the choir, here!

    You seem disinterested, but the least you could do is say, “GA’s can’t solve many problems unless they have a target to converge on, either explicitly or implicitly described.We don’t know for a fact that biological GA’s can create the complexity we see in biology.”

    No, because that would not be true. The issue is not whether “they have a target to converge on” but whether fitness space is connected. There could be many solutions to a problem, and yet GAs could reliably find some but not others, depending on which solutions are connected in fitness space. For example, wheels would be a great solution to mobility for multicellular animals, but none of us have wheels. That is probably because wheels are in an unconnected part of fitness space, and can only be reached by intelligent agents (e.g. us). For unicellular animals, however, they seem to be connected, and indeed, bacteria have evolved rotors.

    The target in the steiner problem was a representation of the physical solution.

    There was no target. There was only a set of criteria – a problem to solve – which the Steiner solution happens to meet/solve better than any other. Sometimes the solution reached was the Steiner solution, sometimes it wasn’t. What happened, reliably, was that final solutions were better than “starting” solutions. Exactly as in biology, which has no “target”, merely problems to solve (reproducing within the current environment, its resources and hazards), and solutions that are better than other solutions.

    Unless the description of the constraints were provided (as in front-loaded) into the computer, the program would not converge on a representation of the real-world physics. You failed to point out, the intelligent designer of the code had to choose a correct fitness function, otherwise the GA would not converge on the desired target.

    You have got this backwards, and as a result, your argument is circular. Clearly a program cannot solve a problem unless you present it with the problem!

    You have identified three entities where there are only two . You think there is a Problem, a Fitness Function and a Target. All there is the Problem and the Solutions. The problem IS the fitness function, and the “Target” is any solution that solves the problem better than some other solution.

    In Patrick’s GA, the problem is minimising the lengths of the connectors between the nodes. Therefore the fitness function is “small lengths of the connection between the nodes”. The solutions (“targets”) are solutions with small lengths of connection between the nodes.

    In biology, the problem is something that enhances reproduction (which could be minimising something like surface area to volume). The fitness function is therefore “small surface area to volume”. The solutions are anything that results in small surface area to volume.

    The “active information” lies simply in the problem. It doesn’t need to be put there “intelligently” (although clearly, in a computer GA it is). It just needs to be a set of environmental resources and hazards in which a population of self-replicators is situated.

    Anyway, thanks for responding.It was informative.

    It was, but I think you misunderstood the information :)

    ETA: *500 if it is to fall within Dembski’s rejection region for his chance hypothesis. Thanks to Joe F for pointing this out.

  70. Elizabeth, that was a very clear, very appropriate, and very telling criticism of Sal Cordova’s statements about genetic algorithms and of his “challenge”. Sal has avoided dealing with the original post, which showed clearly s csse where GAs do far better than random search.

    I’d modify your statements in two ways, however. First, Dembski’s Complex Specified Information is achieved by tossing 500 heads in a row, not 100. Second, Dembski is not “absolutely right” about the No Free Lunch Theorem. He jumps from behavior averaged over all possible fitness surfaces to the unsupported conclusion that this behavior is relevant to the fitness surfaces found in biology. He has never said “I guess I was wrong about that”.

    Will Sal Cordova address the points in your comment? The point In the original post?

  71. I notice that you chose the word “evolutionism”. Why did you add “ism”? Why not just ‘evolution’?

    Because I do not want to equivocate- ID is OK with ecvolution. Evolutionism refers to the untestable premise that necessity and chance produced the diversity of life starting from some population(s) of prokaryote-like organisms.

    They just might claim that the GA programs they use in their computers help them to understand the processes of evolution though.

    Yup, evolution by design.

    YOU and some other IDiots are the ones who claim that all evolutionary processes themselves (in nature) are completely dependent on and driven by the alleged GAs that you claim were/are designed, created, and installed in living things and the whole universe by “the designer”, and some of you IDiots claim that those GAs are sometimes, regularly, or constantly tinkered with by “the designer”. In other words, according to you and some other IDiots, evolution has everything to do with GAs.

    Man you are dense. GAs = evolution by design.

    Obvioulsy you have serious issues…

  72. GAs are design mechanisms, Elizabeth. They do not mimic nature. They do not mimic natural selection.

    BTW the target is that problem to be solved…

  73. Joe G:
    Well reality says otherwise oleg. There are no targets/ goals in nature, duh.

    You’d think that by now Joe G would have figured out that genetic algorithms don’t have targets. Amazingly, he hasn’t. Simple ideas have trouble penetrating six inches of bone.

  74. Joe G:
    LoL! Of course GAs have a target/ goal- they are written to solve problems.

    No, Joe. Solving a problem is the goal of the person who writes a genetic algorithm. Not of the algorithm itself.

  75. Joe G:
    GAs are design mechanisms, Elizabeth. They do not mimic nature. They do not mimic natural selection.

    This is simply incorrect, Joe. GAs do mimic nature. That’s why they are called GAs.

    BTW the target is that problem to be solved…

    And if you define “target” as “the problem to be solved” then you agree with my comment to Sal that there are only two entities here, not three: the problem aka target; and the solution.

    GAs find solutions to problems. You do not “smuggle in” to a GA the solution by providing the problem, any more than an exam paper “smuggles in” the answers in the form of the questions!

  76. Again if a programmer writes a GA to solve a problem and the GA soves it, then it solved it by design.

    Solving a problem is the goal of the person who writes a genetic algorithm. Not of the algorithm itself.

    They are one in the same. The GA is an extension of the programmer.

  77. Yes, if you use his definition that includes his UPB, it will take 500 heads in a row to hit the jackpot :)

    Thanks.

  78. GAs might be said to mimic nature, but they do not. They mimic engineering trial and error.

    Yes GAs find solutions to problems because they are designed to do so. And we have already been over the other stuff- why do you bring it up, again?

    No need to have the specified target nor the specified path- geez read the paper Patrick is trying to refute.

  79. Once again, from the paper-

    The above quote shows that Thomas is under the misapprehension that intelligent design advocates claim that the actual answer is encoded into the algorithm. This is not in fact what intelligent design advocates claim, as will be shown later. Rather, we say that success is due to prior knowledge being exploited to produce active information in the search algorithm. Although the code does not include the actual Steiner shape, it does include a tuned algorithm for how to find the Steiner shape.

  80. Joe G:
    If a programmer writes a GA to solve a problem, and it solves it, then it did so by design, period.

    He does, but that is beside the point. The designer employs a genetic algorithm to achieve that goal. The algorithm has no goal. The algorithm relies on heritable variation and selection. This is what a genetic algorithm does. By definition.

    A word of advice, Joe. Learn definitions before attempting an argument. :)

  81. The genetic algorithm has the same goal as the designer as the GA is just an extension of the designer.

    But I understand that you have to engage in semantic quibbling seeing that you have nothing else…

Leave a Reply