Evolving Data Structures Using Genetic Programming   [DS] [GP]

by

Langdon, W., B.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95) (Conference proceedings), 1995, p. 295-302
Keywords:Genetic Programming, Genetic Algorithms, Automatic Programming, Machine Learning, Artificial Evolution, Data Structures, Object Oriented Programming, Push down Stack, First-in first-out (FIFO) Queue, Automatically Defined Functions (ADF), Pareto fitness, Demes
Abstract:
Genetic programming (GP) [GP] is a subclass of genetic algorithms (GAs), [GA] [GAG] 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 [SE] practice to ensure that programs use memory via abstract data structures [DS] 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 [DS] implement. The main result presented herein is that GP can automatically generate stacks and queues. Typically abstract data structures support multiple operations, [DS] 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. [PT] Moreover, crossover only mixes genetic material of program trees [PT] that implement the same operation. Program trees [PT] interact with each other only via shared memory and shared ``Automatically Defined Functions'' (ADFs). [ADF] ADFs, ``pass by reference'' when calling them, Pareto selection, [PS] ``good software engineering [SE] practice'' and partitioning the genetic population into ``demes'' where also investigated whilst evolving the queue in order to improve the GP solutions.
Notes:
Discussed on GP mailing list 6--13 Jan 95, subj: GPdata. Mainly as Langdon:1995:GPdataRN but with more details on pareto selection
URL(s):Postscript
(G)zipped postscript

Review item:

Mark as doublet (will be reviewed)

Print entry




BibTex:
@InProceedings{Langdon:1995:GPdata,
  author =       "W. B. Langdon",
  title =        "Evolving Data Structures Using Genetic Programming",
  booktitle =    "Genetic Algorithms: Proceedings of the Sixth
                 International Conference (ICGA95)",
  year =         "1995",
  editor =       "L. Eshelman",
  pages =        "295--302",
  address =      "Pittsburgh, PA, USA",
  publisher_address = "San Francisco, CA, USA",
  month =        "15-19 " # jul,
  publisher =    "Morgan Kaufmann",
  keywords =     "Genetic Programming, Genetic Algorithms, Automatic
                 Programming, Machine Learning, Artificial Evolution,
                 Data Structures, Object Oriented Programming, Push down
                 Stack, First-in first-out (FIFO) Queue, Automatically
                 Defined Functions (ADF), Pareto fitness, Demes",
  ISBN =         "1-55860-370-0",
  URL =          "ftp://cs.ucl.ac.uk/genetic/papers/GPdata_icga-95.ps",
  size =         "8 pages",
  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.",
  notes =        "Discussed on GP mailing list 6--13 Jan 95, subj:
                 GPdata. Mainly as Langdon:1995:GPdataRN but with more
                 details on pareto selection",
}