There are a variety of claims concerning natural selection
and computers. I'll list a few here:
1. Natural selection is an inadequate theory of adaptation
because it does not provide the basic rules for successful
computer simulation.
2. Natural selection is disproved because attempted computer
simulation has always failed.
3. Simulation of natural selection on computers will be
found to be no different than random search in efficiency.
4. Natural selection might be capable of being simulated
on computers, and the simulations may demonstrate good
capacity for solving problems in optimization, but the
optimization problems are not as complex as those in
actual biology.
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.
The state of things today is that assertions 1, 2, and 3 are
simply and plainly false. I'll pass over the essential
goalpost-moving tactic that runs through the sequence of
invocation of these objections. Assertion 4 is true but of
not much value. Assertion 5 is one that I believe to be false
fairly obviously, but a number of bright people disagree, so
I'll state it as being an arguable point and start the
argument rolling.
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 assertion 5 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 asserion 5,
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.
It has been posed as an open problem that the generation of a
natural language sentence via means of evolutionary
computation is either difficult or impossible. I think that
instead of either, 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. 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, and 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.
Wesley