Grammar-Guided Genetic Programming
Created by W.Langdon from
gp-bibliography.bib Revision:1.7954
- @InCollection{reference/ai/ManriqueRR09,
-
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 = "http://www.igi-global.com/bookstore/titledetails.aspx?TitleId=343",
-
bibdate = "2011-01-18",
-
bibsource = "DBLP,
http://dblp.uni-trier.de/db/reference/ai/ai2009.html#ManriqueRR09",
-
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 = "Cited by \cite{Krauss:2020:GI}
3 Volumes. Inteligencia Artificial, Facultad de
Informatica, UPM, Spain",
- }
Genetic Programming entries for
Daniel Manrique Gamo
Juan Rios Carrion
Alfonso Rodriguez-Paton Aradas
Citations