Wesley R. Elsberry posted Entry 2525 on August 18, 2006 01:37 PM.
Trackback URL: http://www.pandasthumb.org/cgi-bin/mt/mt-tb.fcgi/2520
Back in 1999, I started a draft of an article about objections to evolutionary computation. It looks like now would be a good time to remind people that these arguments against evolutionary computation have long been addressed.
1. Natural selection is an inadequate theory of adaptation because it does not provide the basic rules for successful computer simulation.
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.
2. Natural selection is disproved because attempted computer simulation has always failed.
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 Marcel-Paul Schutzenberger, the originator of this criticism, would have been willing to go so far as to say that natural selection is supported because simulation is successful.
3. Simulation of natural selection on computers will be found to be no different than random search in efficiency.
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. [Note that humans deploying evolutionary computation are not doing so to explore all cost functions of a problem; most applications have a specific cost function of interest.]
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.
5. Natural selection simulated on computer produces solutions which are informed by the intelligence that went into the operating system, system software, and evolutionary computation software.
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. Any example without a “distant ideal target” demonstrates that GA operation is not dependent on having such a property.
6. The generation of a natural language sentence via means of evolutionary computation is either difficult or impossible.
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.
7. There is an internal contradiction between natural selection and a genetic algorithm, whereby the first step in a GA is to “create” a population of candidate solutions, but no such step exists in natural selection.
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.
Commenters are responsible for the content of comments. The opinions expressed in articles, linked materials, and comments are not necessarily those of PandasThumb.org. See our full disclaimer.