On the use of a directed acyclic graph to represent a population of computer programs

by

Handley, S.

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: Proceedings of the 1994 IEEE World Congress on Computational Intelligence (Conference proceedings), 1994, p. 154-159
Keywords:genetic algorithms, genetic programming
Abstract:
This paper demonstrates a technique that reduces the time and space requirements of genetic programming. [GP] The population of parse trees is stored as a directed acyclic graph (DAG), rather than as a forest of trees. This saves space by not duplicating structurally identical subtrees. Also, the value computed by each subtree for each fitness case is cached, which saves computation both by not recomputing subtrees that appear more than once in a generation and by not recomputing subtrees that are copied from one generation to the next. I have implemented this technique for a number of problems and have seen a 15- to 28-fold reduction in the number [TNO] of nodes extant per generation and an 11- to 30-fold reduction in the number [TNO] of nodes evaluated per run (for populations of size 500).
Notes:
Converts whole GP population to a directed Acyclic Graph, which is functionally equivelent. With primatives that have NO SIDE EFFECTS is able to cache earlier sub tree evaluations so they donot have to be re-evaluated, even if occur in a different individual. Claims speed ups of 11-30 fold.
URL(s):(G)zipped postscript

Review item:

Mark as doublet (will be reviewed)

Print entry




BibTex:
@InProceedings{Handley:1994:DAGpcp,
  author =       "S. Handley",
  title =        "On the use of a directed acyclic graph to represent a
                 population of computer programs",
  booktitle =    "Proceedings of the 1994 IEEE World Congress on
                 Computational Intelligence",
  year =         "1994",
  pages =        "154--159",
  address =      "Orlando, Florida, USA",
  month =        "27-29 " # jun,
  publisher =    "IEEE Press",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://www-leland.stanford.edu/~shandley/postscript/caching_paper___first_draft.ps.gz",
  size =         "6 pages",
  abstract =     "This paper demonstrates a technique that reduces the
                 time and space requirements of genetic programming. The
                 population of parse trees is stored as a directed
                 acyclic graph (DAG), rather than as a forest of trees.
                 This saves space by not duplicating structurally
                 identical subtrees. Also, the value computed by each
                 subtree for each fitness case is cached, which saves
                 computation both by not recomputing subtrees that
                 appear more than once in a generation and by not
                 recomputing subtrees that are copied from one
                 generation to the next. I have implemented this
                 technique for a number of problems and have seen a 15-
                 to 28-fold reduction in the number of nodes extant per
                 generation and an 11- to 30-fold reduction in the
                 number of nodes evaluated per run (for populations of
                 size 500).",
  notes =        "Converts whole GP population to a directed Acyclic
                 Graph, which is functionally equivelent. With
                 primatives that have NO SIDE EFFECTS is able to cache
                 earlier sub tree evaluations so they donot have to be
                 re-evaluated, even if occur in a different individual.
                 Claims speed ups of 11-30 fold.",
}