19990913; modified 20001003
"Evolutionary computation" as I will use it here is an inclusive term to cover a variety of techniques of simulating evolving populations on computers. These techniques include "genetic algorithms" (GAs), "artificial life" (AL), and "genetic programming" (GP). All evolutionary computation is premised upon a "genetic" representation of either a candidate solution for an optimization problem (as in GAs) or an instantiation of a program to be "run" on a virtual or real machine (AL and GP).
Evolutionary computation (EC) is derived from biological principles, specifically those of the theory of natural selection. Much of the terminology used in EC is lifted, more or less accurately, from biological sources. There is much discussion of the relative advantage of "crossover" as opposed to "mutation", for example, which shows at once the reliance upon biological jargon and the sloppiness found in its new application.
As with any relatively new field of endeavor, one finds that there are both those who hype the technology, and those who are skeptical of it. Evolutionary computation comes under fire from three separate groups, whose motivations in skepticism are widely disparate. Many biologists working in genetics have come to scorn EC examples as overhyped, underpowered, and not truly representative of evolutionary processes. Some computer scientists have complained about both explicit and implicit claims concerning the utility of EC in the field of optimization. And, finally, the group whose objections most generally concern readers of RNCSE, various "scientific creationists" and "intelligent design" proponents object to EC because it is seen as substantiating the claims that biology has made concerning the power of natural selection.
I will here entertain the creationist objections first.
Natural selection turned out to be perfectly adequate as a source of basic rules for simulation. The field of evolutionary computation dates back to the late 1950's or early 1960's. Even when Marcel-Paul Schutzenberger assured the attendees of the mid-1960's Wistar conference on mathematical challenges to the Neo-Darwinian synthesis that all efforts to model natural selection on computers just "jam" the machines, another attendee spoke out saying that he had successfully run such simulations, and was, in fact, impressed with how quickly they worked.
Certain early attempts at EC did fail, but in the particular case cited above, the person was attempting a variant of genetic programming, which is still a very difficult field. Since then, successful simulations have been accomplished in GAs, AL, and even genetic programming. It is doubtful that the late objector would be willing to go so far as to say that natural selection is supported because simulation is successful.
This one is commonly encountered in online discussions as a variant of the popular "natural selection is just the same thing as blind chance". We can show that various problems solved by GAs are solved much more efficiently than by random search. (Please see commentary on the "no free lunch theorem" below.)
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.
If we take a limited form of evolutionary computation for simplicity's sake and analyze it, I think that we will come out ahead. Genetic algorithms, as presented by John Holland in 1975, work on a population of fixed-length bit strings. The bit-string representation is generic. The operations which the genetic algorithm performs involves the manipulation of these bit strings, with feedback from an evaluation function.
What are the manipulations on the bit-strings? The GA can copy bit-strings with mutation (change in state of a bit), crossover (production of a new bit-string using parts of two existing bit strings in the population), and a variety of other "genetic" operators. The GA selects bit-strings for reproduction based upon results returned from an evaluation function which is applied against each bit string in the population.
The purpose of the evaluation function is to provide a metric by which the bit-strings can be ranked. The critical point to be grasped is that neither the operations of the GA nor those of the evaluation function need information about the pattern of the end solution. The GA's operations are completely generic; there are a variety of GA shell tools available for use, including plug-ins for MS Excel spreadsheets. Since the same GA tool may be used for job-shop scheduling in one instance, and oilfield pipeline layout in another, the objection that the intelligence of the GA programmer informed the specific designs that result from its application quite soon appear ludicrous. That a programmer might code a generic GA shell and also happen to somehow infuse it with just the right information to optimize PCB drilling movements might be possible, but to insist that the same programmer managed to infuse specific domain knowledge for each and every application to which his tool is put stretches credulity.
Now, let's eliminate the evaluation function as a source of domain-specific information. Obviously the evaluation function does give information to the GA, but that information does not give a direction for adaptive change for each bit-string evaluated, but rather just how well each bit-string performed when evaluated. The result passed back to the GA does not give the GA insights like "Toggle bit 9 and swap 20-23 with 49-52". It merely passes back a scalar number, which when compared to other scalar numbers, forms a ranking of the bit strings. The evaluation function can require very little in the way of domain-specific knowledge. For the PCB drilling application mentioned above, the evaluation function can very simply be instantiated as "return closed path length of the route represented by the input bit-string", which says nothing at all about what the path looks like, and works for any set of hole coordinates. Because the evaluation function can be generic over cases, again we have the argument that domain-specific information is unavailable here on the same grounds as for the GA operations. While we might be able to conceive of an evaluation function that somehow encapsulated information about a particular solution, for problems like the PCB routing one mentioned it is highly unreasonable to credit that information about all possible PCB route configurations has somehow been instilled into the code.
What's left? Merely the information content of the initial bit strings in the GA population. Since this is often, if not always, done by filling the bit-strings based upon random numbers, any non-trivial bit representation is highly unlikely to correspond to a final solution state.
The information or designs said to be produced by GA are the contents of the bit-strings at the end of the GA run. It can be confirmed that the end bit-string content differs from the initial bit-string content. It can be demonstrated that the evaluation of the initial bit-string indicates poorer function than the final bit-string. The question which those who object to evolutionary computation via the assertion that intelligence has somehow been infused into the result must answer is that if intelligence intervenes to shape or produce the final bit-string, *how* does it accomplish that, and *where* did the domain-specific knowledge come from? I've already sealed off infusion via the GA, the evaluation function, and the initial bit-strings for "how". The "where" question poses an extremely serious difficulty for proponents of this assertion, since if the information needed to solve all the problems which a GA can solve is present on every machine which a GA can be run upon, the information capacity of each machine is demonstrably smaller than the information content of all those possible solutions. It is problematic where the information is stored, and even if that information were capable of being stored somehow, the problem of *why* computer designers and programmers, who would be shown by this to be very nearly omniscient, would chose to put all that information into their systems when the vast majority of it is very likely never to be used.
I'll note that it is entirely possible to point to or construct evolutionary computation examples whose evaluation functions incorporate a known final solution state. I only know of such simulations done for pedagogy. Dawkins' "weasel" program from "The Blind Watchmaker" is a fine example of this. However, the mere existence of that simulation is not sufficient to show that all evolutionary computation does so.
I think that instead of either being difficult or impossible, the correct classification is that it would be time-consuming to generate such an application. I'll lay out the approach I would take if I had the time and inclination to do such. First, I would not use fixed-length bit strings, so the underlying computational approach would not quite match the definition of a GA, although most of the same code would likely be useful. Second, the initialization of the evaluation function would involve scanning a large source of text in the language of choice, building a symbol sequence frequency table. (A possible or likely objection here is that this gives information about the language to be generated. However, this procedure gives far less information than is provided to developing humans, who in the absence of examples of language use do not generate grammatically correct sentences, either.) Third, the evaluation function would return a probability value for a bit-string based on the likelihood that the bit-string could be drawn from the distribution represented by the symbol sequence frequency table, with extra points for the final symbol being a period, and the initial symbol being a capital letter. The GA would finish when a bit-string achieved a threshold evaluation value. The likely results will be the production of nonsensical, but often grammatically correct or near-correct sentences. I say this on the basis of experience in coding 'travesty' generators and information entropy analysis applications. The use of evolutionary computation in this regard would be no huge stretch.
In the case of natural selection operating or the case of a GA being run, there has to be some initial state. We aren't concerned with *how* that initial state came to be; our analysis concerns what happens when natural selection operates, or the GA operates. Let's look at another simulation, one in which the rise and fall of barometric pressure is simulated according to provided atmospheric conditions. In this unexceptionable case of a simulation of barometric pressure, we don't claim that there is an internal contradiction because the simulation does not include the creation of an atmosphere from a vacuum.
Possible Computer Science objections:
Those computer scientists who raise objections to evolutionary computation appear to do so as a response to the EC technology pushers, who arguably or even obviously do engage in hyperbolic claims. The counter-claims are often no less hyperbolic, though. Somewhere in between the two camps lies reality, in my view.
EC need not be a panacea for it to be very interesting indeed. EC has been applied to a sufficiently diverse range of real-world problems that it can hardly be said to be worthless. It obviously cannot be applied to all problems with efficiency equal or better than all other fielded techniques. All that NFL establishes is that for all algorithms, there is no algorithm that performs better than blind search when applied to all cost functions of a problem.
In looking at the NFL paper and some other commentary, it seems evident that what the authors have established is that a priori evaluations of suitability of an optimization technique to a task is not secure. We do not know ahead of time and with certainty that Procedure X, which performs well on Problem Y, will also perform well on apparently-similar Problem Z. Finding efficient, or better, optimization techniques for a particular task will always involve applying knowledge concerning the task to matching technique and problem.
NFL establishes that in the absence of prior knowledge of the evaluation function for a problem and when all possible evaluation functions for a problem are considered, no technique will perform better over the complete set of evaluation functions than any other technique. Thus, in the absence of knowledge, blind or random search is exactly as efficient as any other optimization technique.
Let's take it as a given that everything that Wolpert and MacReady say about NFL is true. What does that leave us? First, no technique for optimization is going to be a panacea. That includes not just evolutionary computation techniques, but all techniques, whether known or still to be developed. Second, nobody utilizes optimization techniques in the manner in which their efficiency is shown to be equivalent to blind search.
True, but trivial. If EC can be applied in many cases successfully where no domain-specific technique has yet been developed, it will be useful if only as a default initial optimization strategy. NFL says that in the absence of knowledge, one could use any technique with equal likelihood of obtaining a result in an efficient manner. Thus, by NFL, my suggestion of use of EC as a default initial strategy in preference to blind search is not rational. But by induction, we know that many real-world problems that are not efficiently handled by blind search have been solved satisfactorily by EC approaches.
I'm sure that I can come up with others with some more thought and reflection. These objections seem to arise in response to hype from technology boosters, as I've seen similar objections for traditional top-down AI, artificial neural networks, and fuzzy logic.
Possible Biology objections:
Biologists typically have an innate dislike of intrusions into their turf of mathematicians and computer scientists. In many cases, this dislike has been justifiable and justified, but sometimes it may just be due to force of habit.
While true in some senses, the model that GAs present is actually fairly close to a version of the population genetics familiar to generations of biology students. There have been various EC studies that attempt to incorporate a more complex and biologically plausible genetic structure.
I have elsewhere laid out the formal statements of natural selection and GAs, pointing out the correspondences.
Natural selection is sometimes stated in the form of three premises and a conclusion:
Now, for correspondences to evolutionary computation:
I'd appreciate further counter-EC assertions that you might be aware of.
1. Murray Eden in P.S. Moorhead and M.M. Kaplan, eds., Mathematical Challenges to the Neo-Darwinian interpretation of Evolution, Wistar Institute Press, Philadephia, 1967, p.17.
2. Marcel-Paul Schutzenberger in P.S. Moorhead and M.M. Kaplan, eds., Mathematical Challenges to the Neo-Darwinian interpretation of Evolution, Wistar Institute Press, Philadephia, 1967, pp.74-75.
Wolpert and Macready. [TBD]
Page maintainer: Wesley R. Elsberry