- author = "Jonathan Page",
- title = "Sub-Symbolic Representation and Search Operators for Genetic Programming",
- school = "School of Computer Science, The University of Birmingham",
- year = "1999",
- address = "B29 15TT, UK",
- month = dec,
- email = "jpage@praxis-cs.co.uk, jonny99@btinternet.com",
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/page/thesis.ps.gz",
- size = "226 pages",
-
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.",
