Page 88 - 49A Field Guide to Genetic Programming

74 8 Probabilistic Genetic Programming

Recently an EDA-based system called N-gram GP (Poli and McPhee,
2008a) has been proposed that allows the evolution of linear GP programs.
To some extent, N-gram GP overcomes the common difficulties EDAs have
in performing local search when using a centralised population model. The
N-gram GP system is able to capture both the local and the global features
of the optimal sampling distribution, albeit at the cost of imposing certain
other constraints. This makes it possible, for example, for the search to focus
on the neighbourhood of a small number of individuals without the need to
choose among them. Tests on polynomial symbolic regression problems and
the lawnmower problem were very encouraging.

8.3 Mixing Grammars and Probabilities

A variety of other systems have been proposed which combine the use of
grammars and probabilities. We mention only a few here; a more extended
review of these is available in (Shan, McKay, Essam, and Abbass, 2006).
Ratle and Sebag (2001) used a stochastic context-free grammar to gen-
erate program trees. The probability of applying each rewrite rule was
adapted using a standard EDA approach so as to increase the likelihood of
using successful rules. The system could also be run in a mode where rule
probabilities depended upon the depth of the non-terminal symbol to which
a rewrite rule was applied, thereby providing a higher degree of flexibility.
The approach taken in program evolution with explicit learning (PEEL)
(Shan, McKay, Abbass, and Essam, 2003) was slightly more general. PEEL
used a probabilistic L-system where rewrite rules were both depth- and
location-dependent. The probabilities with which rules were applied were
adapted by an ant colony optimisation (ACO) algorithm (Dorigo and
St¨utzle, 2004). Another feature of PEEL was that the L-system’s rules
could be automatically refined via splitting and specialisation.
Other programming systems based on probabilistic grammars which are
optimised via ant systems include ant-TAG (Abbass, Hoai, and McKay,
2002; Shan, Abbass, McKay, and Essam, 2002), which uses a tree-adjunct
grammar as its main representation, and generalised ant programming
(GAP) (Keber and Schuster, 2002), which is based on a context-free gram-
mar. Other systems which learn and use probabilistic grammars include
grammar model based program evolution (GMPE) (Shan, McKay, Baxter,
Abbass, Essam, and Hoai, 2004), the system described in (Bosman and de
Jong, 2004a,b) and Baysian automatic programming (BAP) (Regolin and
Pozo, 2005).