Abstract
This thesis investigates the evolution and use of
abstract data types within Genetic Programming (GP). In
genetic programming the principles of natural evolution
(fitness based selection and recombination) acts on
program code to automatically generate computer
programs. The research in this thesis is motivated by
the observation from software engineering that data
abstraction (eg via abstract data types) is essential
in programs created by human programmers. We
investigate whether abstract data types can be
similarly beneficial to the automatic production of
programs using GP.
GP can automatically ``evolve'' programs which solve
non-trivial problems but few experiments have been
reported where the evolved programs explicitly
manipulate memory and yet memory is an essential
component of most computer programs. So far work on
evolving programs that explicitly use memory has
principally used either problem specific memory models
or a simple indexed memory model consisting of a single
global shared array. Whilst the latter is potentially
sufficient to allow any computation to evolve, it is
unstructured and allows complex interaction between
parts of programs which weaken their modularity. In
software engineering this is addressed by controlled
use of memory using scoping rules and abstract data
types, such as stacks, queues and files. This thesis
makes five main contributions: (1) Proving that
abstract data types (stacks, queues and lists) can be
evolved using genetic programming. (2) Demonstrating GP
can evolve general programs which recognise a Dyck
context free language, evaluate Reverse Polish
expressions and GP with an appropriate memory structure
can solve the nested brackets problem which had
previously been solved using a hybrid GP. (3) In these
three cases (Dyck, expression evaluation and nested
brackets) an appropriate data structure is proved to be
beneficial compared to indexed memory. (4)
Investigations of real world electrical network
maintenance scheduling problems demonstrate that
Genetic Algorithms can find low cost viable solutions
to such problems. (5) A taxonomy of GP is presented,
including a critical review of experiments with
evolving memory. These contributions support our thesis
that data abstraction can be beneficial to automatic
program generation via artificial evolution.
Users
Please
log in to take part in the discussion (add own reviews or comments).