Page 86 - 49A Field Guide to Genetic Programming

72 8 Probabilistic Genetic Programming

3
a small set of artificial problems, including a GP version of one-max and a
4
GP version of the fully deceptive trap function . Results suggest that PIPE
and standard GP have similar scaling properties, but that standard subtree
crossover inherently links neighbouring nodes whereas PIPE does not.
Sastry and Goldberg (2003) proposed an algorithm called extended com-
pact GP (eCGP) which effectively extends the eCGA algorithm (Harik,
1999) to trees. Like PIPE, eCGA assumes that all trees will fit within a
fixed maximal tree. It partitions the nodes in this maximal tree into groups.
The nodes in a group are assumed to be linked and their co-occurrence is
modelled by a full joint distribution table. As with eCGA, the probability
of generating a particular tree is given by the product of the probabilities of
generating each group of nodes using the groups’ joint distributions. An ad-
vantage of this system is that, unlike PIPE, it captures dependencies among
primitives. However, to the best of our knowledge this system has only been
tested on the two artificial problems used by Ondas et al. (2005) to compare
PIPE and GP. Consequently its behaviour on more typical GP problems is
unknown.
Yanai and Iba (2003) proposed an EDA called estimation of distribution
programming (EDP) which, in principle, can capture complex dependencies
between a node in a program tree and the nodes directly above it or to its
left. 5 As with eCGP and PIPE, programs are tree-like and are assumed
to always fit within an ideal maximal full tree. A conditional probability
table is necessary for each node in such a tree to capture the dependencies.
To keep the size of data structures manageable, only pairwise dependencies
between each node and its parent were stored and used. EDP was tested on
both the Max problem (Gathercole and Ross, 1995) and the 6-multiplexer.
A later hybrid algorithm combining EDP and GP was proposed (Yanai and
Iba, 2004) which showed promise when tested on three symbolic regression
problems.
An EDA based on a hierarchical BOA was used as the main mechanism
to generate new individuals in meta-optimising semantic evolutionary search
(MOSES) (Looks, 2007). This combined multiple strategies and used seman-
tics to restrict and direct the search. BOA was also used to evolve programs
in (Looks, Goertzel, and Pennachin, 2005) using a specialised representation
for trees.

3 One-max is a simple GA test problem where the goal is to maximise the number of
1’s in a binary string.
4 Trap functions are fitness functions that have a gradual slope leading to a sub-optimal
local maxima, and a steep valley between that local maxima and the global optima. They
therefore tend to “trap” populations on the local maxima
5 In the general case a node can depend on the choices of any of the nodes that have
already been chosen. Since the tree is constructed in a depth-first, left-to-right fashion,
it can depend on any nodes that are its direct ancestors, or any nodes that are to its left
in the tree. In practice, however, EDP only tracked the conditional probability of a node
on its parent.