Posted by Dave Thomas on September 1, 2006 | Comments (161)

As promised, hot off the presses, here is a little tutorial I’ve decided to call Genetic Algorithms for Uncommonly Dense Software Engineers. Given some of the bizarre commentary issuing from the ID community over at Uncommon Descent regarding my past posts on Genetic Algorithms, I’ve developed this guide to help the folks over there figure out if the Genetic Algorithms (GAs) they are working on employ a “fixed-target” approach (like Dawkins’s Weasel), or if they are instead un-targeted, like most GAs used in research and industry are.

dummies2.jpg

Continue reading  “Genetic Algorithms for Uncommonly Dense Software Engineers

Posted by Dave Thomas on August 21, 2006 | Comments (164)

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

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

smalGrid.gif

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

critters.gif

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

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

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

Continue reading  “Design Challenge Results: "Evolution is Smarter than You Are"

Posted by Dave Thomas on August 16, 2006 | Comments (79)

In July, I described a Genetic Algorithm that, unlike Dawkins’ “Weasel” experiment, specifies no fixed “Target” for the simulation, but instead rewards those members of the current population which use fewer or shorter segments to connect a fixed set of points. As the algorithm progresses, it finds a multitude of answers for the math problem called “Minimization of Steiner Trees,” i.e. the shortest possible straight-line networks connecting the fixed points.

Last Monday, I posted Take the Design Challenge, wherein I called for solutions to a tricky little 6-point network. Next Monday, I will announce the winners (there are 20 entries already, several with true Steiner Solutions, and others with almost-as-good “MacGyver” solutions).

Imagine my surprise, then, when I found Salvador Cordova at Uncommon Descent spewing blatant falsehoods about this work. I was shocked - shocked, I say - to catch the UD Software Engineers in a lie. And quite a lie it is - with the help of mathematicians like Carl Gauss, I’m going to lift the veil from the obfuscations of IDers, and prove it’s a Lie, much as you would prove a mathematical theorem.

Continue reading  “Calling ID's Bluff, Calling ID's Bluff...

Posted by Dave Thomas on August 14, 2006 | Comments (83)

Since posting my essay on Genetic Algorithms, I’ve since developed a brand-new C++ version of my Steiner Networks genetic algorithm, a vast improvement over the old Fortran number-clunker I developed five years ago.

And already, the new code is leading to some very interesting results.

In light of William Dembski’s remarks in No Free Lunch, basically arguing that in all Genetic Algorithms,

… the fitness function … is well-defined and readily supplies the complex specified information that an optimal crooked wire genetic antenna [or any other problem solved with Genetic Algorithms] seems to acquire for free,

I’m giving Intelligent Design proponents (and everyone else!) a chance to actually Design something!

As you recall, my algorithm involves finding Steiner Trees, the shortest networks of straight-line segments connecting a given collection of fixed points. These networks may include additional variable “Steiner Points” where segments may meet.

The Challenge
Here is a collection of six fixed points. Designers, send your candidates for the Steiner Solution for this particular 6-point system to me at nmsrdaveATswcp.com (replace the AT with an @ if you please).

6nodeGrid.gif

I will announce the winners (if any) in a week’s time, and also will present the answer that Evolution came up with. I’m interested in proposed solutions from any and all (you don’t have to be in the ID camp), but am especially interested in solutions by ID advocates, since y’all are saying that the solution is already implicitly defined in the statement of the problem (finding shortest connected networks).
Here’s a Hint:
4steiner.gif

Continue reading  “Take the Design Challenge!

Posted by Jason Rosenhouse on July 15, 2006

Readers of this blog are doubtless familiar with the Discovery Institute's anemic list of scientists who “dissent from Darwinism.” The list is sadly short on biologists, forcing the DI to accept anyone with a PhD in any branch of science as a possible signatory.

Casey Luskin attempts to defend this practice by explaining why mathematicians are supremely well-placed to offer authoritative pronouncements on the merits of evolutionary theory.

Over at EvolutionBlog, I have replied to his desperate sputterings. In Part One I discuss the question of whether mathematicians, or non-biologists generally, have any authority to be discussing evolutionary theory. In Part Two I consider Luskin's thoughts on the matter. Comments can be left there. Enjoy!

Posted by Dave Thomas on July 8, 2006

Here follows the guts of my new C++ program for solving Steiner Tree problems with a Genetic Algorithm.

I have eliminated much of the Microsoft Foundation Class support code, focusing mainly on the number-crunching routines. I will be happy to share the complete code with interested parties.

The original FORTRAN version from five years ago is still online at NMSR.

You’ll see that I’ve cleaned up and organized everything quite a bit, and completely re-done the snippet which checks for properly connected solutions.

Dave
August 21st, 2006

Continue reading  “Steiner Genetic Algorithm - C++ Code

Posted by Dave Thomas on July 5, 2006 | Comments (125)

Genetic Algorithms are simplified simulations of evolution that often produce surprising and useful answers in their own right. Creationists and Intelligent Design proponents often criticize such algorithms for not generating true novelty, and claim that these mathematical recipes always sneak the “answer” into the program via the algorithm’s fitness testing functions.

4steiner.gif

There’s a little problem with this claim, however. While some Genetic Algorithms, such as Richard Dawkin’s “Weasel” simulation, or the “Hello World” genetic algorithm discussed a few days ago on the Thumb, indeed include a precise description of the intended “Target” during “fitness testing” on of the numerical organisms being bred by the programmer, such precise specifications are normally only used for tutorial demonstrations rather than generation of true novelty.

In this post, I will present my research on a Genetic Algorithm I developed a few years ago, for the specific purpose of addressing the question Can Genetic Algorithms Succeed Without Precise “Targets”? For this investigation, I picked a math problem for which there is a single, specific answer, yet one for which several interesting “quasi-answers” - multiple “targets” - also exist.

PT readers, you are about to enter the Strange and Curious world of “The MacGyvers.” Buckle up your seat belts, folks - our ride through Fitness Landscapes could get a little bumpy.

Continue reading  “Target? TARGET? We don't need no stinkin' Target!

Posted by Jeff on March 18, 2006 | Comments (78)

I don’t know about you, but whenever I want to learn about information theory, I naturally turn to the creationists. Why, they know so much about geology, biology, and paleontology, it only seems reasonable that their expertise would extend to mathematics and computer science.

Take Nancy Pearcey, for example. Here, for example, we learn that Ms. Pearcey has studied philosophy, German, and and music at Iowa State; that she has a master’s degree in biblical studies; that she is a senior fellow at that temple of truth, the Discovery Institute; and that for nine years she worked with former Watergate conspirator and convicted criminal Charles Colson on his radio show, “Breakpoint”. Why, those seem exactly the sort of credentials one would want in an instructor of information theory…

Read more at Recursivity.

Posted by Pim van Meurs on February 23, 2006 | Comments (13)

Forget prime numbers in the movie “Contact”, your own last name may be encoded in your DNA, reports Science

Paging Mr. Chromosome Your last name may be encoded in your DNA

A genetic study of British men finds a one in four chance that two strangers with the same last name share an ancestor. The relationship implies that certain surnames have a unique DNA signature–a fact that could help police narrow down suspects in some unsolved cases. But the criminally intent John Smiths of the world need not worry, because the signatures are found predominantly for rare surnames.

Now that’s a ‘Design Inference’

Posted by Jason Rosenhouse on September 19, 2005 | Comments (12)

Part Two of my column about probability and evolution is now avaialable at CSICOP's Creation Watch site. Enjoy!

In part one I considered the classic anti-evolution arguments based on probability theory, and showed why they failed. In part two we disucss why it is no improvement to add “specification” to the mix. We also examine some of the ways probability theory can be used legitimately to shed light on evolution.

Posted by Reed on August 26, 2004

It has been a while since the last EvoMath.  In this installment I am going to begin to discuss classical selection theory.  Selection occurs when certain alleles are likely to transmit more copies of themselves to the next generation than other alleles at the same locus.  The simplest way to think of this is in terms of the viabilitity of individuals.  If an individual dies before it can reproduce, then it is not able to transmit its genes.  If such a death was influenced by the genes it carried then selection can occur.  Classical selection theory assumes that there exists viability selection and that it is constant, i.e. independent of allele or genotype frequencies.  There is also theory behind frequency-dependent selection, but it beyond the scope of this article.

Read the rest at De Rerum Natura

Posted by Reed on August 24, 2004 | Comments (6)

I’m working on a new installment of evomath.  This one is going to be some simple  examples of classical selection theory.  I am probably going to post it on my blog because it is using features of a new version of Kwickcode that I haven’t setup on PT.  I think I am going to wait until PT makes the switch to MT 3.1 before I install version 2 of my plugins here.

Now to encourage me to keep on track with my series, I want readers to make requests.  Is there any particular part of evolutionary theory that you would like me to cover?  Is there something you didn’t quite get from your days as an undergraduate that you want to see again?  Etc.

Posted by Pim van Meurs on August 12, 2004 | Comments (6)

Note that Dembski has uploaded a revised manuscript which now correctly attributes the measure to Renyi and thanks the many critics for their contributions

I am not a mathematician but let me give it a try and others can amend and revise my comments.

The Kantorovich/Wasserstein distance metric is also known under such names as the Dudley, Fortet Mourier, Mallows and is defined as follows.

d_p(F,G) = \overset{\inf}{\tau_{x,y}} \lbrace E |x-y|^{\frac{1}{p}} \rbrace

where E(x) refers to the expectation of the random variable x and \inf means that the minimum is sought on all random variables X which take a distribution F and random variables Y which take a distribution G.

where \tau_{x,y} is the set of all joint distributions of random variables X and Y whose marginal distributions are F and G.

Continue reading  “A quick explanation of Wasserstein Metric

Posted by Reed on May 30, 2004

Genetic Drift

EvoMath is back from a long hiatus.  In this edition I will briefly touch on genetic drift and coalescence theory.  Genetic drift is the evolutionary force whereby allele frequencies fluctuate due to chance because the alleles in a generation are a random sample of the alleles in previous generation.  To help understand what I am talking about, consider a heterozygous father, with genotype Aa.  Under Mendelian heredity, he will pass on the A allele 50% of the time and the a allele the other 50% of the time.  If he has only one child, then he clearly cannot pass on both of his alleles, and thus one of those alleles—say a—will be lost from his lineage.  The remaining allele, A, will then have “drifted” to 100% or “fixation.”  If he has more children, then he may pass on both of his alleles, but it is not likely to be exactly at a 50:50 ratio.

Genetic drift occurs whenever a population has a finite size, and since all populations are finite, it occurs in all populations.  However, in large populations it can be very weak and thus negligible compared to other evolutionary forces.

Continue reading  “EvoMath 3: Genetic Drift and Coalescence, Briefly

Posted by Jeff on May 12, 2004 | Comments (56)

Two previous entries on this blog by John Lynch have discussed the scientific output (or lack thereof) of two intelligent design superstars, Jonathan Wells and Michael Behe. Despite claims that both of these ID supporters are actively engaged in research, Lynch documents that they have published little or no scientific research in the last six years. Now let's look at the record of another one of ID's superstars, William Dembski.

Continue reading  “Dembski's mathematical achievements

Posted by Reed on April 8, 2004

In the first installment of EvoMath, I derived the Hardy-Weinberg Principle and discussed its significance to biology. In the second installment I will demonstrate how to test if a population deviates from Hardy-Weinberg equilibrium.

Continue reading  “EvoMath 2: Testing for Hardy-Weinberg Equilibrium

Posted by Reed on April 4, 2004 | Comments (9)

The Hardy-Weinberg Principle states that a population satisfying certain primary conditions will not evolve. This result is very important because any departure from these conditions will result in an evolving population. Three scientists in the early 20th century (G.H Hardy, Wilhelm Weinberg, and W.E. Castle) independently discovered this principle which is now used as the null model of population biology.

Consider a group of interbreeding organisms (a population)…

Continue reading  “EvoMath 1: The Hardy-Weinberg Principle

Posted by Reed on April 2, 2004 | Comments (17)

Occasionally a creationist or an aideeist will make the wild assertion that biologists do not understand math/statistics and that math/statistics actually disproves evolution. This is followed by some random math argument based on ignorance of biology. The irony is that biologists probably understand math better than mathematicians understand biology, for the simple fact that biologists use math in their work more than mathematicians use biology in their work.

Continue reading  “EvoMath 0: An Introduction

Posted by Timothy Sandefur on March 31, 2004

A common charge of anti-evolutionists is to say "but what are the chances of this all happening by mechanistic and unguided processes?" Well, in this article (which I saw on Arts & Letters Daily), Freeman Dyson explains "Littlewood's Law of Miracles," which "states that in the course of any normal person's life, miracles happen at a rate of roughly one per month." Reminds me of how Richard Feynman used to put it. "Today on the freeway, I drove behind a car whose license plate was 3SVD543. Can you imagine how small the chances are of that happening?"

For more on the unremarkability of extremely rare coincidences, see chapter 7 of Richard Dawkins' magnificent Unweaving The Rainbow.