A Probabilistic Linear Genetic Programming with Stochastic
Context-Free Grammar for solving Symbolic Regression
problems
Léo Françoso Dal Piccol Sotto

arXiv:1704.00828v1 [cs.NE] 3 Apr 2017

Federal University of São Paulo (UNIFESP)
Avenida Cesare Mansueto Giulio Lattes, 1201
São José dos Campos, SP, Brazil 12231-280
leo.sotto@unifesp.br

ABSTRACT
Traditional Linear Genetic Programming (LGP) algorithms are
based only on the selection mechanism to guide the search. Genetic
operators combine or mutate random portions of the individuals,
without knowing if the result will lead to a fitter individual. Probabilistic Model Building Genetic Programming (PMB-GP) methods
were proposed to overcome this issue through a probability model
that captures the structure of the fit individuals and use it to sample new individuals. This work proposes the use of LGP with a
Stochastic Context-Free Grammar (SCFG), that has a probability
distribution that is updated according to selected individuals. We
proposed a method for adapting the grammar into the linear representation of LGP. Tests performed with the proposed probabilistic
method, and with two hybrid approaches, on several symbolic regression benchmark problems show that the results are statistically
better than the obtained by the traditional LGP.

KEYWORDS
Estimation of Distribution Algorithms, Linear Genetic Programming, Symbolic Regression
ACM Reference format:
Léo Françoso Dal Piccol Sotto and Vinı́cius Veloso de Melo. 2017. A Probabilistic Linear Genetic Programming with Stochastic Context-Free Grammar
for solving Symbolic Regression problems. In Proceedings of the Genetic
and Evolutionary Computation Conference 2017, Berlin, Germany, July 15–19,
2017 (GECCO ’17), 8 pages.
DOI: 10.1145/nnnnnnn.nnnnnnn

1

INTRODUCTION

Evolutionary Algorithms (EAs, [1]) are stochastic methods that
use principles of natural evolution to search for solutions to optimization problems. Their search is based on random modifications
on the individuals of a population, performed by mutation and
crossover operators. In traditional EAs, the only mechanism that
guides the search to promising regions is the selection, which is
based on the fitness of the individuals. Other than that, EAs have
no knowledge on the search space.
Permission to make digital or hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. Copyrights for third-party components of this work must be honored.
For all other uses, contact the owner/author(s).
GECCO ’17, Berlin, Germany
© 2017 Copyright held by the owner/author(s). 978-x-xxxx-xxxx-x/YY/MM. . . $15.00
DOI: 10.1145/nnnnnnn.nnnnnnn

Vinı́cius Veloso de Melo

Federal University of São Paulo (UNIFESP)
Avenida Cesare Mansueto Giulio Lattes, 1201
São José dos Campos, SP, Brazil 12231-280
vinicius.melo@unifesp.br
This non-informed search issue motivated the design of Estimation of Distribution Algorithms (EDAs) [6]. EDAs are derived
from Genetic Algorithms (GAs) [13], but use a probability model
to sample individuals. At each generation, individuals are selected
from the population and used to update the model. This way, the
probability of sampling good solutions is increased and the search
concentrates on promising regions of the search space. The aim is
not only to increase the search efficiency but also its efficacy by solving previously unsolvable problems. Therefore, probability models
can provide mechanisms to largely improve the performance of
search algorithms, being a very relevant research topic.
A very popular example of EA used to design computer programs is the Genetic Programming algorithm (GP) [10]. In this
research field, EDAs are usually called Probabilistic Model Building Genetic Programming algorithms (PMB-GP) [8], and there are
several successful works showing that PMB-GP outperforms traditional GP [12, 22].
In this work, we propose a PMB-GP to improve a GP variant.
We developed a probability model for the Linear Genetic Programming (LGP) algorithm [5] and evaluated the resulting technique on
Symbolic Regression (SR) problems. As far as we know, there is no
grammar-based LGP, making this work novel. The model we chose
for this work is the Stochastic Context Free Grammar (SCFG). LGP
was chosen over GP because it presents interesting characteristics
that can make it perform better than GP; such characteristics will
be explained later in this paper.
The contributions of this work are: 1) introducing SCFG into
LGP; 2) the development of a method for updating an SCFG and
sampling LGP individuals from it; 3) testing the proposed algorithm
on SR problems; 4) the development of a hybrid method to retain
LGP features such as non-effective code, code reuse, and mutations;
5) a brief analysis of the impact of retaining the LGP features on
the SR results.
The rest of the work is organized as follows. Sections 2 and 3
present works related to PMB-GP and the background needed for
understanding the proposed technique. The proposed technique is
explained in detail in Section 4. Section 5 presents the experimental
setup and the experimental results using a simple grammar and a
more complex one, along with discussions. Finally, the conclusion
and future works are discussed in Section 6.

GECCO ’17, July 15–19, 2017, Berlin, Germany

2

PROBABILISTIC MODEL BUILDING
GENETIC PROGRAMMING

Over the last years, many techniques and models have been proposed to incorporate domain knowledge into the tree-based GP
search. Below we briefly describe some of them.
Probabilistic Incremental Program Evolution (PIPE) [12] uses
Probability Prototype Trees (PPTs). A PPT is a standard tree containing the maximum size an individual can reach. Each node has
a table with the probability of that specific node assuming each
terminal or non-terminal allowed for the given problem. However,
nodes are independent from each other.
In [21], PPT is extended to model the conditional probability of
each node with its parent by means of a Bayesian Network. The algorithm was called Estimation of Distribution Programming (EDP).
In [22], EDP is extended to a hybrid version using crossover and
mutation, improving the performance.
A greedy search combined with the MDL (Minimum Description
Length) metric is used in [14] to group nodes of a PPT. This grouping
strategy makes the model multivariate through the calculation of
the joint probability distribution. It can automatically identify nonoverlapping building blocks (BBs) to improve recombination and
reduce the chance of breaking good building blocks.
As previously introduced, grammars have also been studied as a
model for PMB-GP. Shan et al. proposed Program Evolution with
Explicit Learning (PEEL) [15], which uses a stochastic grammar
in which the Left-Hand Sides (LHS) also consist of the depth and
the relative location of the given tree node. The rules are refined
along the evolution process and updated by Ant Colony Optimization (ACO), in which a pheromone value is maintained for each
derivation to inform preferable paths. A similar approach is used
in [17].
A different approach for learning grammars is used in [16]. At
each generation, a very specific SCFG is learned for each best-fitted
individual. The rules are then merged in order to become more
general until the grammar can no longer be improved. The merging
is done by a greedy search using the MML (Minimum Message
Length) metric. The work of Bosman and De Jong [3] uses the same
search strategy for adding new rules (subfunctions) to the grammar
employed in their algorithm.
Wong et al. [20] proposed the GBBGP (Grammar-Based Bayesian
Genetic Programming) that uses a Bayesian Network associated
with each rule of an SCSG. The network models the probability of
choosing a derivation based on the parent node, sibling nodes, and
other context elements. An extension of that technique is proposed
in [19], where a Bayesian Network Classifier is used to derive a
probability distribution for each rule.
Regarding the EA, perhaps the most similar work to the present
one is [11], where N-grams are used in an LGP system. In an N-gram,
the probability of a random variable at position i is conditioned
to the values of the N − 1 last positions. The authors report that
their system was more scalable than LGP, being able to solve more
difficult problems and more frequently.
In the next section we introduce the EA used in this work.

Léo Françoso Dal Piccol Sotto and Vinı́cius Veloso de Melo

3

LINEAR GENETIC PROGRAMMING

Linear Genetic Programming (LGP) is a variant of GP that represents individuals linearly as sequences of instructions [5]. The
result of each instruction is stored into a register. The instruction
consists of an operator that acts on operands, which can be input
data, constants, or registers. An example of such a program for the
SR task is shown in Figure 1.

0: r[1] = x * 1
1: r[2] = x * r[1]
2: r[0] = r[2] + 3
3: r[4] = r[2] + r[1]

Figure 1: Example of an LGP program, representing the formula f (x) = x 2 + x. The first number of each line is the instruction identifier for further reference. The value stored
in the last register (instruction 3) is the program’s output.
The linear representation introduces two features: non-effective
code and code reuse. The non-effective code are instructions attributed to registers that are not used to compute the final result.
Instruction 2 in Figure 1, for instance, is non-effective because it is
not used afterwards. These instructions help to increase the number
of neutral variations (variations that do not change the result of
the program) and can make individuals more flexible - a genetic
operation on a non-effective instruction can make it effective.
The other feature - code reuse - can be exemplified by instruction 0 in Figure 1. It is used by instruction 1 and again by instruction 3. This feature is useful if the same result must be used
more than once in the same program, helping to evolve simpler
individuals.
Crossover in traditional LGP is as in GA (block swap between
parents), while mutation can be of two types: macro and micromutations. Macro-mutations change a complete instruction either
deleting, inserting, or substituting a random instruction. On the
other hand, micro-mutations change one element of an instruction
like the destination register, the operator, or an argument. Given the
existence of non-effective code and neutral variations, operators can
be made effective, that is, when possible, change only the effective
code of the individual.
The LGP implementation used in this work, called effmut, uses
only effective mutations, as reports show that this configuration
performs the best [4, 5]. It is a steady-state algorithm, as explained
in detail in [5]. At each generation, two tournaments are carried out,
yielding two winners and two losers. A copy of the winner replaces
the loser in the population, while the original winner undergoes
mutation according to the mutation rates. More details about the
operators are found in [5].

4

THE PROPOSED TECHNIQUE

In this section, we describe the model used in our approach, the
algorithm to sample individuals, the rule used to update the model
probabilities, and the hybrid algorithms.

A Probabilistic Linear Genetic Programming with Stochastic Context-Free Grammar for solving
GECCO
Symbolic
’17, July
Regression
15–19, 2017,
problems
Berlin, Germany

4.1

The Model

An SCFG is a CFG (Context Free Grammar) in which each rule has
a probability distribution associated with it. Such a grammar G can
be defined by a quintuple G = (T , NT , S, R, P) where: T is the set
of terminal symbols; NT is the set of non-terminal symbols; S is
the start symbol; R is the set of production rules; and P is the set of
probabilities on production rules.

Exp := Exp + Term | Exp - Term | Term | probs 0.5 0.25 0.25
Term := Term * Factor | Term / Factor | Factor | probs 0.5 0.0 0.5
Factor := (Exp) | Num | X | probs 0.1 0.1 0.8
Num =: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | probs 0.11 0.11 0.33 0.0 0.0 0.11 0.22 0.11 0.0
X := x 1 | x 2 | probs 0.8 0.2

Figure 2: Example SCFG for solving symbolic regression
problems. Each rule has a probability distribution associated with it after the keyword probs.
In this work, we are assuming that the probabilities for each
rule are independent. Hence, given a production A := B|C |D, the
probabilities of choosing to derive B, C, or D depend neither upon
the parent derivation nor the depth in the current derivation tree.
Figure 2 shows an example of an SCFG with the rules and the
corresponding probabilities for each derivation.

4.2

Sampling Individuals

To sample an individual from the SCFG, we use a recursive leftmost
derivation to construct a syntax tree; the difference being that the
final result of the process is a sequence of instructions instead of a
tree. The resulting program is a linear representation of what would
be a syntax tree, and has only effective code and no reuse. While
the tree is a functional paradigm where the results are passed from
the bottom to the top, the linear representation is the procedural
paradigm. Thus, it may be seen as an upside-down tree because
the arguments for a function must be instantiated previously in the
code.
One begins by sampling from the start symbol of the grammar,
which is represented by the last instruction of the program. If
the sampled production requires the further derivation of nonterminals, we call the function recursively (leftmost). The sequence
of instructions for the leftside argument of a binary operator comes
first in the individual; thus, the same store register cannot be used
later to store the results of the rightside argument. Figure 3 shows
an example of a derivation tree and the equivalent LGP program.
In the example, it can be noticed that there are repeated instructions. While the derivation is a non-terminal, a register receives
itself because one must keep track of where an instruction came
from. This way, one can update the correct production rule. This
will be explained further.
As a consequence of the chosen representation, the maximum
depth of a full binary tree equivalent to the sampled program is
limited by the maximum number of registers. Given that each inner
node of the equivalent tree corresponds to an instruction in the
program, one has:

I=

D−1
Õ

2i = 2D − 1,

(1)

i=0

where I is the number of instructions and D is the tree depth (starting with 0). Thus, a full binary tree with depth 9 would need 9
registers and 511 instructions to be represented by an LGP program
using our sampling algorithm. Nevertheless, individuals sampled
from the grammar tend to be much shorter than that.

4.3

Update Rule

At each generation, the probability distribution associated with each
rule of the grammar is updated towards the best individuals. That
way, individuals sampled from the updated grammar are supposed
to be better fitted to the given problem than if they are generated
randomly. The update rule used in the proposed algorithm is similar
to the one used in PBIL [2].
First, the N best individuals are selected from the population. As
seen in Figure 3, each instruction has an ID indicating which production of the grammar was used to derive it. With such information
from the selected individuals, one calculates a proportion of use of
productions for each distribution. Then, the probability distribution
of each rule is updated according to the following formula:
д+1

Probi j

д

д

= (1 − α) ∗ Probi j + α ∗ Propi j ,

(2)

where α is the learning rate that ranges from 0 to 1, д is the current
generation, i is the rule index, j is the production index, Prob is
the probability distribution, and Prop is the proportion of use. The
proportion calculation is carried out for all instructions considering
all N selected individuals at the same time.
As it stands, the proposed Grammar-Based LGP (GB-LGP) method
of updating the model and resampling the population at each generation without using the genetic operators is not different from a
GP with the same kind of grammar (EDA style). The only difference
here is that the tree is represented linearly - no LGP extra feature
is present. In order to introduce non-effective code, code reuse,
and make use of the macro and micro-mutation operators, a hybrid
scheme was developed.

4.4

The Hybrid Approach

We designed a hybrid approach that combines the mutation operators of LGP with the resampling from SCFG. The role of the hybrid
approach is to introduce, via mutation operators, non-effective code
and code reuse, and to add the benefits of the LGP evolution into
the technique. Also, the running time of the algorithm is reduced
when the resampling rate is lowered, as it is a costly procedure.
Two hybrid schemes were investigated in this work: 1) Resampling the entire population at each s generations and applying
mutations in the other ones (Hybrid GB-LGP v1); 2) At each generation, resample half of the population and generate the other half by
mutations (Hybrid GB-LGP v2). In this last scheme, a tournament
is performed, the winner is mutated, and the original winner along
with the resulting individual of the mutation are passed to the next
generation.
An issue arises because one must keep track of the productions
used to generate the instructions. When an individual’s instruction

GECCO ’17, July 15–19, 2017, Berlin, Germany

Léo Françoso Dal Piccol Sotto and Vinı́cius Veloso de Melo

Figure 3: In the left, one has the syntax tree of f (x) = x + 1 using the grammar shown in Figure 2. In the right, one has the
LGP program that represents the tree, along with the parts of the tree that corresponds to each part of the program, and the
associated grammar production. The order of construction is the order in which the recursive algorithm builds the program.
The production ID (i, j) identifies which production is associated with each instruction, where i is the number of the rule and
j is the number of the associated production.
is mutated, part of the grammar productions associated to it may
no longer be valid, misleading the update rule of the distributions.
This may change not only the instruction being mutated, but also
the production of its parent or children. To simplify the present
implementation, we ignore this cascade effect and focus only on
the instruction being mutated. However, it is paramount to deal
with such effect to avoid breaking the model.
Macro and micro-mutations can change the production of an
instruction to one that whether involves the identity operator (such
as r [0] = r [0]) or not. When mutation does not involve the identity
operator, one simply replaces the production that is currently associated to the instruction with the production that has the selected
operator.
On the other hand, when a production is changed to another
one that involves the identity operator, more than one option is
possible for the new production. For instance, in the grammar in
Figure 2, the possibilities to generate a terminal node (argument)
are in the following path: Exp := Term, Term := Factor, Factor :=
(Exp), Factor := Num, Factor := X, and the productions for rules
Num and X . For this case, one checks the content of the argument
register of the identity operator. For instance, in the sequence
r [1] = 1; r [1] = r [1]; r [1] = r [1], the argument register is r [1]
and its content is 1. Based on the production used to generate
this instruction, one knows which production to associate to the
resulting mutated instruction.

5

5.1

Experimental Setup

The configuration of algorithms effmut, GB-LGP, Hybrid1, and Hybrid2 are presented in Table 1. These values were either suggested
by previous works on LGP [4, 5] or chosen empirically without
fine-tuning. The operators allowed for effmut are the same that
appear in the grammar for each of the two experiments. However,
effmut does not use a grammar. GB-LGP and the hybrids need more
registers to allow for larger trees to be derived, as explained before.
Parameter
Value
Initial Program Size
20*
Maximum Program Size
200*
8*, 13**
Allowed Registers
Population Size
100
100
Generations
Elite
1
Tournament Size
2
0.75
Macro-Mutation Rate
Insertion
0.66
Deletion
0.33
Micro-Mutation Rate
0.25
N
3**
s
2**
α
0.1**
Table 1: Configuration of the tested techniques. The symbol
* means that the configuration is valid only for effmut, while
** is for GB-LGP and the hybrids.

EXPERIMENTS

In this section, we present the experimental analysis of the proposed
algorithms on well-known SR benchmark functions of distinct difficulty levels. The experiments were elaborated to investigate the
performance of the proposed techniques against the effmut baseline,
with the objective of outperforming it. Thus, in this study, we are
not interested in comparing our methods with others than effmut.

First, we tested the algorithms on simpler benchmark functions
that require only sum and multiplication to be solved, using an
equally simple grammar. We later tested them using a grammar
with more options on more complex functions.
We performed 100 independent runs and compared the results
using the Median of the Mean Absolute Error (MMAE), the Median

A Probabilistic Linear Genetic Programming with Stochastic Context-Free Grammar for solving
GECCO
Symbolic
’17, July
Regression
15–19, 2017,
problems
Berlin, Germany
Absolute Deviation (MAD)1 , and the success rate. A solution is
successful if its mean error is less than 1e-05. For the statistical
comparison we employed the Pairwise Wilcoxon’s Rank-Sum Test
at significance level α = 0.05.
We implemented all algorithms in Python and ran the experiments on a system environment with an Intel(R) Xeon(R) CPU
E5-2620@2.00GHz, Ubuntu Linux 14.04, Kernel 3.13.0-30- generic
x86 64, GCC (Ubuntu 4.8.2-19ubuntu1), and Python 2.7.6.

5.2

Experiment one

In this experiment, we test the algorithms on polynomials. The
grammar and the functions (taken from [18]) are shown, respectively, in Figure 4 and Table 2.

Exp := Exp + Term | Exp - Term | Term | probs 0.33 0.33 0.33
Term := Term * Factor | Term / Factor | Factor | probs 0.33 0.33 0.33
Factor := (Exp) | Num | X | probs 0.33 0.33 0.33
Num =: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | probs 0.11 0.11 0.11 0.11 0.11 0.11 0.11 0.11 0.11
X := x 1 | ... | x D | probs …

Figure 4: SCFG used in the first experiment. The X rule depends on the dimension D of the function (number of input
data terminals).

Name
nguyen1
nguyen2
nguyen3
nguyen4

Function
x3 + x2 + x
x4 + x3 + x2 + x
x5 + x4 + x3 + x2 + x
x6 + x5 + x4 + x3 + x2 + x

D
1
1
1
1

Train / Test
U[-1,1,20]
U[-1,1,20]
U[-1,1,20]
U[-1,1,20]

Table 2: The SR functions used in the first experiment.
U [a, b, c] means c samples from a uniform distribution from
a to b.

Table 3 shows the results obtained for this experiment: MMAE,
MAD, and success rate. Table 4 shows the p-values from the statistical comparison.
Compared to effmut, the algorithms that employ the probabilistic model yielded much better results. For the simpler functions
(nguyen1 and nguyen2), the success rate of GB-LGP was at least
80%, while effmut reached a maximum of 32%. For the fifth order
polynomial (nguyen3), the error increased substantially, but the
proposed approaches still showed a much better success rate than
effmut. Finally, for the sixth order polynomial (nguyen4), the success rate was very low and very similar for all techniques. However,
the probabilistic algorithms found solutions with a much smaller
error.
Given that the grammar is simple, and the rules that need to
be learned are clear, the inferior performance on the higher order
polynomials may be explained by the limitation of registers, which
limit the depth of the equivalent tree. For instance, if the production
Term := Factor is chosen multiple times in sequence, although the
1 MAD = median |V −median(V ) |, i = 1, ..., L , where V is an array of numerical
i
values and L is its length.

result is not affected, the tree depth is, which limits the further representation of the program. A suggestion could be removing such
sequences from the individuals, leaving only one of the equivalent
productions. However, as we need them to know the productions
used to generate the instructions, we must advance our research to
elaborate a better tracking system.
As for the hybrid approaches, although they did perform better than effmut, which was our primary objective, they did not
outperform GB-LGP. The statistical tests in Table 4 suggest that
the differences between GB-LGP and the hybrids are not, in the
most part, significant. However, one can observe a trend in Table 5
for the hybrids being worse than GB-LGP. We do not know if the
effects on the productions of the individuals caused by the mutation
operators were the reason for this lower performance; it will be
deeply investigated in a future work. Nevertheless, because the
hybrids resample less than GB-LGP, they are faster and could be
preferable over GB-LGP to solve these problems.
In order to asses the impact of the hybrid approach on the individuals, Figure 5 shows the evolution of the mean percentage of
effective code in the population for each function. As expected,
individuals in effmut have very few effective code. In GB-LGP, the
entire code is effective, as no genetic operator is applied on them.
Hybrid v1 switches between having only effective code and having
a little of non-effective code. As the population was resampled
every two generations, there was no time to increase the amount
of non-effective code. In Hybrid v2, programs remained mostly
effective, with only a small amount of non-effective code. We conclude that the hybrid approaches worked well in introducing LGP
features into the programs.

5.3

Experiment two

In this experiment, we incorporated some other functions to the
grammar and tested the algorithms on different benchmark functions from [7, 9]. Figure 6 shows the resulting grammar and Table
5 specifies the functions.
MMAE and MAD for this second experiment are shown in Table 6, and the p-values are shown in Table 7. We are not presenting
the success rates because they were very small.
The results in this experiment follow the same pattern of the
previous experiment, with GB-LGP yielding the best results, and the
techniques that use the probabilistic model performing better than
effmut. As both the functions and the grammar are more complex in
this experiment, the prediction errors (MMAE and MAD) were not
as small as in the previous experiment. No method could perform
well on Korns’ functions, likely due to the constants that must be
tuned.
Although the mean error shown in Table 6 for GB-LGP on
nguyen3 is lower than that in Table 3, in this second experiment the
algorithm had no success. The population approximated the data
with other functions present in the extended grammar (Figure 6),
such as sin and cos. This suggests that a more complex grammar may
lead the search more easily to stagnation on sub-optimal (wrong)
solutions.
The hybrid versions were expected to overcome that issue at
some level, but it did not occur. The failure may be related to
the parameters or the way the productions associated with an

GECCO ’17, July 15–19, 2017, Berlin, Germany

Léo Françoso Dal Piccol Sotto and Vinı́cius Veloso de Melo

nguyen1

Method

nguyen2

MMAE (MAD)

Success

nguyen3

nguyen4

MMAE (MAD)

Success

MMAE (MAD)

Success

MMAE (MAD)

Success

effmut

0.20 (0.53)

0.32

0.22 (0.43)

0.23

0.27 (0.34)

0.11

0.24 (0.35)

0.05

GB-LGP

2.77e-17 (0.34)

0.88

4.99e-17 (0.29)

0.8

0.07 (0.59)

0.33

0.08 (0.22)

0.04

Hybrid v1

3.67e-17 (0.23)

0.86

6.00e-17 (4.58e-16 )

0.69

0.09 (0.39)

0.22

0.12 (0.29)

0.06

Hybrid v2

3.26e-17 (2.24e-15)

0.74

0.02 (0.14)

0.5

0.09 (0.47)

0.27

0.14 (0.34)

0.05

Mean percentage of effective code

Table 3: Descriptive statistics for experiment one.

nguyen1

nguyen2

nguyen3

nguyen4

1.00

0.75

0.50

●

●
0.25

0

●

●

●

25

50

75

100

0

●

●
●

●

25

●

●

50

75

●
100

0

●

●

●

●

25

50

75

100

0

●

●

●

●

25

50

75

100

Method
● effmut
GB−LGP
Hybrid_v1
Hybrid_v2

Generations

Figure 5: Mean percentage of effective code throughout the generations. The curves are means over 100 runs.

Exp := Exp + Term | Exp - Term | Term | probs 0.33 0.33 0.33
Term := Term * Factor | Term / Factor | Factor | probs 0.33 0.33 0.33
Factor := sin(Arg) | cos(Arg) | exp(Arg) | ln(Arg) | Arg | probs 0.2 0.2 0.2 0.2 0.2
Arg := (Exp) | Num | X | probs 0.33 0.33 0.33
Num =: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | probs 0.11 0.11 0.11 0.11 0.11 0.11 0.11 0.11 0.11
X := x 1 | ... | x D | probs …

Figure 6: SCFG used in the second experiment. The X rule depends on the dimension D of the benchmark function (number of terminals).
individual are updated after a mutation. Nonetheless, the use of the
hybrid versions make it possible to obtain better results than with
effmut in less time than with GB-LGP, as less samplings from the
grammar take place.
In order to evaluate how big solutions get using the grammar,
Table 8 shows the mean size, in number of instructions and effective instructions, of the solutions found. The effective size of the
solutions created with the grammar are not much bigger than the
ones found by effmut. In fact, they have a smaller total size.
Method

nguyen1

nguyen2

nguyen3

nguyen4

GB-LGP x effmut

5.17e-13

2.72e-15

6.63e-10

2.69e-06

Hybrid v1 x effmut

8.88e-10

1.18e-13

1.56e-06

6.00e-04

Hybrid v2 x effmut

3.41e-10

8.26e-09

2.28e-06

4.13e-03

Hybrid v1 x GB-LGP

0.19

0.12

0.06

0.20

Hybrid v2 x GB-LGP

0.19

3.15e-03

0.06

0.01

Hybrid v1 x Hybrid v2

0.91

0.06

0.88

0.21

Table 4: p-values from Pairwise Wilcoxon Rank-Sum Test.

It is not possible to show how every grammar evolved for each
technique on each function, due to the large amount of space needed
for that. However, to illustrate how the grammar evolves, Figure 7
shows the evolution of the probability distributions for GB-LGP on
the Korns5 function. One can observe, for instance, that the high
probability of generating solutions containing ln, a number (5),
and x 2 , which is the only input that the benchmark function uses.
This plot is a strong indicative that our algorithms are working
as expected and that improvements can be obtained in further
investigations.

6

CONCLUSIONS AND FUTURE WORK

The use of grammars to enhance the performance of Genetic Programming algorithms is a well-investigated topic, but its Linear
counterpart was still unexplored, as far as we know. LGP is harder
to implement than GP, and tracking the changes to adequately
update the model proved to not be trivial.
In this work, the use of SCFG to acquire some knowledge about
the search space during the evolution and to guide the process
allowed the proposed algorithms to obtain better results than the
standard LGP on a set of well-known Symbolic Regression problems.
When using a simple grammar on polynomials, GB-LGP was able
to achieve high success rates. The hybrid approaches were also able
to outperform the standard LGP (effmut) while introducing LGP
mutations and reducing the execution time. The promising results
open an avenue for many future investigations.
The proposed algorithms faced some issues: the existence of sequences of instructions that represent the same production rule and
do not affect the final result of a program, like an identity attribution
r [0] = r [0] used several times in sequence; the effects of the mutation operators to the productions associated to an individual; the
convergence to local optima, or simply a stagnation in the wrong

A Probabilistic Linear Genetic Programming with Stochastic Context-Free Grammar for solving
GECCO
Symbolic
’17, July
Regression
15–19, 2017,
problems
Berlin, Germany
Name

Function

D

Train

Test

nguyen3

x5 + x4 + x3 + x2 + x

1

U[-1,1,20]

U[-1,1,20]

nguyen6

sin(x ) ∗ sin(x + x 2 )

1

U[-1,1,20]

U[-1,1,20]

keijzer4

x 3 ∗ e −x ∗ cos(x ) ∗ sin(x ) ∗ (sin(x )2 ∗ cos(x ) − 1)

1

E[0,10,0.05]

E[0.05,10.05,0.05]

keijzer5

30∗x ∗z
(x −10)∗y 2

3

x,z: U[-1,1,500]

x,z: U[-1,1,10000]

−5.41 + 4.9 ∗

korns3

v −x +y/w
3∗w

3 + 2.13 ∗ ln(w )

korns5

y: U[1,2,500]

y: U[1,2,10000]

5

U[-50,50,500]

U[-50,50,10000]

5

U[0,50,500]

U[0,50,10000]

Table 5: The SR functions used in the first experiment. E[a, b, c] means a sequence of numbers spaced by an interval of c from
a to b.

Method

nguyen3

nguyen6

keijzer4

keijzer5

korns3

korns5

effmut

0.223 (0.315)

0.083 (0.342)

0.204 (1.35e-16)

0.348 (0.089)

528.54 (0.27)

1.493 (0.077)

GB-LGP

0.042 (0.184)

0.017 (0.245)

0.159 (0.028)

0.136 (0.063)

594.31 (0.09)

0.628 (0.363)

Hybrid v1

0.048 (0.184)

0.024 (0.244)

0.154 (0.021)

0.134 (0.044)

291.29 (0.13)

0.778 (0.464)

Hybrid v2

0.049 (0.207)

0.022 (0.178)

0.182 (0.112)

0.147 (0.072)

666.26 (0.15)

1.275 (0.162)

Table 6: Descriptive statistics - MMAE (MAD) - for experiment two.

Method

nguyen3

nguyen6

keijzer4

keijzer5

korns3

korns5

GB-LGP x effmut

3.317e-21

1.328e-14

3.350e-15

5.469e-12

1

6.612e-12

Hybrid v1 x effmut

1.644e-15

1.229e-09

1.141e-19

1.569e-10

0.774

5.039e-14

Hybrid v2 x effmut

1.481e-16

4.815e-08

3.463e-12

5.897e-06

1

1.086e-11

Hybrid v1 x GB-LGP

0.025

0.119

3.326e-4

0.960

0.269

0.894

Hybrid v2 x GB-LGP

0.025

0.097

0.182

0.134

1

0.832

Hybrid v1 x Hybrid v2

0.884

0.680

7.257e-06

0.134

0.241

0.832

Table 7: p-values from Pairwise Wilcoxon Rank-Sum Test.

Method

nguyen3

nguyen6

keijzer4

keijzer5

korns3

effmut

7.5 / 57

12 /58

9.5 / 48

13 / 51

13 / 51.5

korns5
5 / 57.5

GB-LGP

21 / 21

22 / 22

35 / 35

29 / 29

29.5 / 29.5

21.5 / 21.5

Hybrid v1

22 / 26

25 / 28.5

34 / 44.5

29.5 / 40.5

35.5 / 43.5

20.5 / 24

Hybrid v2

25 / 25

23 / 25

28 / 29

31.5 / 36.5

33 / 34.5

21.5 / 24.5

Table 8: Mean effective size / total size of the final solution.

regions of the search-space, because of function approximations
using the wrong operators.
In future works, the following issues will be explored:
• Removing sequences of equivalent instructions that augment the depth of the equivalent tree;
• Investigate parsing the individuals after the use of a mutation operator in order to correctly find which productions
from the grammar should be updated;
• Develop genetic operators that take into consideration
information of the probability distributions of the SCFG
rules;
• Investigate methods to reduce the complexity (size) of the
solutions;
• Either incorporate dependency into SCFG or replace it by
another model better fit to the LGP representation.

ACKNOWLEDGMENTS
This work was supported by Fundação de Amparo à Pesquisa do
Estado de São Paulo (FAPESP – Proc. 2016/07095-5).

REFERENCES
[1] T. Bäck. 1996. Evolutionary Algorithms in Theory and Practice: Evolution Strategies,
Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford,
UK.
[2] S. Baluja. 1994. Population-Based Incremental Learning: A Method for Integrating
Genetic Search Based Function Optimization and Competitive Learning. Technical
Report. Pittsburgh, PA, USA.
[3] P. A. N. Bosman and E. D. De Jong. 2004. Grammar transformations in an EDA for
genetic programming. In In GECCO 2004 Workshop Proceedings (Seattle. 26–30.
[4] M. Brameier and W. Banzhaf. 2001. Effective Linear Genetic Programming. Technical Report. Department of Computer Science, University of Dortmund, 44221
Dortmund, Germany.
[5] M. F. Brameier and W. Banzhaf. 2007. Linear genetic programming. Springer.
[6] M. Hauschild and M. Pelikan. 2011. An introduction and survey of estimation of
distribution algorithms. Swarm and Evolutionary Computation 1, 3 (2011), 111 –

GECCO ’17, July 15–19, 2017, Berlin, Germany

Léo Françoso Dal Piccol Sotto and Vinı́cius Veloso de Melo

Exp

Term
Exp − Term

Term

Term * Factor

1.0

1.0

0.8

0.8
Probability

Probability

Exp + Term

0.6
0.4
0.2

0.6
0.4

0.0
0

20

40

60

80

100

0

20

40

Generations

cos(Arg)

60

80

100

Generations

Factor
sin(Arg)

Arg

exp(Arg)

ln(Arg)

Arg

(Exp)

1.0

1.0

0.8

0.8
Probability

Probability

Factor

0.2

0.0

0.6
0.4
0.2

Num

X

0.6
0.4
0.2

0.0

0.0
0

20

40

60

80

100

0

20

40

Generations

2

3

4

60

80

100

Generations

Num
1

X

5

6

7

8

9

1

1.0

1.0

0.8

0.8
Probability

Probability

Term / Factor

0.6
0.4
0.2

2

3

4

5

0.6
0.4
0.2

0.0

0.0
0

20

40

60

80

100

Generations

0

20

40

60

80

100

Generations

Figure 7: Evolution of the probability distribution of each rule of the grammar throughout the generations for Korns5. The
curves are the mean of the 100 independent runs.
128.
[7] M. Keijzer. 2003. Improving Symbolic Regression with Interval Arithmetic
and Linear Scaling. In Proceedings of the 6th European Conference on Genetic
Programming (EuroGP’03). Springer-Verlag, 70–82.
[8] K. Kim, Y. Shan, X. H. Nguyen, and R. I. McKay. 2014. Probabilistic model building
in genetic programming: a critical review. Genetic Programming and Evolvable
Machines 15, 2 (2014), 115–167.
[9] M. F. Korns. 2011. Accuracy in Symbolic Regression. Springer New York, New
York, NY, 129–151.
[10] J. R. Koza. 1992. Genetic programming: on the programming of computers by
means of natural selection. MIT Press, Cambridge, MA, USA.
[11] R. Poli and N. F. McPhee. 2008. A Linear Estimation-of-distribution GP System. In
Proceedings of the 11th European Conference on Genetic Programming (EuroGP’08).
Springer-Verlag, Berlin, Heidelberg, 206–217.
[12] R. Salustowicz and J. Schmidhuber. 1997. Probabilistic Incremental Program
Evolution. Evol. Comput. 5, 2 (June 1997), 123–141.
[13] K. Sastry, D. Goldberg, and G. Kendall. 2005. Genetic Algorithms. Springer US,
Boston, MA, 97–125.
[14] K. Sastry and D. E. Goldberg. 2003. Probabilistic Model Building and Competent
Genetic Programming. Springer US, Boston, MA, 205–220.
[15] Y. Shan, R. I. Mckay, H. A. Abbass, and D. Essam. 2003. Program Evolution
with Explicit Learning: a New Framework for Program Automatic Synthesis. In
University College, University of New South. IEEE Press, 1639–1646.

[16] Y. Shan, R. I. McKay, R. Baxter, H. Abbass, D. Essam, and H. X. Nguyen. 2004.
Grammar model-based program evolution. In Evolutionary Computation, 2004.
CEC2004. Congress on, Vol. 1. 478–485 Vol.1.
[17] I. Tanev. 2004. Implications of Incorporating Learning Probabilistic Contextsensitive Grammar in Genetic Programming on Evolvability of Adaptive Locomotion Gaits of Snakebot. In GECCO 2004 Workshop Proceedings. Seattle, Washington,
USA.
[18] N. Q. Uy, N. X. Hoai, M. O’Neill, R. I. Mckay, and E. Galvan-Lopez. 2011.
Semantically-based Crossover in Genetic Programming: Application to Realvalued Symbolic Regression. Genetic Programming and Evolvable Machines 12, 2
(June 2011), 91–119.
[19] PK. Wong, LY. Lo, ML. Wong, and KS. Leung. 2014. Grammar-based Genetic
Programming with Dependence Learning and Bayesian Network Classifier. In
Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO ’14). ACM, New York, NY, USA, 959–966.
[20] P. K. Wong, L. Y. Lo, M. L. Wong, and K. S. Leung. 2014. Grammar-Based Genetic
Programming with Bayesian network. In Evolutionary Computation (CEC), 2014
IEEE Congress on. 739–746.
[21] K. Yanai and H. Iba. 2003. Estimation of distribution programming based on
Bayesian network. In Evolutionary Computation, 2003. CEC ’03. The 2003 Congress
on, Vol. 3. 1618–1625 Vol.3.
[22] K. Yanai and H. Iba. 2004. Program evolution by integrating EDP and GP. In In
Genetic and Evolutionary Computation Conference. Springer-Verlag, 774–785.

