Evolving Data Structures Using Genetic Programming
Research Note, RN/95/1. UCL, Gower Street, London, WC1E 6BT, UK, (January 1995)Abstract
Genetic programming (GP) is a subclass of genetic
algorithms (GAs), in which evolving programs are
directly represented in the chromosome as trees.
Recently it has been shown that programs which
explicitly use directly addressable memory can be
generated using GP.
It is established good software engineering practice to
ensure that programs use memory via abstract data
structures such as stacks, queues and lists. These
provide an interface between the program and memory,
freeing the program of memory management details which
are left to the data structures to implement. The main
result presented herein is that GP can automatically
generate stacks and queues.
Typically abstract data structures support multiple
operations, such as put and get. We show that GP can
simultaneously evolve all the operations of a data
structure by implementing each such operation with its
own independent program tree. That is, the chromosome
consists of a fixed number of independent program
trees. Moreover, crossover only mixes genetic material
of program trees that implement the same operation.
Program trees interact with each other only via shared
memory and shared ``Automatically Defined Functions''
(ADFs).
ADFs, ``pass by reference'' when calling them, Pareto
selection, ``good software engineering practice'' and
partitioning the genetic population into ``demes''
where also investigated whilst evolving the queue in
order to improve the GP solutions.