Evolving Recursive Programs for Tree Search

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

@InCollection{brave:1996:aigp2,
  author =       "Scott Brave",
  title =        "Evolving Recursive Programs for Tree Search",
  booktitle =    "Advances in Genetic Programming 2",
  publisher =    "MIT Press",
  year =         "1996",
  editor =       "Peter J. Angeline and K. E. {Kinnear, Jr.}",
  pages =        "203--220",
  chapter =      "10",
  address =      "Cambridge, MA, USA",
  keywords =     "genetic algorithms, genetic programming",
  ISBN =         "0-262-01158-1",
  URL =          "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.3005",
  URL =          "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.3005&rep=rep1&type=pdf",
  URL =          "http://cisnet.mit.edu/Advances-in-Genetic-Programming/220",
  abstract =     "This article compares basic genetic programming,
                 genetic programming with automatically defined
                 functions (ADFs), and genetic programming with ADFs
                 using a restricted form of recursion on a planning
                 problem involving tree search. The results show that
                 evolution of a recursive program is possible and
                 further that, of the three techniques explored, genetic
                 programming with recursive ADFs performs the best for
                 the tree search problem. Additionally, genetic
                 programming using ADFs (recursive and non-recursive)
                 outperforms genetic programming without ADFs. The
                 scalability of these techniques is also investigated.
                 The computational effort required to reach a solution
                 using ADFs with recursion is shown to remain
                 essentially constant with world size, while genetic
                 programming with non-recursive ADFs scales linearly at
                 best, and basic genetic programming scales
                 exponentially. Finally, many solutions were found using
                 genetic programming with recursive ADFs which
                 generalised to any world size.",
  notes =        "Recursive ADFs, non-recursive ADFs and non-ADF GP
                 compared on a tree searching problem. Tree depths 2-7
                 (ie up to 127 leaf nodes) containing one goal node.
                 Problem arranged so can only be solved (by luck?) or by
                 using memory. READ+WRITE update a single memory cell
                 per tree node, ie no index, just access current cell.
                 WRITE not as Teller but returns its argument. ADF1 and
                 ADF2 syntax set up so one can search tree and one can
                 move within it, cf. Andre.

                 Recursive ADFs much better than ADFs much better than
                 non-ADFs, difference increase as tree size increases.
                 {"}random{"}? program search can find recursive ADF
                 programs which solve problem.

                 DGPC",
  size =         "17 pages",
}

Genetic Programming entries for Scott Brave