Sub-Symbolic Representation and Search Operators for
Genetic Programming
School of Computer Science, The University of
Birmingham, B29 15TT, UK, (December 1999)Abstract
Genetic Programming (GP) is one of the more recent
additions to a diverse body of biologically-inspired
search techniques known as evolutionary algorithms
(EAs). GP differs from most other EAs in that candidate
solutions are executable programs of arbitrary size
which are evaluated according to how well they perform
on a specified task. Whilst GP has been successfully
applied to a number of problem domains, there remain
many tasks on which performance is notably poor.
This thesis argues that poor performance is, in many
cases, due to the nature of the search that GP's
operators perform. GP's primary operator, crossover,
has been shown to perform a predominantly local search
of the program space, and this can make global optima
difficult to locate if the fitness landscape is
characterised by long stretches of very weak or neutral
fitness gradients.
Recently, a GP search operator that performs global
search has been proposed. This operator is known as GP
uniform crossover, and in this thesis we test it
extensively on a number of benchmark problems. We also
propose a novel sub-symbolic representation for
function which can be used in conjunction with GP
uniform crossover, and which accords GP the additional
ability to perform a very local, directed search of the
program space.
The experiments reported in this thesis raise a number
of issues that are discussed in detail. The
sub-symbolic representation, as used here, constrains
the size of the function set and in many cases this is
significantly larger than those used in most GP
implementations. Despite of this, we report enhanced
performance on a number of problems and this leads us
to question the received wisdom which states that the
recommends a minimalist approach to function set
design. The use of different operators and
representations transforms the search space and
highlights a number of properties of GP program spaces
that have so far been overlooked. We discuss these and,
in the light of our findings, reevaluate some of the
hypotheses that have been put forward concerning the
program spaces of some well-known functions. The search
operators used here also constrain the complexity of
the programs that may be evolved. We examine the
advantages of this, particularly with respect to
controlling program size and resultant run-time, and
the disadvantages.
The issues arising from these studies are diverse and
many have received little attention in the literature.
We believe that the findings reported here pose
numerous questions, and we suggest several directions
for future research.