Data Structures and Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.4504

  author =       "W. B. Langdon",
  title =        "Data Structures and Genetic Programming",
  school =       "University College, London",
  year =         "1996",
  month =        "27 " # sep,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  URL =          "",
  URL =          "",
  size =         "350 pages",
  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.",

Genetic Programming entries for William B Langdon