# Co-evolutionary Probabilistic Structured Grammatical Evolution

Jessica Mégane<EMAIL_ADDRESS>0000-0001-6697-5423 University of
CoimbraCoimbraPolo II - Pinhal de MarrocosPortugal3030 ,  Nuno Lourenço
0000-0002-2154-0642<EMAIL_ADDRESS>University of CoimbraCoimbraPolo II -
Pinhal de MarrocosPortugal3030 and  Penousal Machado  0000-0002-6308-6484
<EMAIL_ADDRESS>University of CoimbraCoimbraPolo II - Pinhal de
MarrocosPortugal3030

(2022)

###### Abstract.

This work proposes an extension to Structured Grammatical Evolution (SGE)
called Co-evolutionary Probabilistic Structured Grammatical Evolution (Co-
PSGE). In Co-PSGE each individual in the population is composed by a grammar
and a genotype, which is a list of dynamic lists, each corresponding to a non-
terminal of the grammar containing real numbers that correspond to the
probability of choosing a derivation rule. Each individual uses its own
grammar to map the genotype into a program. During the evolutionary process,
both the grammar and the genotype are subject to variation operators.

The performance of the proposed approach is compared to 3 different methods,
namely, Grammatical Evolution (GE), Probabilistic Grammatical Evolution (PGE),
and SGE on four different benchmark problems. The results show the
effectiveness of the approach since Co-PSGE is able to outperform all the
methods with statistically significant differences in the majority of the
problems.

probabilistic algorithms, grammar-based, Gaussian mutation, co-evolution

††journalyear: 2022††copyright: acmlicensed††conference: Genetic and
Evolutionary Computation Conference; July 9–13, 2022; Boston, MA,
USA††booktitle: Genetic and Evolutionary Computation Conference (GECCO ’22),
July 9–13, 2022, Boston, MA, USA††price: 15.00††doi:
10.1145/3512290.3528833††isbn: 978-1-4503-9237-2/22/07††ccs: Computing
methodologies Heuristic function construction

##  1\. Introduction

Evolutionary Algorithms (EAs) is the name given to a set of stochastic search
procedures that are loosely inspired by the principles of natural selection
and genetics. These methods iteratively improve a set of candidate solutions,
usually referred to as the population, guided by a fitness function. The
improvement is obtained by selecting the most promising solutions (taking into
account the objective function), and applying some stochastic variations using
operators similar to mutations and recombinations that take place in
biological reproduction. Individuals with higher fitness are more likely to
survive and reproduce. The application of these elements is repeated for
several generations and it is expected that, over time, the quality of
individuals improves.

Grammars are used by many EAs to define the search space and impose
limitations on the solutions. The same syntax can be represented by an
infinite amount of grammars, so a good grammar design may impact on the
effectiveness of the optimization by converging to better solutions faster.
Context-Free Grammar Genetic Programming (CFG-GP) (Whigham and Science, 1995)
and Grammatical Evolution (GE) (O’Neill and Ryan, 2003; Ryan et al., 1998;
Ryan et al., 2018) are the most popular grammar-based Genetic Programming (GP)
algorithms. Both these methods use grammars to introduce syntactic
constraints, but the way individuals are represented differs. Individuals in
CFG-GP are derivation trees that start with the axiom of the grammar. In GE,
individuals have a genotype, which is a vector of integers, that with the help
of the Context-Free Grammar (CFG), is used to expand a derivation rule to form
the solution (i.e., phenotype).

GE has grown in popularity over time, although it does have some drawbacks,
such as low locality and high redundancy (Rothlauf and Goldberg, 2003;
Rothlauf and Oetzel, 2006). When several genotypes map to the same phenotype,
a representation is said to have high redundancy. Locality has to do with how
variations in the genotype cause phenotypic alterations. The best scenario,
i.e. high locality, would be such that a small change in the genotype would
result in a small change in the phenotype. Because of these two issues,
exploitation is often changed by exploration, behaving similarly as random
search in some problems (Whigham et al., 2015). However, some GE alternatives
have developed in the literature that have improved results by introducing
different mechanisms for representing individuals (O’Neill et al., 2004; Kim
and Ahn, 2015; Kim et al., 2016; Lourenço et al., 2016a, 2017; Ryan et al.,
2002; Mégane et al., 2021), population initialization (Nicolau, 2017; Ryan and
Azad, 2003; Fagan et al., 2016; Luke, 2000; Murphy et al., 2012) and grammar
design (Nicolau and Agapitos, 2018; Harper, 2010; Nicolau, 2004; O’Neill and
Ryan, 2004; O’Neill and Brabazon, 2005; Ali et al., 2021a).

In the literature it has been shown that adjusting the biases of the grammar
productions based on individuals in the population can improve the results
(Mégane et al., 2021; Kim et al., 2016), as can co-evolving the grammar with
the genetic code (O’Neill and Ryan, 2004). Due to the impact that grammars can
have on the quality and variability of the generated solutions, the goal of
this work was to create a method that evolves the probabilities of the
grammar, also introducing some randomness to prevent it from converging to
local optima solutions.

In this work we propose Co-evolutionary Probabilistic Structured Grammatical
Evolution (Co-PSGE), an extension of Structured Grammatical Evolution (SGE)
(Lourenço et al., 2016a, 2018), in which each individual is composed of its
genotype and a grammar. SGE is a method that besides presenting better
performance than GE, it also overcomes its issues, presenting high locality
and low redundancy (Lourenço et al., 2016b). The genotype of the Co-PSGE
individuals is a set of lists, one for each non-terminal of the grammar, and
each element of the list corresponds to the probability of choosing a
production rule of the respective non-terminal. The grammar of each individual
can be subject to variation operators, and at the end of each generation it is
used to update its phenotype.

The proposed method was compared with standard GE (O’Neill and Ryan, 2003;
Ryan et al., 1998; Ryan et al., 2018), Probabilistic Grammatical Evolution
(PGE) (Mégane et al., 2021) and SGE (Lourenço et al., 2016a, 2018) on four
different benchmark problems (McDermott et al., 2012). Statistical tests show
that Co-PSGE is better than GE, outperforming it with significant differences
on all problems. PGE was outperformed in three of the four problems analyzed,
while SGE was outperformed in two problems.

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

##  2\. Grammatical Evolution

GE (O’Neill and Ryan, 2003; Ryan et al., 1998; Ryan et al., 2018) is a
grammar-based EA in which individuals are represented as a list of integers.
The elements of the list (i.e., codons) are mapped creating the phenotype of
the individual (i.e., solution to the problem), using 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.

The genotype of individuals is a list of integer values (i.e., codons)
randomly generated in the interval $[0,255]$. The genotype-phenotype mapping
starts with the axiom of the grammar, and the expansion is always made from
the leftmost non-terminal. Each codon is mapped into a production rule by
applying the modulo operator ($mod$) between the codon and the number of
expansion options of the non-terminal to expand.

$\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 grammar.

Gen otype $\displaystyle{[}\text{54, 7, 83, 237, 71, 123, }$
$\displaystyle\text{67, 142, 25, 195, 202, 153}{]}$
$\displaystyle{<}\text{expr}{>}\rightarrow$
$\displaystyle\,{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle 54mod2=0$
$\displaystyle{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,{<}\text{var}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle 7mod2=1$
$\displaystyle{<}\text{var}{>}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{1.0}\,{<}\text{op}{>}{<}\text{expr}{>}$ $\displaystyle
83mod3=2$ $\displaystyle\text{1.0}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{1.0}\,\text{-}\,{<}\text{expr}{>}$ $\displaystyle
237mod4=1$ $\displaystyle\text{1.0}\,\text{-}\,{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{1.0}\,\text{-}\,{<}\text{var}{>}$ $\displaystyle
71mod2=1$ $\displaystyle\text{1.0}\,\text{-}\,{<}\text{var}{>}\rightarrow$
1.0-x $\displaystyle 123mod3=0$ Phenotype: $\displaystyle 1.0-x$

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

An example of this process is shown in Fig. 2, using the example of grammar
presented in Fig. 1. The mapping begins with $<$expr$>$, the grammar’s axiom,
which has two expansion alternatives, and the genotype’s first unused value,
$54$. Applying the mapping function, $54mod(2)=0$, we obtain the index of the
rule to be selected, $<$expr$><$op$><$expr$>$. This process is performed until
there are no more non-terminal symbols to expand or there are no more integers
to read from the genotype. In this last case and if we still have non-
terminals to expand, a wrapping mechanism can be used, where the genotype will
be re-used until it generates a valid individual or the predefined number of
wraps is over. If after all the wraps we still have not mapped all the non-
terminals, the mapping process stops, and the individual will be considered
invalid. The phenotype of each individual is evaluated with the fitness
function and then the population goes through the selection mechanisms.

###  2.1. Related Work

GE is one of the most used GP variants, and over the years it has been subject
of several improvements to address some of of its main criticisms, namely the
high redundancy and low locality. Both properties are related to the impact of
genetic operators on an individual’s phenotype, with low locality referring to
small genotype changes that make big changes in the phenotype, while high
redundancy means that there are many genotypes corresponding to the same
phenotype. The majority of these proposed solutions include changes to
grammars (Harper, 2010; Nicolau, 2004; Nicolau and Agapitos, 2018; O’Neill and
Ryan, 2004; O’Neill and Brabazon, 2005; Ali et al., 2021b), individual
representation (Kim and Ahn, 2015; Kim et al., 2016; Lourenço et al., 2018;
Mégane et al., 2021; O’Neill et al., 2004; Ryan et al., 2002), or population
initialization (Fagan et al., 2016; Luke, 2000; Murphy et al., 2012; Nicolau,
2017; Ryan and Azad, 2003).

SGE (Lourenço et al., 2018) is a recent proposal that tackles the locality and
redundancy issues of GE (Lourenço et al., 2016a), at the same time achieving
better performance results (Lourenço et al., 2017). In SGE the genotype is a
set of dynamic lists of ordered integers, with one list for each non-terminal
of the grammar. Each value in the list represents which production rule to
choose from the respective non-terminal. In (Lourenço et al., 2017) different
grammar-based GP approaches were compared, and the authors showed that SGE
achieved a good performance when compared with several grammar-based GP
representations.

Position Independent Grammatical Evolution ($\pi$GE) (O’Neill et al., 2004) is
a method that introduces a different representation and mapping mechanism, in
which the order of expansion of the non-terminals is determined by the
genotype of the individual, removing the positional dependency that exists in
GE. The genotype of the individuals is composed of two values (nont, rule),
where nont used to select the next non-terminal to be expanded, and rule
selects which rule to derive from that non-terminal. This method proved to be
better than GE on several problems, showing statistical differences (Fagan et
al., 2010).

Chorus (Ryan et al., 2002) is another method in which there is positional
independence, with each gene specifically encoding one production of the
grammar. However, this approach has not been shown to be better 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 so the choice of grammar
can influence the speed of convergence to the best solution (Nicolau and
Agapitos, 2018). Some studies have been conducted to analyze the performance
of GE with different types of grammars, such as the use of recursively
balanced grammars (Harper, 2010; Nicolau and Agapitos, 2018) and the reduction
of non-terminal symbols (Nicolau, 2004; Nicolau and Agapitos, 2018).

Harper et al. (Harper, 2010) showed that the grammar chosen at the beginning
of the evolutionary process can have a large impact on the solutions, such as
generating many invalid individuals when using recursive grammars. It has also
been shown that there is more variety in the size of solutions when using a
balanced grammar.

Nicolau et al. (Nicolau and Agapitos, 2018) tested GE using different types of
grammars, which included, balanced grammars, grammars with corrected biases,
and grammars with unlinked productions. The tests using recursively balanced
grammars, in which for every recursive production there is a non-recursive
one, showed improved results over the original grammar. However it resulted in
a larger number of individuals consisting of a non-terminal symbol. Nicolau
(Nicolau, 2004) proposed a method to reduce the number of non-terminal
symbols, replacing them by their productions, which despite showing a slight
increase in performance, it has the disadvantage of generating very complex
grammars that are difficult to read.

Another line of study has been the evolution of grammar during the
evolutionary process (O’Neill and Ryan, 2004; Mégane et al., 2021; Kim and
Ahn, 2015; Kim et al., 2016; Ali et al., 2021a).

Grammatical Evolution by Grammatical Evolution ((GE)2) (O’Neill and Ryan,
2004) is an approach in which there is co-evolution of grammar and genetic
code. The method uses two distinct grammars, the universal grammar and the
solution grammar. The universal grammar dictates the structure of the solution
grammar, that is used to map the individuals. This method has shown to be
effective in evolving biases towards some non-terminal symbols. Later, was
implemented into a new algorithm, meta-Grammar Genetic Algorithm (mGGA)
(O’Neill and Brabazon, 2005), which obtained performance improvements.

Automatic Grammatical Evolution (AutoGE) (Ali et al., 2021a) is a tool
designed to help define the structure of the grammar and fitness function to
be used by GE. This tool introduces a Production Rule Pruning (PRP) algorithm,
which assigns ranks to productions to detect the least valuable ones. This
strategy was tested on real-world symbolic regression problems (Ali et al.,
2021b), and obtained significant performance improvements in 3 of the 10
problems analyzed. Although in all problems there were improvements in
genotype size, these were significant in 7 of the 10 problems.

PGE (Mégane et al., 2021) is a recent variant of GE, in which a Probabilistic
Context-Free Grammar (PCFG) is used to map the individuals 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 is done from the leftmost non-terminal, and for
each non-terminal to be expanded, the rule whose probability interval includes
the codon is selected. At the end of each generation, the PCFG probabilities
are updated 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 better than GE with statistical differences in the two problems
analysed.

Kim et al. (Kim and Ahn, 2015) have proposed a Probabilistic Model Building
Grammatical Evolution (PMBGE) in which the mapping uses a PCFG to the
probabilistic technique Estimation Distribution Algorithm (EDA), which also
replaces the mutation and crossover operators. This technique at each
generation generates a new population from the new grammar, whose
probabilities are generated based on the frequency of the rules expanded by
the best individuals. The proposed approach had a similar performance when
compared with GE. Later, Kim et al. (Kim et al., 2016) adapted Conditional
Dependency Tree (CDT) to the mechanism of updating the grammar, in which
dependencies between production rules are considered. This method outperformed
GE with statistical differences in two of the four problems analysed. The
major distinction between these two methods and PGE (Mégane et al., 2021) is
in the method of adjusting the probabilities of the grammar over the
evolutionary process and that PGE considers the genetic operators while the
two other methods uses EDA.

The main difference between these two methods and PGE (Mégane et al., 2021) is
in the mechanism of altering the grammar’s probability over the evolutionary
process, as well as the fact that PGE considers genetic operators, whilst the
other two methods employ EDA.

##  3\. Co-Evolutionary Probabilistic Structured Grammatical Evolution

In this paper we propose Co-PSGE 111The implementation of Co-PSGE is available
at: https://github.com/jessicamegane/co-psge, an extension to SGE that adapts
its representation and mapping mechanism to use a PCFG, which, like the
individuals in the population, can be subject to variation operators.

Each individual in the population is composed of a grammar and its genotype,
which is a set of dynamical lists, each list being associated with a non-
terminal of the grammar. Each list contains an ordered sequence of real
numbers, bounded to the interval [0, 1], that corresponds to the probability
of selecting a derivation rule. Each individual uses its own grammar to map
the genotype into a program. During the evolutionary process both the grammar
and the genotype are subject to variation operators. At the end of each
generation, the phenotype is updated using the new genotype and its updated
grammar.

At initialisation, a genotype is generated for each individual as well as a
PCFG. The grammar assigned to the individual at initialization has the same
probability for each production rule of each non-terminal. Individuals are
initialized recursively, with a codon generated randomly and added to the
genotype list of the non-terminal that is being expanded at each iteration
(Alg. 1, lines 2-3). The genotype (which starts empty for each non-terminal),
the non-terminal symbol to expand (in the first iteration, the axiom of the
grammar), the current depth (which starts at 0), the maximum depth limit and
the individual’s grammar are all given as parameters to the algorithm. The
function simulates the mapping process, which will be described in detail
further on (Alg. 1, line 4) to determine which non-terminals should be
expanded next. When all non-terminals symbols have been expanded (i.e., only
terminals remain) the algorithm terminates with a valid individual.

Algorithm 1 Random Candidate Solution Generation of Co-PSGE

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

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

3: genotype[symb].append(codon)

4: selected_rule = $generate\\_expansion$(symb, codon, pcfg, current_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, sym, current_depth + 1, max_depth, pcfg)

9: end if

10: end for

11:end procedure

The genotype-phenotype mapping process is presented in Alg. 2. The algorithm
receives as arguments the genotype, a counter called $positions\\_to\\_map$
(which is used to store the genotype position of each non-terminal list at the
current iteration, initialized with 0 for each non-terminal), the symbol to
expand (starts in the axiom), the current depth, the maximum depth limit and
the grammar. If, during mapping, more codons are needed to create a valid
individual, they will be randomly generated and added to the genotype (Alg. 2,
lines 3-6). The dynamic genotype is one of the advantages of the
representation proposed by SGE (Lourenço et al., 2018). With the depth limit,
it is possible to add productions whenever necessary, without the risk of
bloat (a considerable growth in the size of the solutions (Eiben and Smith,
2015)), always creating valid individuals.

Algorithm 2 Genotype-Phenotype Mapping Function of Co-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

The process of choosing a derivation rule from a codon of the genotype using a
PCFG is similar to that proposed by PGE (Mégane et al., 2021) (Alg. 3, lines
15-21), except that there is a distinction when the maximum depth limit is
exceeded, in which only non-recursive productions can be chosen (Alg. 3, lines
4-13). The function receives as parameters the non-terminal symbol to be
expanded, the codon, the grammar, the current depth and the maximum depth
established.

When the defined maximum tree depth limit is exceeded (Alg. 3, lines 4-13),
the algorithm considers only non-recursive rules, and adjusts the
probabilities of each of them, so that the sum is 1. To accomplish this, we
first sum the value of the current probabilities of the non-recursive rules,
which is used to perform the adjustment. Using the new probabilities, the
production rule is chosen with the normal procedure: It is verified whether
the codon belongs to the probability range of each production rule of the non-
terminal to be expanded and when this condition is verified, the rule is
chosen.

Algorithm 3 Co-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 $>=$ 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

The mapping process in Co-PSGE is illustrated in Fig. 4, using the PCFG shown
on Fig. 3. The mapping begins with the grammar’s axiom, $<$expr$>$ and the
first entry in the genotype’s respective list, $0.29$. The probabilities of
the rules of the non-terminal are compared to the value of the codon. In this
scenario, we have two equally probable possibilities. The non-terminal will be
expanded to $<$expr$><$op$><$exp$>$ because $0.29$ falls within the range of
probabilities of the initial production.

The next non-terminal to expand, according to the leftmost derivation rule, is
$<$expr$>$. The process is repeated, this time with the codon 0.73, which
corresponds to the second derivation rule, $<$var$>$. This non-terminal is the
next to be expanded, and it has three derivation rules. $0.41$ is the first
codon available in the list of the non-terminal $<$var$>$. The codon falls
within the range of the second rule, $y$, when we look at the probabilities of
the derivation rules. The procedure is repeated until a valid individual is
formed.

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

Figure 3. PCFG example.

Genot ype
$\displaystyle\framebox[79.6678pt]{$<expr>$}\framebox[56.9055pt]{$<op>$}$
$\displaystyle\framebox[71.13188pt]{$<var>$}$ [0.29,0.73,0.52][0.86] [0.41,
0.15] $\displaystyle{<}\text{expr}{>}\rightarrow$
$\displaystyle\,{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle(0.29)$
$\displaystyle{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,{<}\text{var}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle(0.73)$
$\displaystyle{<}\text{var}{>}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{y}\,{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle(0.41)$
$\displaystyle\text{y}{<}\text{op}{>}{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{y}\,\text{/}\,{<}\text{expr}{>}$ $\displaystyle(0.86)$
$\displaystyle\text{y}\,\text{/}\,{<}\text{expr}{>}\rightarrow$
$\displaystyle\,\text{y}\,\text{/}\,{<}\text{var}{>}$ $\displaystyle(0.52)$
$\displaystyle\text{y}\,\text{/}\,{<}\text{var}{>}\rightarrow$ y/x
$\displaystyle(0.15)$ Phenotype: $\displaystyle y/x$

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

At the end of each generation the PCFG of each individual is itself subject to
variation through mutations on its probabilities. This process is demonstrated
in Alg. 4. The algorithm takes as parameters the individual whose grammar is
to be mutated, the probability of mutation occurring (between 0 and 1) and the
float corresponding to the standard deviation to use in a normal destribution.
The mutation probability is used to check for each non-terminal production
rule whether mutation should occur (Alg. 4, line 5). When a production is
selected for mutation, a generated value is added to it with a Gaussian
distribution of mean 0 and the standard deviation previously defined, keeping
the new value in the range [0,1] (Alg. 4, lines 6-8). Gaussian mutations have
been widely used in the literature and have showed to be a good approach to
make small changes in the search space (Bäck et al., 1997; Hinterding, 1995;
Beyer and Schwefel, 2004). In this method only one mutation can occur per non-
terminal, so after a production is mutated, the probabilities of the remaining
productions of the respective non-terminal are updated until their sum equals
1, and can only be changed again in the next generation (Alg. 4, line 9). The
grammar of the parent with the best fitness is passed on to the offspring
during crossover. The individual’s phenotype is updated at the end of each
generation using the new grammar and genotype.

Algorithm 4 Co-PSGE algorithm to mutate PCFG’s probabilities.

1:procedure mutateGrammar(individual, prob_mutation, sd_normal_dist)

2: $grammar=individual.getGrammar()$

3: for NT, prods in grammar do

4: for each production rule i of prods do

5: if $random()<$ prob_mutation then

6: value = $random\\_Gaussian$(0, sd_normal_dist)

7: $prob_{i}=min(prob_{i}$ \+ value, 1.0)

8: $prob_{i}=max(prob_{i}$, 0.0)

9: adjust_probabilities(prods)

10: break

11: end if

12: end for

13: end for

14:end procedure

$\displaystyle{<}\text{expr}{>}::=$
$\displaystyle\,{<}\text{expr}{>}{<}\text{op}{>}{<}\text{expr}{>}$
$\displaystyle(0.73)$ $\displaystyle|\,{<}\text{var}{>}$ (0.27)
$\displaystyle{<}\text{op}{>}::=$ $\displaystyle\,+\,$ $\displaystyle(0.25)$
$\displaystyle|\,-$ $\displaystyle(0.25)$ $\displaystyle|\,*$
$\displaystyle(0.25)$ $\displaystyle|\,/$ $\displaystyle(0.25)$
$\displaystyle{<}\text{var}{>}::=$ x (0.45) $\displaystyle|\,\text{y}$
$\displaystyle(0.27)$ $\displaystyle|\,\text{1.0}$ $\displaystyle(0.27)$

Figure 5. PCFG grammar after mutation.

Fig. 5 shows an example of the grammar of Fig. 3 after suffering a mutation.
Assuming that the non-terminal $<expr>$ production rule $<var>$ has been
randomly selected to be mutated, and that the random number generator of a
Gaussian distribution of mean 0 and standard deviation 0.50 ($N(0,0.50)$) has
generated the number $-0.23$, the new probability of that production becomes
0.27 ($0.50-0.23$). The probability of the other production of the non-
terminal $<expr>$ is adjusted to 0.73. As a maximum of one mutation can occur
in one production of each non-terminal, other mutations can occur in other
non-terminals, for example, if the production rule $x$ of the non-terminal
$<var>$ suffers a mutation of $+0.12$, it will have a value of 0.45, and the
remaining outputs need to be adjusted, having a probability of 0.27.

###  3.1. Variation Operators

Mutation and crossover are two genetic operators that can be used to change
individuals. The mutation operator modifies randomly chosen codons. The codons
are subjected to a Gaussian mutation, with the resultant value falling within
the range [0,1].

Genotype before mutation: $<expr>$$<op>$$<var>$
[0.29, 0.73, 0.52][0.86][0.41, 0.15]

Genotype after mutation: $<expr>$$<op>$$<var>$
[0.29, 0.73, 0.52][0.86][0.64, 0.15]

Figure 6. Example of Co-PSGE’s mutation on one codon of the genotype.

Fig. 6 shows an example of Gaussian mutation in an individual. Assuming that
randomly only the first codon in the list of the non-terminal $<$var$>$ was
selected for mutation and that the value generated with a Gaussian
distribution of mean 0 and standard deviation 0.50 ($N(0,0.50)$) was $0.23$,
the codon will be changed to $0.64$ ($0.41+0.23$).

The crossover operator is the same as the SGE’s and uses two parents to
generate the offspring. A binary mask of the size of the number of lists of
the genotype (the same number of non-terminals of the grammar) is randomly
generated and the genotype of the offspring is created according to the values
of the mask.

Fig. 7 shows an example of a crossover between two individuals, generating one
offspring and the randomly generated mask for the procedure. In the example
shown, the descendant inherits the non-terminal $<$expr$>$ list from the
second parent, and the remaining ones from the first. In case two descendants
are generated, the other would get the opposite lists.

Parents genotype:
Parent 1:
$<expr>$$<op>$$<var>$
[0.29, 0.73, 0.52][0.86][0.41, 0.15]

Parent 2:
$<expr>$$<op>$$<var>$
[0.16,0.71,0.48][0.23][0.19,0.86,0.56]

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

Offspring:
$<expr>$$<op>$$<var>$
[0.29, 0.73, 0.52][0.23][0.41, 0.15]

Figure 7. Example of Co-PSGE’s crossover between two individuals, generating
one offspring.

##  4\. Experimental Setup

The performance of Co-PSGE will be compared with the results of GE (O’Neill
and Ryan, 2003; Ryan et al., 1998; Ryan et al., 2018), PGE (Mégane et al.,
2021) and SGE (Lourenço et al., 2016a, 2018), analyzing the evolution of the
mean best fitness in 100 independent runs. The framework of Whigham et al.
(Whigham et al., 2015) is followed, and four problems of different scopes are
considered taking into account the recommendations of McDermott et al.
(McDermott et al., 2012). Table 1 presents the parameters used by all the
approaches.

Regarding the GE and PGE variation operators, one-point crossover is used. The
GE mutation replaces the selected codons with new ones randomly generated on
the interval [0, 255] and in the case of PGE a float mutation is used in which
the codons are replaced with new ones generated on the interval [0, 1].
Neither of these methods uses a wrap mechanism. Regarding the operators used
by SGE and Co-PSGE, these methods use the same crossover, which is the SGE
crossover (Lourenço et al., 2018). The mutation operator, in the case of SGE,
replaces the selected codon with another valid option, that is, the index of
another production of the same non-terminal, and in the case of Co-PSGE a
Gaussian mutation is performed with N(0, 0.5) on the value of the selected
codon, keeping the new value in the range [0, 1].

Additionally, in PGE a learning factor of 1% was used, and in Co-PSGE a 5%
probability of a mutation occur in each non-terminal of the grammar, with a
random value drawn from a $N(0,0.50)$.

Table 1. Parameters used in the experimental analysis for GE, PGE, SGE and Co-
PSGE.

| GE | PGE | SGE | Co-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

The fitness functions used to evaluate the individuals were designed with the
objective of minimizing 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. All the problems are detailed bellow as well as the
grammars used.

###  4.1. Symbolic Regression

Popular benchmark problem for testing GP algorithms, with the objective of
finding the mathematical expression that best fits a given dataset. The Pagie
polynomial was selected as it is a challenging symbolic regression problem
(Pagie and Hogeweg, 1997), that has the following mathematical expression:

(1) $\frac{1}{1+x[1]^{-4}}+\frac{1}{1+x[2]^{-4}}.$

The function is sampled with x[1], x[2] $\in$ [-5, 5] with a step of 0.4. The
solutions are generated using the following grammar:

¡start¿ ::= ¡expr¿

¡expr¿ ::= ¡expr¿ ¡op¿ ¡expr¿ — ( ¡expr¿ ¡op¿ ¡expr¿ ) ¡pre_op¿ ( ¡expr¿ ) —
¡var¿

¡op¿ ::= + — - — * — /

¡pre_op¿ ::= sin — cos — exp — log — inv

¡var¿ ::= x[..] — 1.0

where $inv=\frac{1}{f(x)}$. The division and logarithm functions are
protected, i.e., $1/0=1$ and $log(f(x))=0$ $iff(x)\leq 0$.

###  4.2. Boston Housing

This is a famous Machine Learning problem to predict the prices of Boston
Houses. The dataset comes from the StatLib Library (Harrison and Rubinfeld,
1993) and has 506 entries, with 13 features. It was divided in 90% for
training and 10% for testing. The grammar used for the Boston Housing
regression problem is the same as the Symbolic Regression (Section 4.1).

###  4.3. 5-bit Even Parity

The objective of this problem is to evolve a boolean function that takes as
input a binary string with length 5, and returns 0 if the string is even or 1
if it is odd. Considering $b0$, $b1$, $b2$, $b3$, and $b4$ the input bits, the
following grammar is used:

¡start¿ ::= ¡B¿

¡B¿ ::= ¡B¿ and ¡B¿ — ¡B¿ or ¡B¿ not (¡B¿ and ¡B¿) — not (¡B¿ or ¡B¿) ¡var¿

¡var¿ ::= b0 — b1 — b2 — b3 — b4

###  4.4. 11-bit Boolean Multiplexer

The aim of the 11-bit Multiplexer is to decode a 3-bit binary address and
return the value of the corresponding data register ($d0$ to $d7$). The
function receives as input three addresses ($s0$ to $s2$) and eight data
registers ($i0$ to $i7$). For this problem we used:

¡start¿ ::= ¡B¿

¡B¿ ::= ¡B¿ and ¡B¿ — ¡B¿ or ¡B¿ — not ¡B¿ ¡B¿ if ¡B¿ else ¡B¿ — ¡var¿

¡var¿ ::= s0 — s1 — s2 — i0 — i1 — i3 — i4— i5 — i6 — i7

##  5\. Results

To be able to support our study and compare the different approaches, a
statistical analysis was conducted. Since the populations were independently
initialized and the results do not meet the criteria for the parametric tests,
the Kruskal-Wallis non-parametric test was employed to check for meaningful
differences between the different methods. When this happened the Mann-Whitney
post-hoc test with Bonferroni correction was performed to verify in which
pairs the differences exist, with a level of significance of $\alpha=0.05$.
Table 2 shows the statistical results, and values in bold indicate that Co-
PSGE outperforms the other approaches with statistical differences.

Table 2. 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 Co-PSGE is statistically better than GE, PGE or
SGE.

Problems | GE | PGE | SGE
---|---|---|---
Pagie Polynomial | 0.003 | 0.023 | 0.155
Boston Housing Train | 0.000 | 0.000 | 0.223
Boston Housing Test | 0.000 | 0.045 | 0.000
5-bit Even Parity | 0.000 | 0.000 | 0.000
11-bit Multiplexer | 0.000 | 0.000 | 0.000

Additionally, the effect size $r$ was calculated in order to determine how
significant the differences are, and shown in Table 3. The following notation
was used: ”~” was used when there are no significant differences between
samples, the ”+” sign was used when the effect size is small ($r<=0.3$), ”++”
was used when the effect size is medium ($0.3<r<=0.5$), and ”+++” was used
when the effect size is large ($r>0.5$).

Table 3. Effect size between Co-PSGE and GE, PGE and SGE.

Problems | GE | PGE | SGE
---|---|---|---
Pagie Polynomial | + | - | ~
Boston Housing Train | +++ | ++ | ~
Boston Housing Test | +++ | + | ++
5-bit Even Parity | +++ | +++ | +++
11-bit Multiplexer | +++ | +++ | \- - -

The evolution of the mean best fitness over the 50 generations for the
symbolic regression problem is represented in Fig. 8. In this method PGE
stands out by finishing with better fitness. These results are in line with
what was observed in the work of Mégane et al. (Mégane et al., 2021), in which
PGE presented no statistical differences when compared with SGE. We see that
although they all start with approximately the same fitness, PGE takes a few
generations to keep up with the faster decrease of Co-PSGE and SGE, however,
it outperforms them after 20 and 30 generations, respectively. Co-PSGE is
significantly different from PGE on this problem, with a small effect size.
Comparing the performance of Co-PSGE with that of GE, we see that Co-PSGE
shows better results, presenting statistically significant differences with a
large effect size. Compared to SGE we see that there are no significant
differences between the methods.

Figure 8. Performance results for the Pagie polynomial. Results are the mean
best fitness of 100 runs. Figure 9. Testing results for the Boston Boston
Housing problem. Results are the mean best fitness of 100 runs.

The results in Fig. 9 show the evolution of mean best fitness for the Boston
Housing test data. For this problem we can see that the best performing method
is Co-PSGE, having a steeper decrease than the other approaches. Looking at
the statistical test results in Table 2 and effect size in Table 3, we can see
that Co-PSGE is statistically better than all methods, showing a large effect
size relative to GE, a small effect size relative to PGE, and a medium effect
size relative to SGE. The training data is interesting to analyze, since in
training SGE and Co-PSGE do not show significant differences, however in
testing they do exist with a medium effect size, which shows that Co-PSGE
creates a more generalized model for the unseen 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 in Fig. 10 for the 5-bit parity problem, we observe
that SGE and Co-PSGE start the evolutionary process with better average
fitness when compared to GE and PGE. However, the decrease slope of Co-PSGE is
much steeper, distancing itself quickly from the curve of SGE, and in a few
generations it manages to reach a better error more than twice as much as the
other approaches. Co-PSGE shows significant differences from all methods, with
a large effect size. Analyzing the performance of GE and PGE, we see that PGE
has a more pronounced decrease, however in the analyzed generations it does
not reach the behavior of SGE. An analysis was performed on the average
probability of the grammars of the best individuals in each generation of all
the runs, and we observed that the probability of the NOR production rule ends
with probability greater than 90%. Since this is a universal gate, through it
we can reach the remaining productions and consequently the best solution.

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

The results for the 11-bit multiplexer are shown in Fig. 11. We see that GE
and PGE start with worse fitness compared to SGE and Co-PSGE, and maintain
throughout the evolutionary process, with Co-PSGE showing statistically
significant differences with a large effect size for both methods. Although
they start with the same fitness, SGE has a larger decrement, which makes it
statistically different on this problem compared to Co-PSGE.

##  6\. Conclusion

In this paper we proposed Co-PSGE, a method that adapts the representation and
mapping of SGE by assigning each individual a grammar that, like the
individual, is subjected to variation operators. The genotype is a list of
dynamic lists, each of which corresponds to a non-terminal of the grammar and
contains real numbers, which correspond to the probability of choosing a
derivation rule.

The proposed method was compared with standard GE, PGE and SGE on four
different benchmark problems. Statistical tests showed that Co-PSGE is better
than GE, outperforming it with significant differences on all problems. PGE
was outperformed in three of the four problems analyzed, while SGE was
outperformed in two problems. The co-evolution of the grammar with the
genotype of the individuals allowed guiding the evolutionary process to better
solutions faster, as shown by the performance analysis, supporting the work
presented by O’Neill et al. (O’Neill and Ryan, 2004). Further experimentation
will be necessary to gain more insight into the advantages of the proposed
method.

As future work it will be interesting to study different metrics, such as
locality and redundancy of Co-PSGE, in order to be able to analyze the impact
that mutated grammars have on the representation of individuals and compare it
with the results of GE and SGE. Another line of work will be to analyze the
evolution of the grammars by initializing them with different probabilities
for each individual, but also test different grammars, following the work of
Nicolau et al. (Nicolau and Agapitos, 2018). It would also be interesting to
test problems from different scopes, including multi-optimization problems.

###### Acknowledgements.

This work is funded by national funds through the FCT - Foundation for Science
and Technology, I.P., within the scope of the project 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.

## References

  * (1)
  * Ali et al. (2021a) M. S. Ali, M. Kshirsagar, E. Naredo, and C. Ryan. 2021a.  AutoGE: A Tool for Estimation of Grammatical Evolution Models.. In _ICAART (2)_. 1274–1281.
  * Ali et al. (2021b) M. S. Ali, M. Kshirsagar, E. Naredo, and C. Ryan. 2021b.  Towards Automatic Grammatical Evolution for Real-world Symbolic Regression.  (2021).
  * Beyer and Schwefel (2004) H. Beyer and H. Schwefel. 2004.  Evolution strategies – A comprehensive introduction.  _Natural Computing_ 1 (2004), 3–52.
  * Bäck et al. (1997) T. Bäck, G. Rudolph, and H. Schwefel. 1997.  Evolutionary Programming and Evolution Strategies: Similarities and Differences. In _In Proceedings of the Second Annual Conference on Evolutionary Programming_. 11–22.
  * Eiben and Smith (2015) A. E. Eiben and J. E. Smith. 2015.  What Is an Evolutionary Algorithm?  In _Natural Computing Series_. Springer Berlin Heidelberg, 25–48.  https://doi.org/10.1007/978-3-662-44874-8_3
  * Fagan et al. (2016) D. Fagan, M. Fenton, and M. O'Neill. 2016\.  Exploring position independent initialisation in grammatical evolution. In _2016 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, 5060–5067.  https://doi.org/10.1109/cec.2016.7748331
  * Fagan et al. (2010) D. Fagan, M. O’Neill, E. Galván-López, A. Brabazon, and S. McGarraghy. 2010.  An Analysis of Genotype-Phenotype Maps in Grammatical Evolution.  In _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 62–73.  https://doi.org/10.1007/978-3-642-12148-7_6
  * Harper (2010) R. Harper. 2010\.  GE, explosive grammars and the lasting legacy of bad initialisation. In _IEEE Congress on Evolutionary Computation_. IEEE.  https://doi.org/10.1109/cec.2010.5586336
  * Harrison and Rubinfeld (1993) D. Harrison and D. Rubinfeld. 1993.  Boston Housing Data.  http://lib.stat.cmu.edu/datasets/boston.  [Online; accessed 27-December-2020].
  * Hinterding (1995) R. Hinterding. 1995\.  Gaussian mutation and self-adaption for numeric genetic algorithms. In _Proceedings of 1995 IEEE International Conference on Evolutionary Computation_ , Vol. 1. 384–.  https://doi.org/10.1109/ICEC.1995.489178
  * Kim and Ahn (2015) H. Kim and C. W. Ahn. 2015\.  A New Grammatical Evolution Based on Probabilistic Context-free Grammar.  In _Proceedings in Adaptation, Learning and Optimization_. Springer International Publishing, 1–12.  https://doi.org/10.1007/978-3-319-13356-0_1
  * Kim et al. (2016) H. Kim, H. Kang, and C. W. Ahn. 2016.  A Conditional Dependency Based Probabilistic Model Building Grammatical Evolution.  _IEICE Transactions on Information and Systems_ E99.D, 7 (2016), 1937–1940.  https://doi.org/10.1587/transinf.2016edl8004
  * Lourenço et al. (2018) N. Lourenço, F. Assunção, F. B. Pereira, E. Costa, and P. Machado. 2018.  Structured Grammatical Evolution: A Dynamic Approach.  In _Handbook of Grammatical Evolution_. Springer International Publishing, 137–161.  https://doi.org/10.1007/978-3-319-78717-6_6
  * Lourenço et al. (2017) N. Lourenço, J. Ferrer, F. B. Pereira, and E. Costa. 2017\.  A Comparative Study of Different Grammar-Based Genetic Programming Approaches.  In _Lecture Notes in Computer Science_. Springer International Publishing, 311–325.  https://doi.org/10.1007/978-3-319-55696-3_20
  * Lourenço et al. (2016a) N. Lourenço, F. B. Pereira, and E. Costa. 2016a.  SGE: A Structured Representation for Grammatical Evolution.  In _Lecture Notes in Computer Science_. Springer International Publishing, 136–148.  https://doi.org/10.1007/978-3-319-31471-6_11
  * Lourenço et al. (2016b) N. Lourenço, F. B. Pereira, and E. Costa. 2016b.  Unveiling the properties of structured grammatical evolution.  _Genetic Programming and Evolvable Machines_ 17, 3 (Feb. 2016), 251–289.  https://doi.org/10.1007/s10710-015-9262-4
  * Luke (2000) S. Luke. 2000.  Two fast tree-creation algorithms for genetic programming.  _IEEE Transactions on Evolutionary Computation_ 4, 3 (2000), 274–283.  https://doi.org/10.1109/4235.873237
  * McDermott et al. (2012) J. McDermott, D. R. White, S. Luke, L. Manzoni, M. Castelli, L. Vanneschi, W. Jaskowski, K. Krawiec, R. Harper, K. De Jong, and U. O’Reilly. 2012.  Genetic Programming Needs Better Benchmarks. In _Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation_ (Philadelphia, Pennsylvania, USA) _(GECCO ’12)_. Association for Computing Machinery, New York, NY, USA, 791–798.  https://doi.org/10.1145/2330163.2330273
  * Mégane et al. (2021) J. Mégane, N. Lourenço, and P. Machado. 2021\.  Probabilistic Grammatical Evolution. In _Genetic Programming_ , Ting Hu, Nuno Lourenço, and Eric Medvet (Eds.). Springer International Publishing, Cham, 198–213.
  * Murphy et al. (2012) E. Murphy, E. Hemberg, M. Nicolau, M. O’Neill, and A. Brabazon. 2012.  Grammar Bias and Initialisation in Grammar Based Genetic Programming.  In _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 85–96.  https://doi.org/10.1007/978-3-642-29139-5_8
  * Nicolau (2004) M. Nicolau. 2004\.  Automatic Grammar Complexity Reduction in Grammatical Evolution.  (2004).
  * Nicolau (2017) M. Nicolau. 2017\.  Understanding grammatical evolution: initialisation.  _Genetic Programming and Evolvable Machines_ 18, 4 (July 2017), 467–507.  https://doi.org/10.1007/s10710-017-9309-9
  * Nicolau and Agapitos (2018) M. Nicolau and A. Agapitos. 2018.  Understanding Grammatical Evolution: Grammar Design.  In _Handbook of Grammatical Evolution_. Springer International Publishing, 23–53.  https://doi.org/10.1007/978-3-319-78717-6_2
  * O’Neill and Brabazon (2005) M. O’Neill and A. Brabazon. 2005.  mGGA: The meta-Grammar Genetic Algorithm.  In _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 311–320.  https://doi.org/10.1007/978-3-540-31989-4_28
  * O’Neill et al. (2004) M. O’Neill, A. Brabazon, M. Nicolau, S. McGarraghy, and P. Keenan. 2004.  $\uppi$Grammatical Evolution.  In _Genetic and Evolutionary Computation – GECCO 2004_. Springer Berlin Heidelberg, 617–629.  https://doi.org/10.1007/978-3-540-24855-2_70
  * O’Neill and Ryan (2003) M. O’Neill and C. Ryan. 2003.  _Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language_.  Springer US.  https://doi.org/10.1007/978-1-4615-0447-4
  * O’Neill and Ryan (2004) M. O’Neill and C. Ryan. 2004.  Grammatical Evolution by Grammatical Evolution: The Evolution of Grammar and Genetic Code.  In _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 138–149.  https://doi.org/10.1007/978-3-540-24650-3_13
  * Pagie and Hogeweg (1997) L. Pagie and P. Hogeweg. 1997.  Evolutionary Consequences of Coevolving Targets.  _Evolutionary Computation_ 5, 4 (12 1997), 401–418.  https://doi.org/10.1162/evco.1997.5.4.401 arXiv:https://direct.mit.edu/evco/article-pdf/5/4/401/1366039/evco.1997.5.4.401.pdf
  * Rothlauf and Goldberg (2003) F. Rothlauf and D. E. Goldberg. 2003.  Redundant Representations in Evolutionary Computation.  _Evolutionary Computation_ 11, 4 (Dec. 2003), 381–415.  https://doi.org/10.1162/106365603322519288
  * Rothlauf and Oetzel (2006) F. Rothlauf and M. Oetzel. 2006.  On the Locality of Grammatical Evolution.  In _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 320–330.  https://doi.org/10.1007/11729976_29
  * Ryan et al. (2002) C. Ryan, A. Azad, A. Sheahan, and M. O’Neill. 2002\.  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, 131–141.  https://doi.org/10.1007/3-540-45984-7_13
  * Ryan and Azad (2003) C. Ryan and R. M. A. Azad. 2003.  Sensible Initialisation in Grammatical Evolution. In _GECCO 2003: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference_ , Alwyn M. Barry (Ed.). AAAI, Chigaco, 142–145.
  * Ryan et al. (1998) C. Ryan, J.J. Collins, and M. O Neill. 1998.  Grammatical evolution: Evolving programs for an arbitrary language.  In _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 83–96.  https://doi.org/10.1007/bfb0055930
  * Ryan et al. (2018) C. Ryan, M. O'Neill, and J.J. Collins (Eds.). 2018\.  _Handbook of Grammatical Evolution_.  Springer International Publishing.  https://doi.org/10.1007/978-3-319-78717-6
  * Whigham et al. (2015) P. A. Whigham, G. Dick, J. Maclaurin, and C. A. Owen. 2015\.  Examining the ”Best of Both Worlds” of Grammatical Evolution. In _Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation_ (Madrid, Spain) _(GECCO ’15)_. Association for Computing Machinery, New York, NY, USA, 1111–1118.  https://doi.org/10.1145/2739480.2754784
  * Whigham and Science (1995) P. A. Whigham and Department Of Computer Science. 1995\.  Grammatically-based Genetic Programming.