Grammar-Guided Genetic Programming

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

  title =        "Grammar-Guided Genetic Programming",
  author =       "Daniel Manrique and Juan Rios and 
                 Alfonso Rodriguez-Paton",
  booktitle =    "Encyclopedia of Artificial Intelligence",
  publisher =    "IGI Global",
  year =         "2009",
  editor =       "Juan R. Rabu{\~n}al and Julian Dorado and 
                 Alejandro Pazos",
  chapter =      "114",
  pages =        "767--773",
  keywords =     "genetic algorithms, genetic programming",
  isbn13 =       "9781599048499",
  DOI =          "doi:10.4018/978-1-59904-849-9.ch114",
  DOI =          "doi:10.4018/978-1-59904-849-9",
  URL =          "",
  bibdate =      "2011-01-18",
  bibsource =    "DBLP,
  abstract =     "Evolutionary computation (EC) is the study of
                 computational systems that borrow ideas from and are
                 inspired by natural evolution and adaptation (Yao & Xu,
                 2006, pp. 1-18). EC covers a number of techniques based
                 on evolutionary processes and natural selection:
                 evolutionary strategies, genetic algorithms and genetic
                 programming (Keedwell & Narayanan, 2005). Evolutionary
                 strategies are an approach for efficiently solving
                 certain continuous problems, yielding good results for
                 some parametric problems in real domains. Compared with
                 genetic algorithms, evolutionary strategies run more
                 exploratory searches and are a good option when applied
                 to relatively unknown parametric problems. Genetic
                 algorithms emulate the evolutionary process that takes
                 place in nature. Individuals compete for survival by
                 adapting as best they can to the environmental
                 conditions. Crossovers between individuals, mutations
                 and deaths are all part of this process of adaptation.
                 By substituting the natural environment for the problem
                 to be solved, we get a computationally cheap method
                 that is capable of dealing with any problem, provided
                 we know how to determine individuals' fitness
                 (Manrique, 2001). Genetic programming is an extension
                 of genetic algorithms (Couchet, Manrique, Rios &
                 Rodriguez-Paton, 2006). Its aim is to build computer
                 programs that are not expressly designed and programmed
                 by a human being. It can be said to be an optimisation
                 technique whose search space is composed of all
                 possible computer programs for solving a particular
                 problem. Genetic programming's key advantage over
                 genetic algorithms is that it can handle individuals
                 (computer programs) of different lengths.
                 Grammar-guided genetic programming (GGGP) is an
                 extension of traditional GP systems (Whigham, 1995, pp.
                 33-41). The difference lies in the fact that they
                 employ context-free grammars (CFG) that generate all
                 the possible solutions to a given problem as sentences,
                 establishing this way the formal definition of the
                 syntactic problem constraints, and use the derivation
                 trees for each sentence to encode these solutions
                 (Dounias, Tsakonas, Jantzen, Axer, Bjerregard & von
                 Keyserlingk, D. 2002, pp. 494-500). The use of this
                 type of syntactic formalisms helps to solve the
                 so-called closure problem (Whigham, 1996). To achieve
                 closure valid individuals (points that belong to the
                 search space) should always be generated. As the
                 generation of invalid individuals slows down
                 convergence speed a great deal, solving this problem
                 will very much improve the GP search capability. The
                 basic operator directly affecting the closure problem
                 is crossover: crossing two (or any) valid individuals
                 should generate a valid offspring. Similarly, this is
                 the operator that has the biggest impact on the process
                 of convergence towards the optimum solution. Therefore,
                 this article reviews the most important crossover
                 operators employed in GP and GGGP, highlighting the
                 weaknesses existing nowadays in this area of research.
                 We also propose a GGGP system. This system incorporates
                 the original idea of employing ambiguous CFG to
                 overcome these weaknesses, thereby increasing
                 convergence speed and reducing the likelihood of
                 trapping in local optima. Comparative results are shown
                 to empirically corroborate our claims.",
  notes =        "3 Volumes. Inteligencia Artificial, Facultad de
                 Informatica, UPM, Spain",

Genetic Programming entries for Daniel Manrique Gamo Juan Rios Carrion Alfonso Rodriguez-Paton Aradas