# Probabilistic Structured Grammatical Evolution

Jessica Mégane University of Coimbra
CISUC
Dept. of Informatics Engineering
Coimbra, Portugal
<EMAIL_ADDRESS>Nuno Lourenço University of Coimbra
CISUC
Dept. of Informatics Engineering
Coimbra, Portugal
<EMAIL_ADDRESS>Penousal Machado University of Coimbra
CISUC
Dept. of Informatics Engineering
Coimbra, Portugal
<EMAIL_ADDRESS>
###### Abstract

The grammars used in grammar-based Genetic Programming (GP) methods have a
significant impact on the quality of the solutions generated since they define
the search space by restricting the solutions to its syntax. In this work, we
propose Probabilistic Structured Grammatical Evolution (PSGE), a new approach
that combines the Structured Grammatical Evolution (SGE) and Probabilistic
Grammatical Evolution (PGE) representation variants and mapping mechanisms.
The genotype is a set of dynamic lists, one for each non-terminal in the
grammar, with each element of the list representing a probability used to
select the next Probabilistic Context-Free Grammar (PCFG) derivation rule.
PSGE statistically outperformed Grammatical Evolution (GE) on all six
benchmark problems studied. In comparison to PGE, PSGE outperformed 4 of the 6
problems analyzed.

###### Index Terms:

Grammatical Evolution, Grammar-based Genetic Programming, Grammar Design,
Probabilistic.

##  I Introduction

Evolutionary Algorithms (EAs) are metaheuristic algorithms driven by an
objective function that follow a trial-and-error approach to problem-solving.
Inspired by the principles of natural selection and genetics, these algorithms
evolve a population of individuals towards better solutions, using an
objective function, over several generations. The quality of solutions
improves by selecting the most promising ones (taking into account the
objective function), and applying stochastic variations using operators
similar to mutations and recombinations that take place in biological systems,
where individuals with higher fitness are more likely to survive and
reproduce.

Genetic Programming (GP) [1] is a branch of EAs in which individuals are
represented as computer programs that evolve to solve problems, without the
need to program the solution explicitly. Grammatical Evolution (GE) [2, 3, 4]
is a GP approach that uses a Context-Free Grammar (CFG) to constrain the
search space of possible solutions. The individuals are represented by a list
of integers (i.e., genotype), where each value (i.e., codon) is used to choose
a production rule of the grammar until it forms a solution to the problem
(i.e., phenotype).

Despite being one of the most widely used GP variants, GE is not exempt from
having some issues [5, 6]. GE has low locality, which means that small changes
in the genotype often cause large changes in the phenotype, causing
exploitation to be replaced for exploration, which can lead to a behaviour
similar to random search [7]. GE also suffers from high redundancy, which
means that often changes in the genotype do not cause changes in the phenotype
[5]. To overcome these issues, numerous methods have been proposed in the
literature. Most of these methods perform changes in grammars [8, 9, 10, 11],
representation of individuals [12, 13, 14, 15, 16, 17] or population
initialization [18, 19, 20, 21, 22].

In this paper we propose a new method called Probabilistic Structured
Grammatical Evolution (PSGE) that results from the combination of the
representation of Structured Grammatical Evolution (SGE) and the mapping
mechanism of Probabilistic Grammatical Evolution (PGE). The main motivation
for this work rises from the interest of creating a method that inherits the
main advantages of the representation used by SGE, namely the high locality
and low redundancy [23, 24], with the probabilistic mapping form PGE that is
able to guide the evolutionary process towards better solutions by iteratively
adjusting the biases of the grammar.

Identically to SGE, the genotype in PSGE is a set of dynamic lists of real
values, with a list for each non-terminal of the grammar. Each element of the
list (i.e., codon) represents the probability of choosing a production rule
from the grammar, which are updated based on the phenotype of the best
individual at the end of each generation, using the same mapping mechanism
proposed by PGE. PSGE is compared with GE, PGE and SGE on six different
benchmark problems and the results showed that PSGE version is better than GE
and PGE.

The remainder of this work is structured as follows: Section II presents the
background necessary to understand the work presented, introducing GE as well
as related work. Section III present the proposed method, detailing the
representation and mapping method used. Section IV details the experimentation
framework used and Section V the experimental results regarding performance.
Section VI gathers the main conclusions and provides some insights regarding
future work.

##  II Grammatical Evolution

GE [2, 3, 4] is a grammar-based GP approach used to evolve programs. Each
individual in the population is represented by a list of integers, called
genotype, and each value is randomly generated in the interval $[0,255]$. The
elements of the list are used in the mapping process to create the phenotype,
that is the solution of the problem, using the production rules defined by a
CFG. A grammar is a tuple $G=(NT,T,S,P)$ where $NT$ and $T$ represent the non-
empty set of Non-Terminal (NT) and Terminal (T) symbols, $S$ is an element of
$NT$ in which the derivation sequences start, called the axiom, and $P$ is the
set of production rules. The rules in $P$ are in the form $A::=\alpha$, with
$A\in NT$ and $\alpha\in(NT\cup T)^{+}$. The $NT$ and $T$ sets are disjoint.
Each grammar defines a language $L(G)=\\{w:\,S\overset{*}{\Rightarrow}w,\,w\in
T^{*}\\}$, that is the set of all sequences of terminal symbols that can be
derived from the axiom. The symbol $*$ represents the unary operator Kleene
star.

$\displaystyle{<}\text{expr}{>}::=$
$\displaystyle\,{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle|\,{<}\text{var}{>}$ $\displaystyle{<}\text{op}{>}::=$
$\displaystyle\,+\,$ $\displaystyle|\,-$ $\displaystyle|\,*$
$\displaystyle|\,/$ $\displaystyle{<}\text{var}{>}::=$ x
$\displaystyle|\,\text{y}\,$ $\displaystyle|\,\text{1.0}\,$

Figure 1: Example of a CFG.

The mapping from genotype to phenotype is done starting from the axiom of the
grammar and expanding the leftmost non-terminal. The codons of the genotype
are used to choose which production rule to expand by applying the modulo
operator ($mod$) between the codon and the number of derivation rules of the
respective non-terminal.

Gen otype $\displaystyle{[}\text{34, 13, 9, 151, 95, 221, }$
$\displaystyle\text{23, 98, 145, 42, 153}{]}$
$\displaystyle{<}\text{expr}{>}\rightarrow$
$\displaystyle\,{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle 34mod2=0$
$\displaystyle{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,{<}\text{var}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle 13mod2=1$
$\displaystyle{<}\text{var}{>}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{x}\,{<}\text{op}{>}{<}\text{expr}{>}$ $\displaystyle
9mod3=0$ $\displaystyle\text{x}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{x}\,\text{/}\,{<}\text{expr}{>}$ $\displaystyle
151mod4=3$ $\displaystyle\text{x}\,\text{/}\,{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{x}\,\text{/}\,{<}\text{var}{>}$ $\displaystyle 95mod2=1$
$\displaystyle\text{x}\,\text{/}\,{<}\text{var}{>}\rightarrow$ x/1.0
$\displaystyle 221mod3=2$ Phenotype: $\displaystyle x/1.0$

Figure 2: Example of the genotype-phenotype mapping of GE.

An example of the genotype-phenotype process is shown in Fig. 2, using the
example of grammar presented in Fig. 1. The mapping begins with the axiom of
the grammar, $<$expr$>$, which has two expansion alternatives, and the first
unused codon of the genotype, $34$. By applying the modulo operator between
the codon and the number of production rules, $34mod(2)=0$, we obtain the
index of the rule to be expanded which is $<$expr$><$op$><$expr$>$. This
procedure is repeated until there are no more non-terminal symbols to expand
or numbers from the genotype to read. In the last case, if we still have non-
terminals to expand, we can employ a wrapping technique, in which the genotype
is reused until it yields a valid individual or the predefined number of wraps
is reached. If we haven’t mapped all of the non-terminals after all of the
wraps, the mapping procedure will stop and the individual will be considered
invalid. The fitness function is used to evaluate each individual’s phenotype,
and then the population is subjected to selection procedures.

###  II-A Related Work

GE is one of the most popular GP variants, and it has undergone various
modifications over the years to address some of its major criticisms, namely
high redundancy and low locality. Low locality refers to small genotype
changes that result in large phenotypic changes, whereas high redundancy
refers to multiple genotypes corresponding to the same phenotype. The majority
of these proposed solutions include changes to grammars [8, 10, 9, 11],
individual representation [12, 13, 25, 15, 16, 17], or population
initialization [18, 19, 20, 21, 22].

SGE [25] addresses GE’s locality and redundancy issues while achieving better
performance results [14]. The genotype in SGE is a set of dynamic lists of
ordered integers, one list for each non-terminal of the grammar. Each value in
the list represents which production rule to select from the non-terminal.
Different grammar-based GP approaches were compared in [26], and the authors
demonstrated that SGE outperformed several grammar-based GP representations in
some problems.

Position Independent Grammatical Evolution ($\pi$GE) [16] is a method that
uses a new representation and mapping mechanism in which the genotype of the
individual determines the order of expansion of the non-terminals, reducing
the positional dependency that exists in GE. Individual genotypes are made of
tuples of two values (nont, rule), with nont determining which non-terminal to
expand next and rule determining the rule to derive from that non-terminal. On
several problems, this technique outperformed GE, with statistical
differences.

Chorus [17] is another method that allows for positional independence, with
each gene encoding only one production of the grammar. This strategy, however,
has not been proved to be superior than the GE standard.

The design of the grammars is another aspect that has had some attraction for
researchers since they define the search space, and thus the choice of grammar
can affect the speed of convergence to the best solution [9]. Some research
has been done to study the performance of GE with various types of grammars,
such as the use of recursively balanced grammars [8, 9] and the reduction of
non-terminal symbols [10, 9].

Harper et al. [8] demonstrated that the grammar used at the start of the
evolutionary process can have a significant impact on the solutions, such as
generating a large number of invalid individuals when using recursive
grammars. It has also been demonstrated that when a balanced grammar is used,
there is more variety in the size of solutions.

Nicolau et al. [9] tested GE with different grammars, which included balanced
grammars, grammars with corrected biases, and grammars with unlinked
productions. The experimental tests using a recursively balanced grammar, in
which there is a non-recursive production for every recursive one, yielded
better results than the original grammar. However it resulted in a larger
number of individuals consisting of a non-terminal symbol. Nicolau [10]
proposed a method for reducing the number of non-terminal symbols, replacing
them with their productions, which, while showing a slight improvement in
performance, has the disadvantage of producing complex grammars that are
difficult to read.

Another area of research has been the evolution of the grammar throughout the
evolutionary process [11, 15, 12, 13].

Grammatical Evolution by Grammatical Evolution ((GE)2) [11] is a method where
the grammar and genetic code co-evolve. The method employs two distinct
grammars: universal grammar and solution grammar. The structure of the
solution grammar, which is used to map the individuals, is dictated by the
universal grammar. This method has been shown to be effective in developing
biases toward non-terminal symbols. Later, it was implemented into a new
algorithm, meta-Grammar Genetic Algorithm (mGGA) [27], which resulted in
improved performance.

PGE [15] is a recent variant of GE in which the individuals are mapped using a
Probabilistic Context-Free Grammar (PCFG) and the genotype is a list of real
numbers. A PCFG is a quintuple $PG=(NT,T,S,P,Probs)$ where $NT$ and $T$
represent the non-empty set of Non-Terminal (NT) and Terminal (T) symbols, $S$
is an element of $NT$ called the axiom, $P$ is the set of production rules,
and $Probs$ is a set of probabilities associated with each production rule.
The mapping begins with the leftmost non-terminal, and the rule whose
probability interval includes the codon is chosen for each non-terminal to be
expanded. The PCFG probabilities are updated at the end of each generation
based on the expansion rules used to create the best individual of the current
generation alternating with the best individual overall. PGE proved to be
superior than GE with statistical differences in the two problems studied.

Kim et al. [12] proposed Probabilistic Model Building Grammatical Evolution
(PMBGE), in which the mapping is based on a PCFG and the probabilistic
technique Estimation Distribution Algorithm (EDA), which also replaces the
mutation and crossover operators. The probabilities of the grammar are changed
every generation based on the frequency of the rules expanded by the best
individuals. This technique generates a new population from the new grammar at
each generation. When compared to GE, the proposed approach performed
similarly. Later, Kim et al.[13] adapted Conditional Dependency Tree (CDT) to
the mechanism of updating the grammar, creating cdPMBGE which takes into
account the dependencies between production rules. The results revealed no
statistical differences between GE and the proposed approach. This method
outperformed GE with statistical differences in two of the four problems
analysed.

##  III Probabilistic Structured Grammatical Evolution

In this work we propose PSGE 111The implementation of PSGE is available at:
https://github.com/jessicamegane/psge in which the representation of
individuals and the mapping mechanism is a combination of the approaches
followed by SGE and PGE. The mapping resorts to a PCFG to choose the
derivation rules. At the end of each generation the probabilities of the
grammar are updated according to the production rules expanded by the best
individual of the current generation or the best individual overall.

The individuals are represented by a set of dynamic lists, with each list
being associated with a non-terminal of the grammar. The lists contain an
ordered sequence of real numbers, with each codon corresponding to the
probability of choosing a production rule.

The pseudo-code of the initialization of individuals in PSGE is presented in
Alg. 1. The algorithm takes as parameters the genotype (which starts with an
empty list for each non-terminal), the non-terminal symbol to expand (the
axiom of the grammar in the first iteration), the current depth (which starts
at 0), the maximum depth limit and the PCFG. The function is recursive and
ends when the genotype belongs to a valid individual. At each iteration a
random value between 0 and 1 is generated and added to the list of the non-
terminal to be expanded (Alg. 1, lines 2-3). To determine which rule to expand
next based on the new codon, the mapping process is simulated (Alg. 1, line
4).

Algorithm 1 Random candidate solution of PSGE

1:procedure createIndividual(genotype, symb, depth, max_depth, pcfg)

2: codon = $random$(0,1)

3: genotype[symb].append(codon)

4: selected_rule = $generate\\_expansion$(symb, codon, pcfg, depth, max_depth)

5: expansion_symbols = pcfg[symb][selected_rule]

6: for sym in expansion_symbols do

7: if not $is\\_terminal$(sym) then

8: $createIndividual$(genotype, symb, depth + 1, max_depth, pcfg)

9: end if

10: end for

11:end procedure

The approach for genotype-phenotype mapping is described in Alg. 2. The
genotype, a counter called $positions\\_to\\_map$ (which is initially empty
and is used to store the genotype position of each non-terminal list at the
current iteration), the symbol to expand (which starts in the axiom), the
current depth, the maximum depth limit, and the grammar are all passed as
arguments to the algorithm. If more codons are required to construct a valid
individual during mapping, they will be created at random and added to the
genotype (Alg. 2, lines 3-6). One of the benefits of this representation is
that with the depth limit, it is feasible to add productions as needed without
the risk of bloat (a significant increase in the size of the solutions [28]),
ensuring that valid individuals are always created.

Algorithm 2 Genotype-Phenotype mapping of PSGE

1:procedure mapping(genotype, positions_to_map, symb, depth, max_depth, pcfg)

2: phenotype = ""

3: if positions_to_map[symb] $>=$ $len$(genotype[symb]) then

4: codon = $random$(0,1)

5: genotype[symb].append(codon)

6: end if

7: codon = genotype[symb][positions_to_map[symb]]

8: selected_rule = $generate\\_expansion$(symb, codon, pcfg, current_depth,
max_depth)

9: expansion = pcfg[symb][selected_rule]

10: positions_to_map[symb] += 1

11: for sym in expansion do

12: if $is\\_terminal$(sym) then

13: phenotype += sym

14: else

15: phenotype += $mapping$(genotype, positions_to_map, sym, depth + 1,
max_depth, pcfg)

16: end if

17: end for

18: return phenotype

19:end procedure

To choose the derivation rule to expand, we use the function that is described
in Algorithm 3. The function receives as parameters the non-terminal symbol to
be expanded, the codon, the grammar, the current depth and the maximum depth
established. The mechanism for choosing the derivation rule is based on that
of PGE [15], in which the rule whose probability interval incorporates the
value of the codon is chosen (Alg. 3, lines 15-21), however for PSGE when the
depth limit is reached, only non-recursive production rules are considered
(Alg. 3, lines 4-13). In this case, the probabilities of the non-recursive
rules are adjusted proportionally so that their sum is 1. The codon value is
compared with the new probability values, and the rule whose probability range
includes the codon value is chosen.

Algorithm 3 PSGE function to select an expansion rule

1:procedure generate_expansion(symb, codon, pcfg, depth, max_depth)

2: cum_prob = 0.0

3: if depth $\geq$ max_depth then

4: nr_prods = $get\\_non\\_recursive\\_prods$(pcfg[symb])

5: total_nr_prods = $sum$(nr_prods.$getProb$())

6: for prod in non_recursive_prods do

7: new_prob = prod.$getProb$() / total_nr_prods

8: cum_prob = cum_prob + new_prob

9: if codon $\leq$ cum_prob then

10: selected_rule = prod

11: break

12: end if

13: end for

14: else

15: for prod in pcfg[symb] do

16: cum_prob = cum_prob + prod.$getProb()$

17: if codon $\leq$ cum_prob then

18: selected_rule = prod

19: break

20: end if

21: end for

22: end if

23: return selected_rule

24:end procedure

PCFG Prob. $\displaystyle{<}\text{expr}{>}::=$
$\displaystyle\,{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle[0.00;0.37]$ $\displaystyle|\,{<}\text{var}{>}$
$\displaystyle]0.37;1.00]$ $\displaystyle{<}\text{op}{>}::=$
$\displaystyle\,+\,$ $\displaystyle[0.00;0.22]$ $\displaystyle|\,-$
$\displaystyle]0.22;0.39]$ $\displaystyle|\,*$ $\displaystyle]0.39;0.68]$
$\displaystyle|\,/$ $\displaystyle]0.68;1.00]$
$\displaystyle{<}\text{var}{>}::=$ x $\displaystyle[0.00;0.41]$
$\displaystyle|\,\text{y}$ $\displaystyle]0.41;0.67]$
$\displaystyle|\,\text{1.0}$ $\displaystyle]0.67;1.00]$

Figure 3: PCFG example. Prob. represents the range of values covered by each
production rule, and the size of the range corresponds to the probability of
that production rule being chosen.

An example of an individual’s mapping process is depicted in Fig. 4, using the
grammar in Fig. 3. The process begins by expanding the axiom of the grammar,
$<$expr$>$, using the first codon in the list of the respective non-terminal
of the genotype, in this case $0.19$. The non-terminal $<$expr$>$ presents two
derivation rules, with different probabilities of being chosen. The $0.19$
codon is included in the range of probabilities of the first rule,
$<$expr$><$op$><$exp$>$, therefore expansion is made for that rule. The
derivation is always done from the leftmost non-terminal, so the next non-
terminal to expand is $<$expr$>$. The next available codon in the list of the
non-terminal $<$expr$>$ is $0.46$, which falls within the probability range of
the second expansion rule, $<$var$>$. The $<$var$>$ will be the next to expand
and has three derivation rules. $0.32$ is the first codon available in the
list of $<var>$ of the genotype, and falls within the range of probabilities
covered by the first production rule, $x$, which is a terminal symbol, so
$<$op$>$ is the next symbol to expand. The procedure is repeated until a valid
individual is formed.

Genot ype <expr><op> <var> [0.19,0.46,0.87][0.27] [0.32, 0.64]
$\displaystyle{<}\text{expr}{>}\rightarrow$
$\displaystyle\,{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle(0.19)$
$\displaystyle{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,{<}\text{var}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle(0.46)$
$\displaystyle{<}\text{var}{>}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{x}\,{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle(0.32)$
$\displaystyle\text{x}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{x}\,\text{-}\,{<}\text{expr}{>}$ $\displaystyle(0.27)$
$\displaystyle\text{x}\,\text{-}\,{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{x}\,\text{-}\,{<}\text{var}{>}$ $\displaystyle(0.87)$
$\displaystyle\text{x}\,\text{-}\,{<}\text{var}{>}\rightarrow$ x-y
$\displaystyle(0.64)$ Phenotype: $\displaystyle x-y$

Figure 4: Example of the genotype-phenotype mapping of PSGE with a PCFG.

At the end of each generation the best individual overall and the best
individual from the current generation are used alternately to update the PCFG
probabilities, using the same mechanism proposed for PGE [15]. All individuals
are re-mapped to update the phenotype according to the new updated grammar.

For each production i of each non-terminal j we have a counter with the number
of times that each production was chosen, and the probability (prob) of the
PCFG of choosing that production. If the counter is greater than zero, that
is, the production rule was used to map the individual, we use (1). If the
counter is zero, that is, the production rule has not been used by the
individual, we use (2). The learning factor is represented by $\lambda$, with
$\lambda\in[0,1]$, and is used to make the transitions on the search space
smoother.

$prob_{i}=min(prob_{i}+\lambda*\frac{counter_{i}}{\sum_{k=1}^{j}counter_{k}},1.0)$
(1)

$prob_{i}=prob_{i}-\lambda*prob_{i}$ (2)

After updating the probabilities using the equations, these are adjusted until
the sum of the probabilities of each production rule of each non-terminal is
1.

###  III-A Variation Operators

Genetic operators are used to introduce genotype-level changes in individuals,
such as mutation and crossover. The mutation operator changes randomly chosen
codons, and in PSGE a Gaussian mutation is applied to these codons, keeping
the new value in the interval $[0,1]$. This type of mutation is widely used in
the literature and has proven to be an effective method for making small
changes in the search space [29, 30].

Genotype before mutation: $<expr>$$<op>$$<var>$
[0.19,0.46,0.87][0.27][0.32, 0.64]

Genotype after mutation: $<expr>$$<op>$$<var>$
[0.19,0.29,0.87][0.27][0.32, 0.28]

Figure 5: Example of PSGE’s mutation on one codon of the genotype.

Fig. 5 is an example of Gaussian mutation in an individual. Assuming that the
second codon of the non-terminal $<expr>$, was randomly selected ($0.46$) and
the value generated with a normal distribution of mean 0 and standard
deviation 0.50 ($N(0,0.50)$) was $-0.17$, the codon will now assume a value of
$0.29$.

Parents genotype:
Parent 1:
$<expr>$$<op>$$<var>$
[0.19,0.46,0.87][0.27][0.32,0.64]

Parent 2:
$<expr>$$<op>$$<var>$
[0.02,0.90,0.13][0.48][0.75,0.42,0.56]

Mask and offspring after crossover:
Mask:
$<expr>$$<op>$$<var>$
110

Offspring:
$<expr>$$<op>$$<var>$
[0.02,0.90,0.13][0.48][0.32,0.64]

Figure 6: Example of PSGE’s crossover between two individuals, generating one
offspring.

The crossover operator combines the genetic material of two individuals to
generate an offspring, and is based on the crossover proposed by SGE [25]. The
offspring inherits the list of each non-terminal from one of the parents, and
this decision is made based on a randomly generated binary mask. The mask
contains a binary value for each list of the genotype (i.e., one for each non-
terminal of the grammar). In Fig. 6 are represented an example of crossover,
showing the parents, the mask used and the offspring. In the example, the
descendant inherited the lists of the non-terminals $<expr>$ and $<op>$ from
Parent 2, and the list of the non-terminal $<var>$ from Parent 1. In case two
descendants are generated, the other would get the opposite lists.

##  IV Experimental Setup

The performance of PSGE will be carried out following the framework proposed
by Whigham et al. [7], examining the evolution of the mean best fitness of
each generation over 100 independent runs in six problems of different scopes.
The results will be compared with the standard GE, PGE, and SGE. Table I
presents the parameters used by all the approaches.

TABLE I: Parameters used in the experimental analysis for GE, PGE, SGE and PSGE. Parameters | GE | PGE | SGE | PSGE
---|---|---|---|---
Population Size | 1000
Generations | 50
Elitism Count | 100
Mutation Rate | 0.05
Crossover Rate | 0.90
Tournament | 3
Size of Genotype | 128 | -
Max Depth | - | 10

In what concerns the variation operators, GE and PGE use a one point
crossover. The mutation of GE replaces the selected codons by new ones
randomly generated in the interval $[0,255]$ and in the case of PGE a float
mutation is used, in which the codons are replaced by new ones generated in
the interval $[0,1]$. The wrapping mechanism was removed from GE and PGE.
Regarding the genetic operators used by SGE and PSGE, these methods all use
the same crossover, which is the one presented in Section III-A. Regarding the
mutation operator, in the case of SGE, the mutated codon is replaced with a
different valid option, while in PSGE a Gaussian mutation with $N(0,0.50)$ in
the codon value is performed.

A detailed description of the problems and the grammars used can be found in
the work done by Lourenço et al. [26] and Whigham et al. [7], and were
selected on the basis of the recommendations of McDermott et al. [31]. The
problems considered were the quartic symbolic regression, pagie symbolic
regression [32], the Boston Housing symbolic regression [33], 5-bit even
parity, 1-bit Boolean multiplexer and the Santa Fe artificial ant problem [1].
The objective functions used to evaluate the individuals consider the
minimization of the error. In the case of Symbolic Regression and
classification problems the fitness is the Root Relative Squared Error (RRSE)
between the individual’s solution and the target on a data set. For the
Boolean functions, the error is the number of incorrect predictions, and for
the Path finding problem, the fitness is the number of pieces remaining after
exceeding the step limit.

##  V Results

A statistical analysis was done to be able to fairly compare the different
methods and support our analysis. Since the populations were independently
initialized and the results do not meet the criteria for parametric tests, the
Kruskal-Wallis non-parametric test was used to check for meaningful
differences between the different methods. When the methods show differences,
we verify in which pairs the differences exist, using the Mann-Whitney post-
hoc test with the Bonferroni correction. To determine how significant the
differences are, the effect size $r$ was calculated. The "~" sign was used
when there were no significant differences between samples, the "+" sign was
used when the effect size was small ($r\leq 0.3$), "++" was used when the
effect size was medium ($0.3<r\leq 0.5$), and "+++" was used when the effect
size is large ($r>0.5$). For all the statistical tests we considered a
significance level of $\alpha=0.05$.

TABLE II: Results of the Mann-Whitney post-hoc statistical tests. The
Bonferroni correction is used considering a significance level of $\alpha$ =
0.05. Values in bold mean that PSGE is statistically better than GE, PGE or
SGE.
Problem | PSGE-GE | PSGE-PGE | PSGE-SGE
---|---|---|---
Quartic Polynomial | 0.000 | 0.003 | 0.299
Pagie Polynomial | 0.033 | 0.008 | 0.013
Boston Housing Train | 0.000 | 1.000 | 0.001
Boston Housing Test | 0.000 | 0.525 | 0.577
5-bit Parity | 0.000 | 0.000 | 0.131
11-multiplexer | 0.000 | 0.000 | 0.000
Santa Fe Ant Trail | 0.000 | 0.000 | 0.317
TABLE III: Effect size between PSGE and GE, PGE and SGE. Problem | PSGE-GE | PSGE-PGE | PSGE-SGE
---|---|---|---
Quartic Polynomial | ++ | + | ~
Pagie Polynomial | + | - | -
Boston Housing Train | + | ~ | -
Boston Housing Test | ++ | ~ | ~
5-bit Parity | +++ | +++ | ~
11-multiplexer | ++ | +++ | \- - -
Santa Fe Ant Trail | + | + | ~

Focusing on the results of Tables II and III, several observations about the
approach proposed in this work can be drawn. In bold are the p-values of the
comparisons where PSGE is statistically better than GE, PGE or SGE.

PSGE is statistically better than GE on all problems. Comparing the
performance of PSGE with PGE, we see that PSGE outperforms PGE with
significant differences on four of the problems. In relation to the SGE, PSGE
never outperforms.

Figure 7: Performance results for the Quartic Polynomial. Results are the mean
best fitness of 100 runs.

Fig. 7 shows the evolution of the mean best fitness for the quartic
polynomial. We can see that the decrease in SGE and PSGE is similar, with SGE
ending up with slightly better average fitness, but with no statistical
differences between the methods (Table II). Looking at the PGE curve, we
notice that it starts with better fitness, being surpassed by SGE and PSGE
around generation 3, decreasing more slowly in relation to the other methods.
From generation 20 the fitness starts to move away from GE values, however
these never reach the performance of SGE and PSGE during the 50 generations.
PSGE presents statistical differences from PGE with a small effect size.

Figure 8: Performance results for the Pagie Polynomial. Results are the mean
best fitness of 100 runs.

The results for the pagie polynomial are shown in Fig. 8. By analysing the
plot we see that all methods perform better than GE, with the curves
decreasing faster, and looking at the statistical test results in Table II we
see that PSGE is better than GE statistically with a small effect size. The
method that ends up with the best average fitness is PGE, which is in line
with the results presented in [15].

Figure 9: Testing results for the Boston Housing. Results are the mean best
fitness of 100 runs.

Regarding the results for the Boston Housing problem, these are divided in 90%
for training and 10% for testing. The test results are the most relevant since
they are the ones that evaluate the models with unseen data. The statistical
tests show that in this problem PSGE only presents statistical differences
relative to GE, having a small effect size in training and medium in testing.
PSGE ends with better fitness than PGE, however these do not present
significant differences. We also see that when comparing with SGE in the
training, PSGE presents small statistical differences, being worse, however,
in the test, these are not significant. The small improvement in the results
of test PSGE over training when compared to GE and PSGE, may indicate that
PSGE has a better generalisation ability to predict unknown data.

Figure 10: Performance results for the 5-bit Even Parity problem. Results are
the mean best fitness of 100 runs.

Looking at the results for the 5-bit Even Parity problem, we observe that the
performance of SGE and PSGE is better than that of GE and PGE, starting with
lower fitness values. According to the statistical results, PSGE is
statistically better than GE and PGE, with a large effect size. In comparison
to SGE we see that the decrease of PSGE is slightly faster, maintaining better
average fitness for 30 generations, and then it is reached by SGE, presenting
no significant differences between the two methods.

Figure 11: Performance results for the 11-bit Boolean Multiplexer problem.
Results are the mean best fitness of 100 runs.

Regarding the results of the tests done for the 11-bit Boolean Multiplexer
(Fig. 11), we can see that the methods behave quite differently. As observed
previously for the 5-bit parity problem (Fig. 10), the average fitness of SGE
and PSGE individuals at the beginning of the evolutionary process is better,
with significant differences between PSGE and GE, with a medium effect size,
and also with PGE presenting a large effect size. In this problem we see that
the decrease of SGE is much steeper, rapidly moving away from the average
fitness of PSGE.

Figure 12: Performance results for the Santa Fe Artificial Ant problem.
Results are the mean best fitness of 100 runs.

The last analysis studies the performance on the Santa Fe Ant problem (Fig.
12). In contrast to the previous analyses, in this problem the method that
performs worst over generations is PGE. On the other hand we observe that the
fitness of the individuals of SGE and PSGE decreases rapidly, approaching the
optimal solution after 20 generations. PSGE is statistically better than GE
and PGE, not presenting statistical differences in relation to SGE.

##  VI Conclusion

GE is a grammar-based GP variant that has attracted the attention of many
researchers and practitioners, since its proposal in the late 1990s and it has
been applied with success to many problem domains. However, it has been shown
that it suffers from some issues, such as low locality and high redundancy [5,
6].

In grammar-based GP, the choice of the grammar has a significant impact on the
quality of the generated solutions as it is the grammar that defines the space
of possible solutions. Our goal work was to create a variant of GE that could
guide the search towards better solutions, inserting bias in the production
rules that generate better individuals, in order to achieve a better overall
performance, and at the same time overcome the problems of GE.

In this paper we present PSGE, a new variant of GE that introduces a new
representation alternative to SGE, using PGE’s mapping mechanism. The genotype
is a set of dynamic lists, one for each non-terminal of the grammar. Each
codon in the list represents the likelihood of selecting a production rule. At
the end of each generation the PCFG is updated and individuals are remapped,
same as in PGE.

The proposed method is compared to the standard versions of GE, PGE and SGE on
different benchmark problems, analysing the evolution of the mean best
fitness. PSGE outperformed GE with statistical differences in all problems,
while it outperformed PGE in 4 of the 6 problems. Regarding the relative
performance with SGE, we show that the methods obtain similar performances.

PSGE proved to be a good alternative to PGE, since it presents better
performance, keeping the advantage of using a probabilistic grammar. At the
end of the evolutionary process we get a specialised grammar for the problem
at hand which can be used to obtain information about which production rules
are more relevant to create the best individuals. The use of a PCFG can also
be used by manually guide the search, for example, in the real-world problems
where we have some information regarding some problems, we can alter the
probabilities of the grammar by introducing some known biases. As future work
it will be interesting to analyze the average fitness of sample populations
created with a previously evolved grammar and also to analyze the fitness
evolution over multiple generations. Another line of work that will be
interesting to analyze is to test the algorithm behavior with the
probabilities of grammars initialized randomly, or with different types of
grammars, similar to the study done by Nicolau et al. [9].

## Acknowledgment

This work was partially funded by the project grant DSAIPA/DS/0022/2018
(GADgET), by FEDER funds through the Operational Programme Competitiveness
Factors - COMPETE and national funds by FCT - Foundation for Science and
Technology (POCI-01-0145-FEDER-029297, CISUC - UID/CEC/ 00326/2020) and within
the scope of the project A4A: Audiology for All (CENTRO-01-0247-FEDER-047083)
financed by the Operational Program for Competitiveness and
Internationalisation of PORTUGAL 2020 through the European Regional
Development Fund.

## References

  * [1] J. R. Koza, “Genetic programming as a means for programming computers by natural selection,” _Statistics and Computing_ , vol. 4, no. 2, Jun. 1994\.
  * [2] M. O’Neill and C. Ryan, _Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language_. Springer US, 2003.
  * [3] C. Ryan, J. Collins, and M. O. Neill, “Grammatical evolution: Evolving programs for an arbitrary language,” in _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 1998, pp. 83–96.
  * [4] C. Ryan, M. O'Neill, and J. Collins, Eds., _Handbook of Grammatical Evolution_. Springer International Publishing, 2018.
  * [5] F. Rothlauf and D. E. Goldberg, “Redundant representations in evolutionary computation,” _Evolutionary Computation_ , vol. 11, no. 4, pp. 381–415, Dec. 2003.
  * [6] F. Rothlauf and M. Oetzel, “On the locality of grammatical evolution,” in _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 2006, pp. 320–330.
  * [7] P. A. Whigham, G. Dick, J. Maclaurin, and C. A. Owen, “Examining the "best of both worlds" of grammatical evolution,” in _Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation_. ACM, Jul. 2015.
  * [8] R. Harper, “GE, explosive grammars and the lasting legacy of bad initialisation,” in _IEEE Congress on Evolutionary Computation_. IEEE, Jul. 2010.
  * [9] M. Nicolau and A. Agapitos, “Understanding grammatical evolution: Grammar design,” in _Handbook of Grammatical Evolution_. Springer International Publishing, 2018, pp. 23–53.
  * [10] M. Nicolau, “Automatic grammar complexity reduction in grammatical evolution,” in _GECCO 2004 Workshop Proceedings_ , R. Poli, S. Cagnoni, M. Keijzer, E. Costa, F. Pereira, G. Raidl, S. C. Upton, D. Goldberg, H. Lipson, E. de Jong, J. Koza, H. Suzuki, H. Sawai, I. Parmee, M. Pelikan, K. Sastry, D. Thierens, W. Stolzmann, P. L. Lanzi, S. W. Wilson, M. O’Neill, C. Ryan, T. Yu, J. F. Miller, I. Garibay, G. Holifield, A. S. Wu, T. Riopka, M. M. Meysenburg, A. W. Wright, N. Richter, J. H. Moore, M. D. Ritchie, L. Davis, R. Roy, and M. Jakiela, Eds., Seattle, Washington, USA, 26-30 2004.
  * [11] M. O’Neill and C. Ryan, “Grammatical evolution by grammatical evolution: The evolution of grammar and genetic code,” in _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 2004, pp. 138–149.
  * [12] H. Kim and C. W. Ahn, “A new grammatical evolution based on probabilistic context-free grammar,” in _Proceedings in Adaptation, Learning and Optimization_. Springer International Publishing, 2015, pp. 1–12.
  * [13] H. Kim, H. Kang, and C. W. Ahn, “A conditional dependency based probabilistic model building grammatical evolution,” _IEICE Transactions on Information and Systems_ , vol. E99.D, no. 7, pp. 1937–1940, 2016.
  * [14] N. Lourenço, F. B. Pereira, and E. Costa, “SGE: A structured representation for grammatical evolution,” in _Lecture Notes in Computer Science_. Springer International Publishing, 2016, pp. 136–148.
  * [15] J. Mégane, N. Lourenço, and P. Machado, “Probabilistic grammatical evolution,” in _Genetic Programming_ , T. Hu, N. Lourenço, and E. Medvet, Eds. Cham: Springer International Publishing, 2021, pp. 198–213.
  * [16] M. O’Neill, A. Brabazon, M. Nicolau, S. McGarraghy, and P. Keenan, “pigrammatical evolution,” in _Genetic and Evolutionary Computation – GECCO 2004_. Springer Berlin Heidelberg, 2004, pp. 617–629.
  * [17] C. Ryan, A. Azad, A. Sheahan, and M. O’Neill, “No coercion and no prohibition, a position independent encoding scheme for evolutionary algorithms – the chorus system,” in _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 2002, pp. 131–141.
  * [18] D. Fagan, M. Fenton, and M. O'Neill, “Exploring position independent initialisation in grammatical evolution,” in _2016 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, Jul. 2016.
  * [19] S. Luke, “Two fast tree-creation algorithms for genetic programming,” _IEEE Transactions on Evolutionary Computation_ , vol. 4, no. 3, pp. 274–283, 2000.
  * [20] E. Murphy, E. Hemberg, M. Nicolau, M. O’Neill, and A. Brabazon, “Grammar bias and initialisation in grammar based genetic programming,” in _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 2012, pp. 85–96.
  * [21] M. Nicolau, “Understanding grammatical evolution: initialisation,” _Genetic Programming and Evolvable Machines_ , vol. 18, no. 4, pp. 467–507, Jul. 2017.
  * [22] C. Ryan and R. M. A. Azad, “Sensible initialisation in grammatical evolution,” in _GECCO 2003: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference_ , A. M. Barry, Ed. Chigaco: AAAI, 11 July 2003, pp. 142–145.
  * [23] E. Medvet, “A comparative analysis of dynamic locality and redundancy in grammatical evolution,” in _Lecture Notes in Computer Science_. Springer International Publishing, 2017, pp. 326–342.
  * [24] N. Lourenço, F. B. Pereira, and E. Costa, “Unveiling the properties of structured grammatical evolution,” _Genetic Programming and Evolvable Machines_ , vol. 17, no. 3, pp. 251–289, Feb. 2016.
  * [25] N. Lourenço, F. Assunção, F. B. Pereira, E. Costa, and P. Machado, “Structured grammatical evolution: A dynamic approach,” in _Handbook of Grammatical Evolution_. Springer International Publishing, 2018, pp. 137–161.
  * [26] N. Lourenço, J. Ferrer, F. B. Pereira, and E. Costa, “A comparative study of different grammar-based genetic programming approaches,” in _Lecture Notes in Computer Science_. Springer International Publishing, 2017, pp. 311–325.
  * [27] M. O’Neill and A. Brabazon, “mGGA: The meta-grammar genetic algorithm,” in _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 2005, pp. 311–320.
  * [28] A. E. Eiben and J. E. Smith, “What is an evolutionary algorithm?” in _Natural Computing Series_. Springer Berlin Heidelberg, 2015, pp. 25–48.
  * [29] H. Beyer and H. Schwefel, “Evolution strategies – a comprehensive introduction,” _Natural Computing_ , vol. 1, pp. 3–52, 2004.
  * [30] R. Hinterding, “Gaussian mutation and self-adaption for numeric genetic algorithms,” in _Proceedings of 1995 IEEE International Conference on Evolutionary Computation_ , vol. 1, 1995, pp. 384–.
  * [31] J. McDermott, K. D. Jong, U. O'Reilly, D. R. White, S. Luke, L. Manzoni, M. Castelli, L. Vanneschi, W. Jaskowski, K. Krawiec, and R. Harper, “Genetic programming needs better benchmarks,” in _Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference - GECCO '12_. ACM Press, 2012.
  * [32] D. R. White, J. McDermott, M. Castelli, L. Manzoni, B. W. Goldman, G. Kronberger, W. Jaśkowski, U. O’Reilly, and S. Luke, “Better GP benchmarks: community survey results and proposals,” _Genetic Programming and Evolvable Machines_ , vol. 14, no. 1, pp. 3–29, Dec. 2012.
  * [33] D. Harrison and D. Rubinfeld, “Boston Housing Data,” http://lib.stat.cmu.edu/datasets/boston, 1993, [Online; accessed 27-December-2020].