BIOLOGICAL INSPIRATION FOR COMPUTING 269
appropriately under certain circumstances. Thus, in the limit of increasing complexity, testing an evolu-
tionary solution may resemble the Turing test. (In the Turing test, an outside observer is asked to
distinguish between a human being’s answers to a set of questions and a computer’s answers. The
computer is said to have passed the Turing test if the outside observer is unable to distinguish between
the two.)
8.3.1.4 Solution Representation,
In biological organisms, the genetic code of DNA is subject to changes (e.g., mutation), and the
impact of these changes becomes manifest as the new mutated code is involved in the reproductive
process. That is, the particular DNA sequence of an organism can be said to be biology’s representation
of a “solution” to the problem of adapting the organism to a particular set of evolutionary selective
pressures.
From the standpoint of someone solving a problem with techniques from evolutionary computa-
tion, the question arises as to the analogue of DNA. More formally, how is a solution to a computational
problem to be represented?
In general, the solution to a computational problem is an algorithm. However, an algorithm can be
represented in many different ways. Just as data can be represented as lists of numbers or in graphical
form, computer programs (which embed algorithms) can be represented as “source code” that is read-
able by human beings or as “object code”—the raw ones and zeros of binary computation.
If candidate solutions are to be computer programs, one might imagine that their machine language
representation is an obvious possible representation. However, changing a machine language program
one bit at a time, at random, is highly likely to prevent the (modified) program from running at all
(because previously valid op-codes will be turned into invalid ones), and a nonrunning program is
useless. The same comments apply to the source code of a program. By randomly changing characters
in the source code file, the most likely result is a program that will not compile and therefore cannot be
evaluated in any meaningful way. Thus, attempting to evolve a binary program or the source code of a
program would likely result in an extraordinarily slow rate of evolution.
A more robust way to conduct this process is to impose the constraint that the program must be
executable. Thus, one might insist that the source code of a program be syntactically correct but not place
any limits whatsoever on its semantics (on what it does). For example, statements in a program can be
represented as combinations of functions with various numbers of arguments, and the only require-
ment for syntactic correctness is that a function have the right number of arguments.^64 Changes to the
program can be effected by changing the functions and the specific arguments to the functions. The
result, by definition, is a program that is still syntactically correct, still runs, but does not necessarily do
what is desirable. A typical initial program is then created by randomly generating a parse tree. A
population of such parse trees is then subject to crossovers that exchange different parts of the various
parse trees, or mutations that replace one argument or function with a new argument or function.
8.3.1.5 Selection of Primitives,
Closely related to the issue of representations is the question of the appropriate semantic primitives
(i.e., the smallest meaningful unit that can be changed). For example, in the representation of programs
as parse trees, the relevant primitives are functions with arguments, and the efficacy of a genetic
algorithm is strongly dependent on the particular set of functions that the evolutionary process can
manipulate.
(^64) This approach is based on parse trees, a way of representing statements in computer programs. See J.R. Koza, Genetic
Programming: On the Programming of Computers by the Means of Natural Selection, MIT Press, Cambridge, MA, 1992.