Genetic Algorithms for Uncommonly Dense Software Engineers

| 161 Comments

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

Background - the War of the Weasels For those readers wondering what this is all about, here’s a quick road-map to the key battles in this summer’s “War of the Weasels.”

Target? TARGET? We don’t need no stinkin’ Target! (Dave Thomas, July 5th, 2006) UDSE Response (scordova, July 9th, 2006) UDSE Response (scordova, July 14th, 2006)

Take the Design Challenge! (Dave Thomas, August 14, 2006) Tautologies and Theatrics (part 2): Dave Thomas’s Panda Food (scordova, Aug. 15th, 2006)

Calling ID’s Bluff, Calling ID’s Bluff (Dave Thomas, August 16th, 2006) Dave Thomas says, “Cordova’s algorithm is remarkable” (scordova, August 17th, 2006)

Antievolution Objections to Evolutionary Computation (Wesley R. Elsberry, August 18th, 2006)

Design Challenge Results: “Evolution is Smarter than You Are” (Dave Thomas, August 21st, 2006) Congratulations Dave Thomas! (davescot, August 22nd, 2006) Can humans compute better than computers? Dave Thomas’s design challenge (scordova, August 22nd, 2006)

Chapter 1: Check That Random Seed It may surprise some Uncommonly Dense Software Engineers (UDSEs) that the “random” numbers generated by compilers like C or C++ are not truly “random.” Rather, they are pseudo-random numbers, generated by an elaborate algorithm that uses a deterministic formula. These pseudo-random generators are usually initialized with the “seed,” a whole number that serves to start the deterministic formula off in a different place, leading to different “random” numbers.

If this seed is a constant, such as Zero (0), then the sequence of pseudo-random numbers will be exactly the same every time the program is run.

Of course, with this bad programming practice, there is no way the UDSE could determine if a given GA is targeted or not, because, even if it was not targeted, the result would always be the same.

Here is an example of this “no-no” in a supposed GA, scordova’s ga.c listing.

As another example, consider the use of a non-targeted algorithm, the Steiner GA, for a 5-node problem. Here, the seed for the random generator has been changed from something associated with the actual time of day to a constant, 0. As can be seen, the results of several generations (1000 here) always turn out the same. Everything turns out the same - the locations of every node, the connections between every pair of points, everything!

5n0Seed1.gif 5n0Seed2.gif

When the Seed is tied to time of day, however, the results of each trial of 1000 generations can be quite different, as shown in the following two trials. 5node1.gif 5node2.gif

Chapter 1 Summary: Change the Random Generator’s Seed Every Time.

Chapter 2: Is the Answer Always the Same?

If the random generator seed is properly initialized so that the sequence of “random” numbers is different every time, the next step is to run the GA several times, and see if the Answer comes out the same every time.

For example, if if the random seed in ga.c is changed, the result is always the same - the sum of the first 1000 integers is always computed as 500,500. Similarly, the result of running Dawkins “Weasel” algorithm is always the same phrase, “METHINKS IT IS LIKE A WEASEL.”

To illustrate what a real (un-targeted) GA looks like when it is switched over to look for a fixed Target, I added a special feature to my Steiner GA to calculate fitness in a different way from the usual method, where Fitness is simply the length of all segments of a particular candidate solution.

targetB.jpg

When the “Target” button is checked, the Fitness Test is changed from its normal length calculation to the number of “DNA differences” between candidates and a specific organism (represented as a String in the GA). I could have selected the actual Steiner Solution for the 5-point problem, but decided instead to make the “Target” a rather inelegant and overly long candidate far from the actual answer to the 5-point problem. 2874.jpg

Instead of selecting based on proximity to a target phrase like “METHINKS IT IS LIKE A WEASEL,” when the Steiner GA is run in Target Mode, it selects based on proximity to the string for the 2874-unit-long Kluge, target = “04614580132412507588758509TFFTFTFFTFFTFFTFFFFTFFFFFTTFFFFTTFFF”; // the Kluge

In subsequent runs, the Target is obtained every time. Here are two such runs; the first is an exact match to the Target (Fitness = number of DNA differences = 0), and in the second, the algorithm didn’t run quite long enough to get a perfect match to the Target, leaving it with a Fitness of 1. It certainly will achieve the precise target given more generations, however.

target1.gif

target2.gif

In summary, when a Fixed Target is employed, the GA converges to that Target every time it is run. Not surprising, actually!

Chapter 3: Is it just that Computers are Faster?

In his August 22nd response, Salvador Cordova of UD wrote the following:

Dave Thomas wrote:

What is it going to be like having to go to Bill Dembksi and admit that you’ve learned the hard way of the true meaning of what Daniel Dennett terms Leslie Orgel’s Second Law: “Evolution is smarter than you are”?

Thomas has proven no such thing, neither Dennett nor Orgel. Computers can compute certain things faster than us, that is why they exist to help us. For Thomas to argue that evolution is smarter than humans because computers can compute faster than humans is a non-sequitur.

This appears to be the Final Retreat of Intelligent Design theorists. Recall that they originally said that GA’s work only because the Answer is fed into the GA via the Fitness Test. But, given a problem with no obvious answer, and one for which a Genetic Algorithm actually out-performed ID theorist Cordova, the fall-back position is “But Computers are FASTER than humans!”

Unfortunately, the Problem Space for the 6-point Steiner Grid is incredibly large. Using the basic points+segments data structure, there are billions upon billions of different possible solutions.

I set up my GA to also look at completely random solutions for a long time. When the normal GA runs, it can complete 1000 generations (one evolutionary simulation) in a couple of minutes. It works out to examining about 8000 individual solutions every second. On the overnight run leading to the Design Challenge, the Steiner GA found one actual solution after 8 hours (Simulation #150), and found the other (different handedness) solution just 39 minutes later (Simulation #162). In the 300 Simulations of the overnight run, the very worst result had a length of 1877, or about 18% longer than the actual Steiner solution’s length (1586.5 units).

badGA.gif

Compare that to simply running one mindless random solution after another, at 8000 solutions per second. Here is the best result obtained in 14 hours from over 400 million individual solutions. This has a length of 2502 units, almost 58% longer than the formal 6-point Steiner solution (1586.5 units).

RandSrch.gif

Of course, many of our human Intelligent Designers answering the Design Challenge got the formal Steiner solution in much less time than 14 hours. Just because a computer is “fast” doesn’t make it “smart.”

Genetic Algorithms don’t find useful and innovative solutions because they are “fast.” They do so because they are using the processes of selection, mutation and reproduction to solve problems, just as happens in Nature. And because the process is essentially unguided, it might not go down the wrong roads taken by human designers who have biases about what the solutions should look like. GA’s actually evolve new information in very reasonable times.

Sure, computers can perform faster than humans at some tasks. But even blinding speed is of little use when searches are random. It is evolution’s combining of random processes like mutation with deterministic processes like selection and reproduction that enable it to be “smarter than you are.”

RESOURCES

Make your own ‘Dummiez’ Book Covers!

Put your own words on Einstein’s Blackboard!

Put your own victims ‘On Notice’ Colbert-Style!

161 Comments

Very nice! Is the Windows version of the program availaible?

I’m wondering, when is a fixed target not a fixed target? I’ve worked on simple GA’s that are used to program FPGAs. The task was go generate a 0V signal on the input of a 1kHz square waveform and a 5V signal on the input of a 10kHz wave. A trivial task for a human to design, except we weren’t using any supporting RC circuitry or clocks, only power to the FPGA being used.

Obviously, the above phenotype was trivially simple enough to just dump into the fitness function. That would appear to be a fixed target then. However, at the same time, the solution was different every time. This isn’t surprising, as the GA effectively treated the FPGA as an analog device, thus producing a large collection of “solutions”.

I think the above is a good example of how even supposedly fixed target GA’s can produce differing results. Also, it’s interesting to note that the solutions our particular GA produced resembled in no way anything that a human would have come up with. It completely ignored all common concepts of circuit design to come up with often bizarre signal pathways, with some sections detacted from the main circuit through the chip entirely and working merely by apparent electromagnetic coupling.

Anyway, enough of my babble! I really enjoyed reading this series of articles!

Andrew

Dave Thomas wrote:

What is it going to be like having to go to Bill Dembksi and admit that you’ve learned the hard way of the true meaning of what Daniel Dennett terms Leslie Orgel’s Second Law: “Evolution is smarter than you are”?

Thomas has proven no such thing, neither Dennett nor Orgel. Computers can compute certain things faster than us, that is why they exist to help us. For Thomas to argue that evolution is smarter than humans because computers can compute faster than humans is a non-sequitur.

Is Sal really this dim, or is he just dishonest? Nowhere did Dave Thomas “argue that evolution is smarter than humans because computers can compute faster than humans” – that’s as transparent a strawman as you can get. Talk about non-sequitur!

Even if Sal put huge delays into the program, and then set to work trying to find the solution and the MacGyvers and managed to find them before the program did, showing that he’s at least as smart as the GA, he would still be sunk because his position is that evolution can’t do this – “evolution is smarter than you are”, while true, is a red herring in regard to ID. Evolution doesn’t have to be smarter than we are, it just has to be smart enough to produce results.

But it really does no good to shoot down some IDer’s argument; they’ll just switch to another one, or simply deny that their argument was shot down. The only people who are swayed by these exercises are those who already know that the ID arguments are bogus. But hey, if it’s fun to write these programs and see how they perform, that’s enough reason to do so, I suppose.

well, there is an instance where a fixed seed is (well, was) actually a good thing. late 70s/early 80s video games. timer chips were cheap (and essential to the early calculators), but true clock chips with memory were epensive back then so they couldn’t rely on that to generate a seed. instead, they experimented, picked the one that seemed the “fairest”, and went with it. home consoles didn’t have memory clocks either (e.g., Atari 2600) so those games also hard-coded their seed.

sometimes, the seed would be re-generated using user reactions (or even their score at various times), so if the user missed shooting something, it would generate different objects to shoot at from that point on (air sea battle). however, if the user did exactly the same thing, then the game would do the same thing in response.

Its the reason you could buy a book on “How to Win at Pac Man”. they analysed the patterns that repeated if the player was consistent with their actions.

some games like card game cartridges also randomized by looking at “how many milliseconds has the machine been turned on” to give more variety. a card game isn’t much fun if it deals the same deck every time. ;-)

I’m wondering, when is a fixed target not a fixed target? I’ve worked on simple GA’s that are used to program FPGAs. The task was go generate a 0V signal on the input of a 1kHz square waveform and a 5V signal on the input of a 10kHz wave. A trivial task for a human to design, except we weren’t using any supporting RC circuitry or clocks, only power to the FPGA being used.

Obviously, the above phenotype was trivially simple enough to just dump into the fitness function. That would appear to be a fixed target then.

The task description puts constraints on candidate solutions. It isn’t information of the candidate solution. Thus, it isn’t a “fixed target” or “distant ideal target”. That your set of constraints doesn’t change (is not time-variant) doesn’t make it a fixed target in the sense being discussed here.

I’m surprised this challenge project caused much of a stir in ID circles. I thought that most ID adherents would accept the idea of microevolution, which is what this sort of optimization problem is similar to. If so, I would expect the discourse to shift from “GAs need a fixed target to work.” towards “GAs only show that function optimization is a kind of microevolution, but can’t demonstrate features of the natural world such as speciation.”

I don’t think you can answer that objection with a discussion of niching in GAs. My understanding of niching is that it is more similar to a mixed strategy within a species in evolutionary terms.

Obviously, ALife environments such as Tierra demonstrate speciation via mutation when parasites appear, but I’m sure most IDers would not think that parasites are an uptick in complexity, and therefore can be ignored. If mutation is the only operator changing the genotype, speciation is going to be very slow, or not show the growth in complexity we see in nature, IMHO.

I don’t know of any EC studies that show speciation (no interbreeding based on phenotype differences). If anyone has a reference, please share it. Algorithms that compute genotype distances and only allow close genotype matches to mate are going to be open to the argument that the algorithm has “baked in” the speciation rather than showing that speciation is an emergent phenomenon of the run.

My intuition is that a good EC speciation demonstration will require a large number of generations (like nature) and/or demes whose connectivity changes over time (like nature) and/or co-evolution (the rest of the population is part of the fitness function, like nature).

BTW, my prediction is that after “GAs can’t evolve species.”, the next issue will be “GAs can’t evolve sex.” All GAs assume sexual reproduction is available as part of the suite of genetic operators - it doesn’t emerge. That’s baking in the answer because “male and female He created them.” If you use God’s tools, of course you’re going to get similar results. But can you make God’s tools?

All GAs assume sexual reproduction is available as part of the suite of genetic operators - it doesn’t emerge.

Actually, many GAs use asexual reproduction. This is not a problem - most of the time, sexual reproduction doesn’t perform massively better. The reason for this is that, whilst sexual reproduction increases variety, it destroys perfection just as quickly.

The main reason we humans have sexual reproduction isn’t because it’s better for evolution - it’s because it makes life harder for parasites, who have trouble specialising enough to attack one generation whilst generalising enough to attack the next. A good book for this stuff is “The Red Queen” by Matt Ridley.

How about this?

Not sure if this counts. Different species arose, but one could argue that the original population did not qualify as a species.

The general strategy of taking up issues in biology that aren’t the focus of evolutionary computation was addressed in my post here a bit earlier this month:

4. Natural selection might be capable of being simulated on computers, and the simulations may demonstrate good capacity for solving some problems in optimization, but the optimization problems are not as complex as those in actual biology.

This objection typically appears once the first three above have been disposed of. Computer simulation, once held to be either a potential indicator of merit or an actual falsifier of natural selection, is then treated as essentially irrelevant to natural selection. It is certainly true that computer simulations are less complex than biological problems, but the claim at issue is not that EC captures all the nuances of biology, but rather that EC gives a demonstration of the adaptive capabilities of natural selection as an algorithm.

All GAs assume sexual reproduction is available as part of the suite of genetic operators - it doesn’t emerge.

Actually, many GAs use asexual reproduction. This is not a problem - most of the time, sexual reproduction doesn’t perform massively better. The reason for this is that, whilst sexual reproduction increases variety, it destroys perfection just as quickly.

Depends on what you mean by “perform”. Sexual operators will cover much more of the overall solution space in a much shorter time, but won’t converge as nicely at the end like asexual hill-climbing. Sexual operators also have somewhat of a defense against the destruction of perfection - junk DNA. And in the real world, of course, convergence is of relatively minor interest anyway. Evolution does not have a goal.

Wesley Wrote:

The general strategy of taking up issues in biology that aren’t the focus of evolutionary computation was addressed in my post here a bit earlier this month:

Thanks for the reminder! I’ve added a link to that splendid tome in the “War of the Weasels” sidebar above.

Marek 14 Wrote:

Very nice! Is the Windows version of the program available?

Pretty soon now. I had to tweak it a bit so the intense Random Searches could be safely interrupted by other Windows processes.

Dave

What was Salvador Cordova using if not A COMPUTER??? His excuse was too pitiful to even be laughable.

Andrew,

I read an article about your FPGA experiment. Interesting stuff. I believe the article said you were using an asynchronous FPGA, and so the design was very sensitive to temperature and power supply voltage. Did you ever get a synchronous version working?

Is Sal really this dim, or is he just dishonest?

Yes.

Dave Thomas — Well done again!

You forgot one of the major criteria, the same algorithm given a different problem will still find a solution.

The example might be clearer if simplify the problem by not using long strings. I started playing with my own model when I say the contest.

Define the environment as an arbitraty rectangle (say 0,0 to 500,500) Selectors are defined a series of points (arbitrary or random) Define a critter as a series points connected by line segments.

Fitness: Subtract the total length of all line segments in the critter. Subtract the distance from the each selector to the nearest point in the critter multiplied by constant (say 100 so distance is more important than length)

Mutation: Addition: select a random point in the critter and add a line segment to a new random point within radius x (say 10) Reduction: select a random point and remove it from the critter. Integrity must be maintained so new line segments are created between attached points. (ie. A-B-C becomes A-C or A-B-C and B-D becomes A-C and A-D and C-D, etc). Alteration: A given point is moved to a new random location within radius x (say 3)

Selection: Keep the best 3rd of all variations

Given enough generations this will approximate a solution.

Alann Wrote:

You forgot one of the major criteria, the same algorithm given a different problem will still find a solution.

Good point! I guess it was so obvious that I neglected to mention that. The first “Target” post, in July, dealt with four and five-point problems, while the August Design Challenge dealt with a six-point problem.

I got the idea for doing the Design Challenge by doing just as Alann suggested, trying out the GA engine on new, unsolved Steiner problems. When the solution for the new six-point problem turned up in the GA, I was so surprised with this rather complex and skewed result that I decided to issue the Design Challenge two days later.

Cheers, Dave

bob Wrote:

Andrew,

I read an article about your FPGA experiment. Interesting stuff. I believe the article said you were using an asynchronous FPGA, and so the design was very sensitive to temperature and power supply voltage. Did you ever get a synchronous version working?

The article you read was most likely by Adrian Thompson, who originally ran the experiment in 1996 I believe. There is an extended abstract here. As a poxy undergraduate at a different university a couple of years after this original study was done, we merely re-ran the experiment as a tuition aid into GA’s and their potential application to novel circuit design.

So, as to the synchronous models, I can’t answer that one as I have long departed the GA and electronics scene and never contributed anything useful to this field when I was studying it as a uni course. Even so, the original asynchronous FPGA example still strikes me as an extremely intruiging piece of research. The problems of robustness and practicality are simply issues with the fact that a large part of the fitness environment was not controlled. Whilst this may restrict the applicability of solutions developed in this manner, it doesn’t stop the results being extremely interesting. The sheer weirdness of the resulting circuits, totally unlike anything that humans design, strikes me as a compelling likeness to the biological features we see evolution producing.

Andrew

Andrew: thanks, I’ve been looking for that for a while. Had found Adrian Thompson’s site, but couldn’t locate that particular demonstration.

But, given a problem with no obvious answer, and one for which a Genetic Algorithm actually out-performed ID theorist Cordova, the fall-back position is “But Computers are FASTER than humans!”

Which would seem to be the point to using them.

But, given a problem with no obvious answer, and one for which a Genetic Algorithm actually out-performed ID theorist Cordova, the fall-back position is “But Computers are FASTER than humans!”

Which would seem to be the point to using them.

Accuracy, precision, consistency, persistence of memory, and automation are obvious other reasons to use computers, just off the top of my head.

As a professional software developer I would just like to say how astounded I am that anyone claiming to know anything about software dvelopment would use a hard coded constant in a call to srand(). This indicates a basic lack of knowledge of both C and RNG’s.

Furthermore is Cordova claiming this program works? It is riddled with significant errors and most certainly will not compile.

As a professional software developer I would just like to say how astounded I am that anyone claiming to know anything about software dvelopment would use a hard coded constant in a call to srand(). This indicates a basic lack of knowledge of both C and RNG’s.

I’ve been writing software for over 40 years, C for about 30, and I have often used a hard coded constant in a call to srand() – when I need reproducibility (you can omit the call to srand() altogether in that case, but I prefer to make it explicit, and I still have habits from before such things were specified in the standard – before there was a standard, in fact).

Of course, it does not follow that Cordova has basic knowledge of C or RNG’s.

Let me suggest than you replace “uncommonly” with “inordinately” so as to create a more fitting acronym.

“Uncommonly Dense” refers to “Uncommon Descent”, Demski’s blog where much of this insanity occurs. “Uncommon Dissent” also works, both in how science looks at ID and how the blog is administrated.

These rules are hardly formal and I don’t think they accomplish their stated goal:

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.

The rules might work for dummies, and they’re good rules of Thumb (I made a funny), but they’re not sufficient to eliminate/identify a fixed target in the fitness function.

1) Check That Random Seed

Has nothing to do with whether the target is fixed or not. It simply makes the algorithm deterministic and hence reproducible. If you do insist on using the time or whatever for the random number seed, you should store the seeds for the sake of reproducibility. It doesn’t apply here, but what if you ran the GA for over a month, published your findings, and some guy comes along who doesn’t believe you? You will not be able to reproduce your experiment exactly, unless you remember what seeds you used. (I could imagine this being particularly painful if the GA invented something really novel and we wanted to see how it got there)

2) Is the Answer Always the Same?

Unless this can be formally proven a priori (as Dave Thomas has, in the case of Cordova’s program), it’s begging the question. It’s a good hint if in 10 runs the answer is always the same, but this is not strictly proof that the search is targeted. Cf. the Halting Problem; maybe something different will happen on the tenth run.

Furthermore, (and this is really problematic for the counterarguments against ID) if the answers are different, it’s insufficient to conclude that the search is not targeted. Once again, we might not have run the program through enough generations. Who knows, maybe after a while all the McGuyver’s converge to one of the optima after 10 years on the PC?

Secondly, how did you tell that a solution was reached? Did you wait a pre-specified number of generations, or did you employ some sort of stasis criteria? Either way, it may simply be that the algorithm fails to find the target that it was searching for. How can you tell, for instance, that the McGuyver’s weren’t “striving” (whatever that means) towards the optima, and simply the mechanism of RM+NS fails to get us there?

3) Is it just that Computers are Faster?

Good idea to include the Tornado in a Junkyard as a baseline, and speaks to Cordova’s innane retreat. But it has nothing to do with whether GAs are targeted or not.

(I hate to play devil’s advocate here. I think this experiment has been wonderful and to me has aptly demonstrated that so called IC systems can evolve. However, I’m really curious about this problem in general.)

To put it more simply, how can one tell that a fitness function f:C->[0-1], where C is the space of all critters, is targeted or encodes the solution? My guess is that in general one cannot, but also that it doesn’t matter.

I’ve been writing software for over 40 years, C for about 30, and I have often used a hard coded constant in a call to srand() — when I need reproducibility (you can omit the call to srand() altogether in that case, but I prefer to make it explicit, and I still have habits from before such things were specified in the standard — before there was a standard, in fact).

Of course, it does not follow that Cordova has basic knowledge of C or RNG’s.

30 years? Since 1976? Since 2 years before K&R was published? So when did you leave Bell?

Yes, there can be reasons to hard code a constant into a call to srand() but none of them apply in this case. For those who say the seeds should be maintained to allow reproducibility that’s fine but it still shouldn’t be hard coded. Saved to a file or printed out is far better than actually putting it in the code.

GuyeFaux Wrote:

To put it more simply, how can one tell that a fitness function f:C->[0-1], where C is the space of all critters, is targeted or encodes the solution? My guess is that in general one cannot, but also that it doesn’t matter.

An excellent question, and one that could be addressed in the Advanced version of Genetic Algorithms for Uncommonly Dense Software Engineers. The present tome was meant as a very general and light intorduction to the field, especially for those who claim ALL GAs require specification of a precise “Target.”

Dave

…claim that ALL GAs require specification of a precise “Target.” [emphasis in original]

Having reflected upon this further, I don’t even know what the claim means. Particularly the claim that the fitness function must specify a “Target”. Does it mean that there is one and only one optimum in the fitness space?

Anyway I am through playing the Designer’s Advocate.

Dave’s point against inference of design loses none of its potency.

The McGuyver results strongly refutes the suggestion of a true target sequence. Getting stuck with these non-optimal variants is very much in line with evolution and natural selection.

As much as ID wants to complain that the problem is unfair, this places the burden on them to explain what a fair problem would be. Too bad they suck at coming up with alternatives.

Alann wrote:

What ID is calling the “target sequence” (and yes I agree this is bad termonology) is the idea that the fitness equation has an optimal solution and in the conceivable lineage there are no necessary steps which are neutral or less fit.

If I understand correctly, this isn’t true. It may happen that all the offspring of a given generation are in fact “less fit” than the parents. One of those less fit offspring must eventually yield a locally “optimal” solution, yielding a lineage that does not have a monotonically increasing fitness. The algorithm and the fitness function don’t care. Now, admittedly, given enough test cases, there will likely be a lot where a “successful” lineage does have monotonically increasing fitness, but it’s not required.

In fact, one could conceive of a fitness space with a “ridge” in it, whereby the lineage *must* contain a necessary step that is less fit than its parents if the line traced through the fitness space is to achieve a more global optimum.

I think you are trying to dismiss my point out unfairly.

I think that’s ad hominem bullpucky. I find your “points” to be complete and utter drivel that display ignorance and severe confusion, and I treated them far more fairly than they deserved.

As much as ID wants to complain that the problem is unfair, this places the burden on them to explain what a fair problem would be. Too bad they suck at coming up with alternatives.

Indeed, but that was established without any of your “help”.

What ID is calling the “target sequence” (and yes I agree this is bad termonology) is the idea that the fitness equation has an optimal solution

Well, of course, in this particular case, there isn’t an optimal solution; there are two optimal solutions.

On top of that, the statement is complete and utter malarkey; that isn’t what the Meyer is calling the “target sequence” – what he means by “target sequence” is Darwin’s Weasel phrase – the predefined goal. And when the problem is changed to something like Steiner networks, the IDiots still mean that, even though it doesn’t apply. So now the “target sequence” refers to the optimal solution (even though, as you point out there isn’t one), even though that wasn’t predefined and does not exist anywhere in the program – or even in the programmer. So then they argue some nonsense about it being “implicit” in the fitness function – which in the Steiner network case is merely a comparison function that prefers the shorter path, which is a characteristic defined by the problem – to find the network with the shortest path. But the solution isn’t implicit in the FF at all; apply a broken GA to that FF, and it will never find the solution. All that was shown here is that there is some GA that, when applied to that FF, will produce (what we think are) the optimal solutions. Meyer’s and Cordova’s claims, and Alann’s claims about their claims (as well as his nonsense about intermediate steps), are complete hogwash.

As a refresher, here is Meyer’s statement:

Nevertheless, as shown elsewhere (Meyer 1998:127-128, 2003:247-248), these [genetic algorithm] programs only succeed by the illicit expedient of providing the computer with a ”target sequence”´ and then treating relatively greater proximity to future function (i.e., the target sequence), not actual present function, as a selection criterion.

He equates “target sequence” to “future function”. This obviously isn’t the fitness function, of which there is no present vs. future version in the program; he’s referring to the actual entity, which is a string of characters in the Weasel case and a specific Steiner network in this case. He says that the computer is provided with this entity, which is true in the Weasel case but not in the Steiner case. And he claims that the fitness function selects for proximity to that entity, which is true in the Weasel case but not for the Steiner case. In the Steiner case, that entity isn’t known, so it isn’t possible to calculate proximity to it. And, as Coin points out, there are two such entities – which are mirror images of each other, so they aren’t close to each other in the search space; proximity to one is not proximity to the other, and if the algorithm worked the way Meyer portrays it, it could never reach either one. What folks like Alann can’t seem to get their heads around is that these mutating entities follow paths through search space, not along the linear sequence of values of the FF, and so “proximity” is a matter of the former, not the latter. You can’t just take an arbitrary Steiner network and mutate it such that it now has a shorter path length; if you could, there would be no need for a GA. That’s why “examples” like 1,2,3,…n or 2,3,5,7,11,… are inappropriate and downright ludicrous.

Popper's ghost Wrote:

You can’t just take an arbitrary Steiner network and mutate it such that it now has a shorter path length

All right now you’re not making any sense. When the model mutates the Stiener path a shorter path must be a possible outcome; otherwise you’ve reached an evolutionary dead-end.

And proximity in search space versus linear sequence? Really I think you are the one who is lost. What is ludicrous about presenting a simplified alternative? An integer domain (search space) is easier to discuss, and there is no reason why you cannot express mutation and selection in those terms.

As for future vs. present function this is a philosophical agrument about non-selectable intermediates. In the lineage A->B->C where the fitness of C is greater than the fitness of A, the issue is what the fitness of B should be. If you believe that B is in reality a detrimental step; however the abstract problem uses a fitness model where B is a positive step, can you not argue that the reason B is overrated is because you have created a model where future function is innately expressed in present function? Although to be accurate this is in the abstraction of the problem, not in the fitness model.

I do not consider this argument ludicrous, but it is far from compelling.

Alann Wrote:

As for future vs. present function this is a philosophical agrument about non-selectable intermediates. In the lineage A->B->C where the fitness of C is greater than the fitness of A, the issue is what the fitness of B should be. If you believe that B is in reality a detrimental step; however the abstract problem uses a fitness model where B is a positive step, can you not argue that the reason B is overrated is because you have created a model where future function is innately expressed in present function? Although to be accurate this is in the abstraction of the problem, not in the fitness model.

I’m not sure where Alann thinks all this is going. And I don’t know why Alann has to make his points by referring to other types of problems, such as sequences of primes.

As regards the topic of this series of posts, Steiner’s problem, remember that mutations are not applied to “networks,” but rather to strings of data that look like “0845617892168435168TFTFTTFFTTFTFTFTF…”

These strings are what are mutated, bred (crossovers), and transcribed. The Fitness is based on the lengths of segments in the “expressed” version of the creatures (phenotypes).

I haven’t put any restrictions on the program to ensure, for example, that “fitness” is a monotonically increasing function of the number of generations.

Because of the stochastic nature of the breeding/selection process, less-fit individuals can still be selected for breeding. Even if two individuals have higher levels of fitness, there’s no guarantee their offspring (crossovers) will have a similar high fitness.

I hope that helps.

Dave

All right now you’re not making any sense. When the model mutates the Stiener path a shorter path must be a possible outcome; otherwise you’ve reached an evolutionary dead-end.

Sigh. Do you know what a local peak is? Do you know anything?

I was attempting to abstract a general issue from the complexity of the problem. I realize this is not working.

My point was that the argument about future fitness vs. present fitness can be taken to refer to the nature of the problem (that the problem lends itself to functional intermediates) and not as a direct argument against the fitness function.

I do not agree with the ID argument on this point, I am only trying to see their point of view. I apologize for letting this take the conversation so far off topic.

Oh and for the record (since someone seems to think I am and idiot) my background is mathematics, logic, and computer science. I do not consider myself in any way an expert on biology.

Odd then that you show no understanding of mathematics, logic, computer science, or biology.

Comments are now Closed.

It’s been fun. Let’s do it again some day, shall we?

Thanks & regards, Dave

About this Entry

This page contains a single entry by Dave Thomas published on September 1, 2006 12:49 AM.

The Politically Incorrect Guide to Darwinism and Intelligent Design Review: PIG Ignorant About Ohio was the previous entry in this blog.

Balloons, Stents, and Arteries: A Review of the Logic Behind Modern Cardiology is the next entry in this blog.

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

Categories

Archives

Author Archives

Powered by Movable Type 4.381

Site Meter