Architecture-Altering Operations in Genetic Programming

[John Koza]

Technical report available on new architecture-altering operations for
evolving the architecture of a multi-part program in genetic programming.

Title: Architecture-Altering Operations for Evolving the Architecture of a
Multi- Part Program in Genetic Programming.

John R. Koza
Computer Science Department
Stanford University

October 21, 1994 P Report No. STAN-CS-TR-94-1528

ABSTRACT

Previous work described a way to evolutionarily select the architecture of
a multi-part computer program from among preexisting alternatives in the
population while concurrently solving a problem during a run of genetic
programming.  This report describes six new architecture- altering
operations that provide a way to evolve the architecture of a multi-part
program in the sense of actually changing the architecture of programs
dynamically during the run.

The new architecture-altering operations are motivated by the naturally
occurring operation of gene duplication as described in Susumu Ohno's
provocative 1970 book Evolution by Means of Gene Duplication as well as the
naturally occurring operation of gene deletion.

The six new architecture-altering operations are branch duplication,
argument duplication, branch creation, argument creation, branch deletion
and argument deletion.

A connection is made between genetic programming and other techniques of
automated problem solving by interpreting the architecture-altering
operations as providing an automated way to specialize and generalize
programs.

The report demonstrates that a hierarchical architecture can be evolved to
solve an illustrative symbolic regression problem using the
architecture-altering operations.

Future work will study the amount of additional computational effort
required to employ the architecture- altering operations.

INTRODUCTION (SECTION 1 OF TECH REPORT)

In nature, crossover ordinarily recombines a part of the chromosome of one
parent with a corresponding (homologous) part of the second parent's
chromosome.  However, in certain very rare and unpredictable instances,
this recombination does not occur in the usual way.  A gene duplication is
an illegitimate recombination event that results in the duplication of a
lengthy subsequence of a chromosome.  Susumu Ohno's seminal 1970 book
Evolution by Gene Duplication proposed the provocative thesis that the
creation of new proteins (and hence new structures and behaviors in living
things) begins with a gene duplication and that gene duplication is "the
major force of evolution."

This report describes six new architecture-altering genetic operations for
genetic programming that are suggested by the mechanism of gene duplication
(and the complementary mechanism of gene deletion) in chromosome strings.
This report proposes that these new operations be added to the toolkit of
genetic programming when the user desires to evolve the architecture of a
multi-part program containing automatically defined functions (ADFs) during
the run of genetic programming.

The six new architecture-altering operations can be viewed from five
perspectives.

First, the new architecture-altering operations provide a new way to solve
the problem of determining the architecture of the overall program in the
context of genetic programming with automatically defined functions.

Second, the new architecture-altering operations provide an automatic
implementation of the ability to specialize and generalize in the context
of automated problem-solving.

Third, the new architecture-altering operations automatically and
dynamically change the representation of the problem while simultaneously
and automatically solving the problem.

Fourth, the new architecture-altering operations automatically and
dynamically decompose problems into subproblems and then automatically
solve the overall problem by assembling the solutions of the subproblems
into a solution of the overall problem.

Fifth, the new architecture-altering operations automatically and
dynamically discover useful subspaces (usually of lower dimensionality than
that of the overall problem) and then automatically assemble a solution of
the overall problem from solutions applicable to the individual subspaces.

Section 2 of this report describes the naturally occurring processes of
gene duplication and gene deletion.  Section 3 describes analogs of gene
duplication and gene deletion that have appeared in previous work with
character strings in the field of genetic algorithms and other evolutionary
algorithms.  Section 4.1 provides basic background information on genetic
programming and automatically defined functions.  Section 4.2 lists the
steps for executing genetic programming.  Section 4.3 describes the five
existing methods for determining the architecture of multi- part programs
in the context of genetic programming with automatically defined functions.
Section 4.4 describes different methods of creating the initial random
population when these new operations are being used.  Section 4.5 describes
structure-preserving crossover with point typing in an architecturally
diverse population.  Section 5 describes the six new architecture-altering
operations.  Section 6 illustrates the architecture-altering operations
using a gedanken experiment involving the problem of rotating the tires on
an automobile.  Section 7 contains some examples of actual runs of genetic
programming with the new architecture-altering operations.  Section 8 is
the conclusion and section 9 outlines future work.


METHODS OF OBTAINING REPORT:

You can get this 60-page technical report by anonymous 
FTP or you can order a hard copy directly from Stanford 
for $l0.  

HARD COPY ORDERS:
$l0 should be sent to:

Publications Office
Computer Science Department
Margaret Jacks Hall
Stanford University
Stanford, CA 94305-2140 USA

FTP INSTRUCTIONS:

FTP to elib.stanford.edu.  The files containing the report 
are in the /pub/reports/cs/tr/94/1528 directory.  

Detailed FTP instructions:  

ftp elib.stanford.edu
user anonymous  
cd /pub/reports/cs/tr/94/1528

Then, get all the files from that directory.  Type the 
following three commands.

prompt

binary

mget * 

This will transfer all of the files to your machine.