机器学习

Genetic programming (GP) is a form of evolutionary computation in which the individuals in the
evolving population are computer programs rather than bit strings. The basic genetic programming
approach and presents a broad range of simple programs that can be successfully learned by GP.
Representing Programs
Programs manipulated by a GP are typically represented by trees corresponding to the parse tree of the
program. Each function call is represented by a node in the tree, and the arguments to the function are
given by its descendant nodes. For example, below Figure illustrates this tree representation for the
function sin(x) +
 x2
  y  . To apply genetic programming to a particular domain, the user must define
the primitive functions to be considered (e.g., sin, cos,
 , +, -, exponential~), as well as the terminals
(e.g., x, y, constants such as 2). The genetic programming algorithm then uses an evolutionary search to
explore the vast space of programs that can be described using these primitives. As in a genetic
algorithm, the prototypical genetic programming algorithm maintains a population of individuals (in this
case, program trees). On each iteration, it produces a new generation of individuals using selection,
crossover, and mutation. The fitness of a given individual program in the population is typically
determined by executing the program on a set of training data. Crossover operations are performed by
replacing a randomly chosen subtree of one parent program by a subtree from the other parent
program.
Above Figure illustrates a typical crossover operation. It describes a set of experiments applying
a GP to a number of applications. In his experiments, 10% of the current population, selected
probabilistically according to fitness, is retained unchanged in the next generation. The remainder of
the new generation is created by applying crossover to pairs of programs from the current generation,
again selected probabilistically according to their fitness. The mutation operator was not used in this
particular set of experiments.
Illustrative Example
One illustrative example presented by Koza (1992) involves learning an algorithm for stacking the blocks
shown in below Figure The task is to develop a general algorithm for stacking the blocks into a single
stack that spells the word "universal," independent of the initial configuration of blocks in the world.
The actions available for manipulating blocks allow moving only a single block at a time. In particular,
the top block on the stack can be moved to the table surface, or a block on the table surface can be
moved to the top of the stack.
111
As in most GP applications, the choice of problem representation has a significant impact on the
ease of solving the problem. In Koza's formulation, the primitive functions used to compose programs
for this task include the following three terminal arguments:
 CS (current stack), which refers to the name of the top block on the stack, or F if there is no
current stack.
 TB (top correct block), which refers to the name of the topmost block on the stack, such that it
and those blocks beneath it are in the correct order.
 NN (next necessary), which refers to the name of the next block needed above TB in the stack,
in order to spell the word "universal," or F if no more blocks are needed.
As can be seen, this particular choice of terminal arguments provides a natural representation for
describing programs for manipulating blocks for this task. Imagine, in contrast, the relative difficulty of
the task if we were to instead define the terminal arguments to be the x and y coordinates of each
block.
In addition to these terminal arguments, the program language in this application included the
following primitive functions:
 (MS x) (move to stack), if block x is on the table, this operator moves x to the top of the stack
and returns the value T. Otherwise, it does nothing and returns the value F.
 (MT x) (move to table), if block x is somewhere in the stack, this moves the block at the top of
the stack to the table and returns the value T. Otherwise, it returns the value F.
 (EQ x y) (equal), which returns T if x equals y, and returns F otherwise.
 (NOT x), which returns T if x = F, and returns F if x = T.
 (DU x y) (do until), which executes the expression x repeatedly until expressiony returns the
value T.
To allow the system to evaluate the fitness of any given program, Koza provided a set of 166 training
example problems representing a broad variety of initial block configurations, including problems of
differing degrees of difficulty. The fitness of any given program was taken to be the number of these
examples solved by the algorithm. The population was initialized to a set of 300 random programs.
After 10 generations, the system discovered the following program, which solves all 166 problems.
(EQ (DU (MT CS)(NOT CS)) (DU (MS NN)(NOT NN)) )
Notice this program contains a sequence of two DU, or "Do Until" statements. The first repeatedly
112
moves the current top of the stack onto the table, until the stack becomes empty. The second "Do
Until" statement then repeatedly moves the next necessary block from the table onto the stack. The
role played by the top level EQ expression here is to provide a syntactically legal way to sequence these
two "Do Until" loops.
Somewhat surprisingly, after only a few generations, this GP was able to discover a program that solves
all 166 training problems. Of course the ability of the system to accomplish this depends strongly on the
primitive arguments and functions provided, and on the set of training example cases used to evaluate
fitness.
Remarks on Genetic Programming
As illustrated in the above example, genetic programming extends genetic algorithms to the
evolution of complete computer programs. Despite the huge size of the hypothesis space it must
search, genetic programming has been demonstrated to produce intriguing results in a number of
applications. A comparison of GP to other methods for searching through the space of computer
programs, such as hillclimbing and simulated annealing, is given by O'Reilly and Oppacher (1994).
While the above example of GP search is fairly simple, Koza et al. (1996) summarize the use of a GP in
several more complex tasks such as designing electronic filter circuits and classifying segments of
protein molecules. The filter circuit design problem provides an example of a considerably more
complex problem. Here, programs are evolved that transform a simple fixed seed circuit into a final
circuit design. The primitive functions used by the GP to construct its programs are functions that edit
the seed circuit by inserting or deleting circuit components and wiring connections. The fitness of each
program is calculated by simulating the circuit it outputs (using the SPICE circuit simulator) to determine
how closely this circuit meets the design specifications for the desired filter. More precisely, the fitness
score is the sum of the magnitudes of errors between the desired and actual circuit output at 101
different input frequencies. In this case, a population of size 640,000 was maintained, with selection
producing 10% of the successor population, crossover producing 89%, and mutation producing 1%. The
system was executed on a 64-node parallel processor. Within the first randomly generated population,
the circuits produced were so unreasonable that the SPICE simulator could not even simulate the
behavior of 98% of the circuits. The percentage of unsimulatable circuits dropped to 84.9% following
the first generation, to 75.0% following the second generation, and to an average of 9.6% over
succeeding generations. The fitness score of the best circuit in the initial population was 159, compared
to a score of 39 after 20 generations and a score of 0.8 after 137 generations. The best circuit, produced
after 137 generations, exhibited performance very similar to the desired behavior.
In most cases, the performance of genetic programming depends crucially on the choice of
representation and on the choice of fitness function. For this reason, an active area of current research
is aimed at the automatic discovery and incorporation of subroutines that improve on the original set of
primitive functions, thereby allowing the system to dynamically alter the primitives from which it
constructs individuals. See, for example, Koza (1994).