Evolving Data Structures Using Genetic Programming
Genetic Algorithms: Proceedings of the Sixth
International Conference (ICGA95), page 295--302. Pittsburgh, PA, USA, Morgan Kaufmann, (15-19 July 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.