# Improving Model-based Genetic Programming for Symbolic Regression of Small
Expressions

M. Virgolin<EMAIL_ADDRESS>
Life Science and Health group, Centrum Wiskunde & Informatica, Amsterdam, 1098
XG, the Netherlands. T. Alderliesten<EMAIL_ADDRESS>
Department of Radiation Oncology, Amsterdam UMC, University of Amsterdam,
Amsterdam, 1105 AZ, the Netherlands.
Department of Radiation Oncology, Leiden University Medical Center, Leiden,
2333 ZA, the Netherlands. C. Witteveen<EMAIL_ADDRESS>
Algorithmics Group, Delft University of Technology, Delft, 2628 XE, the
Netherlands. P. A. N. Bosman<EMAIL_ADDRESS>
Life Science and Health group, Centrum Wiskunde & Informatica, Amsterdam, 1098
XG, the Netherlands.
Algorithmics Group, Delft University of Technology, Delft, 2628 XE, the
Netherlands

###### Abstract

The Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) is a model-based
EA framework that has been shown to perform well in several domains, including
Genetic Programming (GP). Differently from traditional EAs where variation
acts blindly, GOMEA learns a model of interdependencies within the genotype,
i.e., the linkage, to estimate what patterns to propagate. In this article, we
study the role of Linkage Learning (LL) performed by GOMEA in Symbolic
Regression (SR). We show that the non-uniformity in the distribution of the
genotype in GP populations negatively biases LL, and propose a method to
correct for this. We also propose approaches to improve LL when ephemeral
random constants are used. Furthermore, we adapt a scheme of interleaving runs
to alleviate the burden of tuning the population size, a crucial parameter for
LL, to SR. We run experiments on 10 real-world datasets, enforcing a strict
limitation on solution size, to enable interpretability. We find that the new
LL method outperforms the standard one, and that GOMEA outperforms both
traditional and semantic GP. We also find that the small solutions evolved by
GOMEA are competitive with tuned decision trees, making GOMEA a promising new
approach to SR.

Keywords

> Genetic programming, symbolic regression, linkage, GOMEA, machine learning,
> interpretability

##  1 Introduction

Symbolic Regression (SR) is the task of finding a function that explains
hidden relationships in data, without prior knowledge on the form of such
function. Genetic Programming (GP) (Koza,, 1992) is particularly suited for
SR, as it can generate solutions of arbitrary form using basic functional
components.

Much work has been done in GP for SR, proposing novel algorithms (Krawiec,,
2015; Zhong et al.,, 2018; De Melo,, 2014), hybrids (Žegklitz and Pošík,,
2017; Icke and Bongard,, 2013), and other forms of enhancement (Keijzer,,
2003; Chen et al.,, 2015). What is recently receiving a lot of attention is
the use of so-called _semantic-aware_ operators, which enhance the variation
process of GP by considering intermediate solution outputs (Pawlak et al.,,
2015; Chen et al.,, 2018; Moraglio et al.,, 2012). The use of semantic-aware
operators has proven to enable the discovery of very accurate solutions, but
often at the cost of complexity: solution size can range from hundreds to
billions of components (Pawlak et al.,, 2015; Martins et al.,, 2018). These
solutions are consequently impossible to interpret, a fact that complicates or
even prohibits the use of GP in many real-world applications because many
practitioners desire to understand what a solution means before trusting its
use (Lipton,, 2018; Guidotti et al.,, 2018). The use of GP to discover
uninterpretable solutions can even be considered to be questionable in many
domains, as many alternative machine learning algorithms exist that can
produce competitive solutions much faster (Orzechowski et al.,, 2018).

We therefore focus on SR when GP is _explicitly constrained_ to generate
small-sized solutions, i.e. mathematical expressions consisting of a small
number of basic functional components, to increase the level of
interpretability. With size limitation, finding accurate solutions is
particularly hard. It is not without reason that many effective algorithms
work instead by growing solution size, e.g., by iteratively stacking
components (Moraglio et al.,, 2012; Chen and Guestrin,, 2016).

A recurring hypothesis in GP literature is that the evolutionary search can be
made effective if _salient patterns_ , occurring in the representation of
solutions (i.e., the genotype), are identified and preserved during variation
(Poli et al.,, 2008). It is worth studying if this holds for SR, to find
accurate small solutions.

The hypothesis that salient patterns in the genotype can be found and
exploited is what motivates the design of Model-Based Evolutionary Algorithms
(MBEAs). Among them, the Gene-pool Optimal Mixing Evolutionary Algorithm
(GOMEA) is recent EA that has proven to perform competitively in different
domains: discrete optimization (Thierens and Bosman,, 2011; Luong et al.,,
2014), real-valued optimization (Bouter et al.,, 2017), but also grammatical
evolution (Medvet et al., 2018a, ), and, the focus of this article, GP
(Virgolin et al.,, 2017, 2018). GOMEA embodies within each generation a model-
learning phase, where _linkage_ , i.e. the inter-dependency within parts of
the genotype, is modeled. During variation, the linkage information is used to
propagate genotype patterns and avoid their disruption.

The aim of this article is to understand the role of linkage learning when
dealing with SR, and consequently improve the GP variant of GOMEA (GP-GOMEA),
to find small and accurate SR solutions for realistic problems. We present
three main contributions. First, we propose an improved linkage learning
approach, that, differently from the original one, is unbiased with respect to
the way the population is initialized. Second, we analyze how linkage learning
is influenced by the presence of many different constant values, sampled by
Ephemeral Random Constant (ERC) nodes (Poli et al.,, 2008), and explore
strategies to handle them. Third, we introduce improvements upon GP-GOMEA’s
Interleaved Multistart Scheme (IMS), a scheme of multiple evolutionary runs of
increasing evolutionary budget that executes them in an interleaved fashion,
to better deal with SR and learning tasks in general.

The structure of this article is as follows. In Section 2 we briefly discuss
related work on MBEAs for GP. In Section 3, we explain how GP-GOMEA and
linkage learning work. Before proceeding with the description of the new
contributions and experiments, Section 4 shows general parameter settings and
datasets that will be used along the article. Next, we proceed by interleaving
our findings on current limitations of GP-GOMEA followed by proposals to
overcome such limitations, and respective experiments. In other words, we
describe how we improve linkage learning one step at a time. In particular,
Section 5 presents current limitations of linkage learning, and describes how
we improve linkage learning. Strategies to learn linkage efficiently and
effectively when ERCs are used are described in Section 6. We propose a new
IMS for SR in Section 7, and use it in Section 8 to benchmark GP-GOMEA with
competing algorithms: traditional GP, GP using a state-of-the-art semantic-
aware operator, and the very popular decision tree for regression (Breiman et
al.,, 1984). Lastly, we discuss our findings and draw conclusions in Section
9.

##  2 Related work

We differentiate today’s MBEAs into two classes: Estimation-of-Distribution
Algorithms (EDA), and Linkage-based Mixing EAs (LMEA). EDAs work by
iteratively updating a probabilistic model of good solutions, and sampling new
solutions from that model. LMEAs attempt to capture linkage, i.e., inter-
dependencies between parts of the genotype, and proceed by variating solutions
with mechanisms to avoid the disruption of patterns with strong linkage.

Several EDAs for GP have been proposed so far. (Hauschild and Pelikan,, 2011)
and (Kim et al.,, 2014) are relatively recent surveys on the matter. Two
categories of EDAs for GP have mostly emerged in the years: one where the
shape of solutions adheres to some template to be able to estimate
probabilities of what functions and terminals appear in what locations (called
_prototype tree_ for tree-based GP) (Salustowicz and Schmidhuber,, 1997;
Sastry and Goldberg,, 2003; Yanai and Iba,, 2003; Hemberg et al.,, 2012), and
one where the probabilistic model is used to sample grammars of rules which,
in turn, determine how solutions are generated (Shan et al.,, 2004; Bosman and
De Jong,, 2004; Wong et al.,, 2014; Sotto and de Melo,, 2017). Research on
EDAs for GP appears to be limited. The review of (Kim et al.,, 2014) admits,
quoting, that “ _Unfortunately, the latter research [EDAs for GP] has been
sporadically carried out, and reported in several different research streams,
limiting substantial communication and discussion_ ”.

Concerning symbolic regression, we crucially found no works where it is
attempted on realistic datasets (we searched among the work reported by the
surveys and other recent work cited here). Many contributions on EDAs for GP
have been validated on hard problems of artificial nature instead, such as
_Royal Tree_ and _Deceptive Max_ (Hasegawa and Iba,, 2009). Some real-world
problems have been explored, but concerning only a limited number of variables
(Tanev,, 2007; Li et al.,, 2010). When considering symbolic regression, at
most synthetic functions or small physical equations with only few ($\leq 5$)
variables have been considered (e.g., by (Ratle and Sebag,, 2001; Sotto and de
Melo,, 2017)).

The study of LMEAs has emerged the first decade of the millennium in the field
of binary optimization, where it remains mostly explored to date (Chen et
al.,, 2007; Thierens and Bosman,, 2013; Goldman and Punch,, 2014; Hsu and Yu,,
2015). Concerning GP, GOMEA is the first state-of-the-art LMEA ever brought to
GP (Virgolin et al.,, 2017).

GP-GOMEA was first introduced in (Virgolin et al.,, 2017), to tackle classic
yet artificial benchmark problems of GP (including some of the ones mentioned
before), where the optimum is known. The IMS, largely inspired on the work by
(Harik and Lobo,, 1999), was also proposed, to relieve the user from the need
of tuning the population size. Population sizing is particularly crucial for
MBEAs in general: the population needs to be big enough for probability or
linkage models to be reliable, yet small enough to allow efficient search
(Harik et al.,, 1999).

GP-GOMEA has also seen a first adaptation to SR, to find small and accurate
solutions for a clinical problem where interpretability is important (Virgolin
et al.,, 2018). There, GP-GOMEA was engineered for the particular problem, and
no analysis of what linkage learning brings to SR was performed. Also, instead
of using the IMS, a fixed population size was used. This is because the IMS
was originally designed by (Virgolin et al.,, 2017) to enable benchmark
problems to be solved to optimality. No concern on generalization of solutions
to unseen test cases was incorporated.

As to combining LMEAs with grammatical evolution, (Medvet et al., 2018a, )
also employed GOMEA, to attempt to learn and exploit linkage when dealing with
different types of pre-defined grammars. In that work, only one synthetic
function was considered for symbolic regression, among other four benchmark
problems.

There is a need of assessing whether MBEAs can bring an advantage to real-
world symbolic regression problems. This work attempts to do this, by
exploring possible limitations of GP-GOMEA and ways to overcome them, and
validating experiments upon realistic datasets with dozens of features and
thousands of observations.

##  3 Gene-pool Optimal Mixing Evolutionary Algorithm for GP

Three main concepts are at the base of (GP-)GOMEA: solution representation
(genotype), linkage learning, and linkage-based variation. These components
are arranged in a common outline that encompasses all algorithms of the GOMEA
family.

Algorithm 1 shows the outline of GOMEA. As most EAs, GOMEA starts by
initializing a population $\mathcal{P}$, given the desired population size
$n^{\text{pop}}$. The generational loop is then started and continues until a
termination criterion is met, e.g., a limit on the number of generations or
evaluations, or a maximum time. Lines 4 to 8 represent a generation. First,
the linkage model is learned, which is called Family of Subsets (FOS)
(explained in Sec. 3.2). Second, each solution $\mathcal{P}_{i}$ is used to
generate an offspring solution $\mathcal{O}_{i}$ by the variation operator
Gene-pool Optimal Mixing (GOM). Last, the offspring replace the parent
population. Note the lack of a separate selection operator. This is because
GOM performs variation and selection at the same time (see Sec 3.3).

For GP-GOMEA, an extra parameter is needed, the tree height (or, equivalently,
tree depth) $h$. This is necessary to determine the representation of
solutions, as described in the following Section 3.1.

Algorithm 1 Outline of GOMEA

1procedure runGOMEA($n^{\text{pop}}$)

2 $\mathcal{P}\leftarrow$initializePopulation($n^{\text{pop}}$)

3 while terminationCriteriaNotMet() do

4 $F\leftarrow$learnFOS($\mathcal{P}$)

5 $\mathcal{O}\leftarrow\emptyset$

6 for $i\in\\{1,\dots,n^{\text{pop}}\\}$ do

7 $\mathcal{O}_{i}\leftarrow$GOM($\mathcal{P}_{i},\mathcal{P},F$)

8 $\mathcal{P}\leftarrow\mathcal{O}$

###  3.1 Solution representation in GP-GOMEA

GP-GOMEA uses a modification of the tree-based representation (Koza,, 1992)
which is similar to the one used by (Salustowicz and Schmidhuber,, 1997).
While typical GP trees can have any shape, GP-GOMEA uses a fixed template,
that allows linkage learning and linkage-based variation to be performed in a
similar fashion as for other, fixed string-length versions of GOMEA.

All solutions are generated as _perfect_ $r$-ary trees of height $h$, i.e.,
such that all non-leaf nodes have exactly $r$ children, and leaves are all at
maximum depth $h$, with $r$ being the maximum number of inputs accepted by the
functions (arity) provided in the function set (e.g., for $\\{+,-,\times\\}$,
$r=2$), and $h$ chosen by the user. Note that, for any node that is not at
maximum depth, $r$ child nodes are appended anyway: no matter if the node is a
terminal, or if it is a function requiring less than $r$ inputs (in this case,
the leftmost nodes are used as inputs). Some nodes are thus _introns_ , i.e.,
they are not executed to compute the output of the tree. It follows that while
trees are _syntactically_ redundant, they are not necessarily _semantically_
so. All trees of GP-GOMEA have the same number of nodes, equal to
$\ell=\sum_{i=0}^{h}r^{i}=\frac{r^{h+1}-1}{r-1}$. Figure 1 shows a tree used
by GP-GOMEA.

$\times$ $+$ $\exp$ $x$ $\exp$ $x$ $/$ $x$ $z$ $y$ $x$ $z$ $z$ $x$ $x$

Figure 1: Example of tree for GP-GOMEA with $h=3$ and $r=2$. While 15 nodes
are present, the nodes that influence the output are only 7: the gray nodes
are introns.

###  3.2 Linkage learning

The linkage model used by GOMEA algorithms is called the Family of Subsets
(FOS), and is a set of sets:

$F=\\{F_{1},\dots,F_{|F|}\\},F_{i}\subseteq\\{1,\dots,l\\}.\vspace{-1mm}$

Each $F_{i}$ (called FOS subset) contains indices representing locations in
the genotype. For GP-GOMEA, these indices represent node locations. It is
sufficient to choose a parsing order to identify the same node locations in
all trees, since trees share the same shape.

In GOMEA, linkage learning corresponds to building a FOS. Different types of
FOS exist in literature, however, the one recommended as default is the
_Linkage Tree_ (LT), by, e.g., (Thierens and Bosman,, 2013; Virgolin et al.,,
2017). The LT captures linkage on hierarchical levels. An LT is learned every
generation, from the population. To assess whether linkage learning plays a
key role, i.e. whether it is better than randomly choosing linkage relations,
we also consider the Random Tree (RT) (Virgolin et al.,, 2017).

####  3.2.1 Linkage Tree

The LT arranges the FOS subsets in a binary tree structure representing
hierarchical levels of linkage strength among genotype locations. The LT is
built bottom-up, i.e., from the leaves to the root. The bottom level of the
LT, i.e., the leaves, assume that all genotype locations are independent (no
linkage), and is realized by instantiating FOS subsets to singletons, each
containing a genotype location $i,\forall i\in\\{1,\dots,\ell\\}$.

To build the next levels, mutual information is used as a proxy for linkage
strength. Mutual information is a sensible choice to represent linkage
strength because it expresses, considering e.g. the pair $(i,j)$ of genotype
locations as random variables, the amount of information gained on $i$ given
observations on $j$ (and vice versa). In this light, the population can be
considered as a set of realizations of the genotype. In particular, the
realizations of each genotype location $i$ are what _symbols_ appear at
location $i$ in the population. In a binary genetic algorithm, symbols are
either ‘$0$’ or ‘$1$’, while in GP, symbols correspond to the types of
function and terminal nodes, e.g., ‘$+$’,‘$-$’,‘$x_{1}$’,‘$x_{2}$’. In other
words, random variables can assume as many values as there are possible
symbols in the instruction set111More symbols can be possible than the number
of instructions in case ERCs are used, since instantiating an ERC in a
solution results in a constant being randomly sampled..

Now, the next step is to compute the mutual information between each and every
pair of locations in the genotype of the entire population. Mutual information
between a pair of locations can be computed after measuring entropy for single
locations $\text{H}(i)$, and the joint entropy for locations pairs,
$\text{H}(i,j)$ (this aspect will be used in Sec. 5):

$\displaystyle\begin{split}&\text{MI}(i,j)=\text{H}(i)+\text{H}(j)-\text{H}(i,j),\text{where}\\\
\text{H}(i)&=-\sum\text{P}_{i}\log\text{P}_{i},\hskip
14.22636pt\text{H}(i,j)=-\sum\text{P}_{ij}\log\text{P}_{ij},\vspace{-1mm}\end{split}$
(1)

and $\text{P}_{i}$ ($\text{P}_{ij}$) is the (joint) probability distribution
over the symbols at location(s) $i$ ($i,j$), which can be estimated by
counting occurrences of symbol types in the population genotype. This requires
to loop over the entire population, and to use nested loops over location
pairs $i\in\\{1,\dots,\ell\\}$ and $j\in\\{i,\dots,\ell\\}$, leading to a time
complexity of $O(n^{\text{pop}}\ell^{2})$. The contribution to the entropy of
null probability cases ($-0\log 0$) is set to $0$.

Given mutual information between location pairs, we approximate linkage among
higher orders of locations using the Unweighted Pair Group Method with
Arithmetic Mean (UPGMA) (Gronau and Moran,, 2007). To ease understanding, we
now provide an explanation of how UPGMA is used to build the rest of the LT
that is primarily meant to be intuitive. In practice, we do not use an
implementation that strictly adheres to the following explanation, but we use
a more advanced algorithm that achieves the same result while having lower
time complexity, called the Reciprocal Nearest Neighbor algorithm (RNN). For
details on RNN, see (Gronau and Moran,, 2007).

UPGMA operates in a recursive, hierarchical fashion. Consider each singleton
containing a different genotype location $i$ as a cluster $C_{i}$, and the
mutual information between location pairs as a measure of similarity $S$
between clusters, i.e., $S(C_{i},C_{j}):=\text{MI}(i,j)$. Let $\mathcal{C}$ be
the collection of clusters to be parsed, initially containing all location
singletons. Every iteration, firstly a new cluster $C_{i^{\star}}\cup
C_{j^{\star}}$ is formed by joining the clusters $C_{i^{\star}},C_{j^{\star}}$
that have maximal similarity. Secondly, $C_{i^{\star}}$ and $C_{j^{\star}}$
are removed from $\mathcal{C}$, and $C_{i^{\star}}\cup C_{j^{\star}}$ is
inserted in $\mathcal{C}$. When this happens, a FOS subset is added in the LT
that corresponds to (contains the same locations of) $C_{i^{\star}}\cup
C_{j^{\star}}$, as parent of the subsets that represent $C_{i^{\star}}$ and
$C_{j^{\star}}$. Thirdly, the similarity between $C_{i^{\star}}\cup
C_{j^{\star}}$ and every other cluster $C_{k}$ is computed, with:

$S(C_{k},C_{i^{\star}}\cup
C_{j^{\star}})=\frac{|C_{i^{\star}}|}{|C_{i^{\star}}|+|C_{j^{\star}}|}S(C_{k},C_{i})+\frac{|C_{j^{\star}}|}{|C_{i^{\star}}|+|C_{j^{\star}}|}S(C_{k},C_{j}).\vspace{-1mm}$

Iterations are repeated until no more merging is possible, i.e.,
$\mathcal{C}=\emptyset$. This necessarily happens in $2\ell-1$ iterations.
Note that the last iterations sets the root of the LT, i.e., the subset that
contains all genotype locations: $\\{1,\dots,\ell\\}$. Note also that the
structure of the LT is related to the structure of the tree-like genotype of
GP solutions only in the sense that the LT contains $2\ell-1$ FOS subsets and
the genotype has length $\ell$, but it is not a one-to-one match to the
structure of the genotype.

With the efficient implementation of UPGMA by RNN, the time complexity to
build the LT remains bounded by $O(n^{\text{pop}}\ell^{2})$.

####  3.2.2 Random Tree

While linkage learning assumes an inherent structural inter-dependency to be
present within the genotype that can be captured in an LT, such hypothesis may
not be true. In such a scenario, using the LT might be not better than
building a similar FOS in a completely random fashion. The RT is therefore
considered to test this. The RT shares the same tree-like structure of the LT,
but is built randomly rather than using mutual information (taking $O(\ell)$).
We use the RT as an alternative FOS for GP-GOMEA.

###  3.3 Gene-pool Optimal Mixing

Once the FOS is learned, the variation operator GOM generates the offspring
population. GOM varies a given solution $\mathcal{P}_{i}$ in iterative steps,
by overriding the nodes at the locations specified by each $F_{j}$ in the FOS,
with the nodes in the same locations taken from random donors in the
population. Selection is performed within GOM in a hill-climbing fashion,
i.e., variation attempts that result in worse fitness are undone.

The pseudo-code presented in Algorithm 2 describes GOM in detail. To begin, a
backup $\mathcal{B}_{i}$ of the parent solution $\mathcal{P}_{i}$ is made,
including its fitness, and similarly an offspring solution
$\mathcal{O}_{i}=\mathcal{P}_{i}$ is created. Next, the FOS $F$ is shuffled
randomly: this is to provide different combinations of variation steps along
the run and prevent bias. For each set of node locations $F_{j}$, a random
donor $\mathcal{D}$ is then picked from the population, and $\mathcal{O}_{i}$
is changed by replacing the nodes specified by $F_{j}$ with the homologous
ones from $\mathcal{D}$. This process is exemplified in Fig. 2. It is then
assessed whether at least one (syntactic) non-intron node of the tree has been
changed by variation (indicated by $\neq^{\star}$ in line 7). When that is not
the case, $\mathcal{O}_{i}$ will have the same behavior as $\mathcal{B}_{i}$,
thus the fitness is necessarily identical. Otherwise, the new fitness
$f_{\mathcal{O}_{i}}$ is computed: if not worse than the previous one, the
change is kept, and the backup is updated, otherwise the change is reversed.

Note that if a change results in $f_{\mathcal{O}_{i}}=f_{\mathcal{B}_{i}}$,
the change is kept. This allows random walks in the neutral fitness landscape
(Ebner et al.,, 2001; Sadowski et al.,, 2013). Note also that differently from
traditional subtree crossover and subtree mutation (Koza,, 1992), GOM can
change unconnected nodes at the same time, and keeps tree height limited to
the initially specified parameter $h$. Finally, GOM _does not consider_ any
FOS subset that contains all node locations, i.e., $F_{j}=\\{1,\dots,\ell\\}$,
as using such subset would mean to entirely replace $\mathcal{O}_{i}$ with
$\mathcal{D}$.

Algorithm 2 Pseudocode of GOM

1procedure GOM($\mathcal{P}_{i},\mathcal{P},F$)

2 $\mathcal{B}_{i}\leftarrow\mathcal{P}_{i}$; $f_{\mathcal{B}_{i}}\leftarrow
f_{\mathcal{P}_{i}}$; $\mathcal{O}_{i}\leftarrow\mathcal{P}_{i}$

3 $F\leftarrow$randomShuffle($F$)

4 for $F_{j}\in F$ do

5 $\mathcal{D}\leftarrow$pickRandomDonor($\mathcal{P}$)

6
$\mathcal{O}_{i}\leftarrow$overrideNodes($\mathcal{O}_{i},\mathcal{D},F_{j}$)

7 if $\mathcal{O}_{i}\neq^{\star}\mathcal{B}_{i}$ then

8 $f_{\mathcal{O}_{i}}\leftarrow$computeFitness($\mathcal{O}_{i}$)

9 if $f_{\mathcal{O}_{i}}\leq f_{\mathcal{B}_{i}}$ then #Assumption:
minimization of $f$

10 $\mathcal{B}_{i}\leftarrow\mathcal{O}_{i}$; $f_{\mathcal{B}_{i}}\leftarrow
f_{\mathcal{O}_{i}}$

11 else

12 $\mathcal{O}_{i}\leftarrow\mathcal{B}_{i}$; $f_{\mathcal{O}_{i}}\leftarrow
f_{\mathcal{B}_{i}}$

13 else

14 $\mathcal{B}_{i}\leftarrow\mathcal{O}_{i}$

$\times$ $+$ $\exp$ $x$ $x$ $y$ $x$ $\mathcal{O}_{i}$1253467$+$ $x$ $\times$
$y$ $x$ $x$ $x$ $\mathcal{D}$1253467$F_{j}=\\{3,5\\}$

Figure 2: Example of variation step performed by GOM for trees with $h=2$.
Squares on top of each node indicate the node location according to pre-order
traversal (depth-first). GOM replaces the nodes of $\mathcal{O}_{i}$ of which
the location is specified by $F_{j}$, with the homologous nodes of
$\mathcal{D}$ (blue contour).

##  4 General experimental settings

We now describe the general parameters that will be used in this article.
Table 1 reports the parameter settings which are typically used in the
following experiments, unless specified otherwise. The notation $\mathbf{x}$
represents the matrix of feature values. We use the Analytic Quotient (AQ) (Ni
et al.,, 2013) instead of protected division. This is because the AQ is
continuous in 0 for the second operand: $x_{1}\div_{\text{AQ}}x_{2}\coloneqq
x_{1}/\sqrt{1+x^{2}_{2}}$. Albeit continuity is not needed by many GP
variation operators (including GOM), it is useful at prediction time: (Ni et
al.,, 2013) show that using the AQ helps generalization (whereas using
protected division does not). However, the AQ may be considered relatively
hard to interpret.

As mentioned in the introduction, we focus on the evolution of solutions that
are constrained to be small, to _enable_ interpretability. We choose $h=4$
because this results in relatively balanced trees with up to $31$ nodes (since
$r=2$). We consider this size limitation a critical value: for the given
function set, we found solutions to be already borderline interpretable for us
(this is discussed further in Sec. 9). Larger values for $h$ would therefore
play against the aim of this study. When benchmarking GP-GOMEA in Sec. 8, we
also consider $h=3$ and $h=5$ for completeness.

We consider 10 real-world benchmark datasets from literature (Martins et al.,,
2018) that can be found on the UCI
repository222https://archive.ics.uci.edu/ml/index.php (Asuncion and Newman,,
2007) and other sources333https://goo.gl/tn6Zxv. The characteristics of the
datasets are summarized in Table 2.

We use the linearly-scaled Mean Squared Error (MSE) to measure solution
fitness (Keijzer,, 2003), as it can be particularly beneficial when evolving
small solutions. This means a fast (cost $O(n)$ with $n$ number of dataset
examples) linear regression is applied between the target $y$ and the solution
prediction $\tilde{y}$ prior to computing the MSE. We present our results in
terms of variance-Normalized MSE (NMSE), i.e.
$100\times\frac{\text{MSE}(y,\tilde{y})}{var(y)}$, so that results from
different datasets are on a similar scale (the $100\times$ factor is added for
readability).

To assess statistical significance when comparing the results of multiple
executions of two algorithms (or configurations) on a certain dataset, we use
the Wilcoxon signed-rank test (Demšar,, 2006). This test is set up to compare
competing algorithms based on the same prior conditions. In particular, we
employ pairs of executions where the dataset is split into identical training,
validation, and test sets for both algorithms being tested. This is because
the particular split of data determines the fitness function (based on the
training set), and the achievable generalization error (for the validation and
test sets). We consider a difference to be significant if a smaller $p$-value
than $0.05/\beta$ is found, with $\beta$ the Bonferroni correction
coefficient, used to prevent false positives. If more than two algorithms need
to be compared, we first perform a Friedman test on mean performance over all
datasets (Demšar,, 2006). We use the symbols  $\blacktriangle$,
$\blacktriangle$ to respectively indicate significant superiority, and
inferiority (absence of a symbol means no significant difference). The result
_next_ to the symbol  $\blacktriangle$ ( $\blacktriangle$ ) signifies a result
being better (worse) than the result obtained by the algorithm that has the
same color of the symbol. Algorithms and/or configurations are color coded in
each table reporting results (colors are color-blind safe).

Table 1: General parameter settings for the experiments Parameter | Setting
---|---
Function set | $\\{+,-,\times,\div_{\text{AQ}}\\}$
Terminal set | $\mathbf{x}\cup\\{\text{ERC}\\}$
ERC bounds | $[\min\mathbf{x},\max\mathbf{x}]$
Initialization for GP-GOMEA | Half-and-Half as in (Virgolin et al.,, 2018)
Tree height $h$ | 4
Train-validation-test split |  $50$%–$25$%–$25$%
Experiment repetitions | $30$
Table 2: Regression datasets used in this work

Name | Abbreviation | # Features | # Examples
---|---|---|---
Airfoil | Air | 5 | 1503
Boston housing | Bos | 13 | 506
Concrete compres. str. | Con | 8 | 1030
Dow chemical | Dow | 57 | 1066
Energy cooling | EnC | 8 | 768
Energy heating | EnH | 8 | 768
Tower | Tow | 25 | 4999
Wine red | WiR | 11 | 1599
Wine white | WiW | 11 | 4898
Yacht hydrodynamics | Yac | 6 | 308

##  5 Improving linkage learning for GP

In previous work on GP-GOMEA, learning the LT was performed the same way it is
done for any discrete GOMEA implementation, i.e. by computing the mutual
information between pairs of locations $(i,j)$ in the genotype (Eq. 1)
(Virgolin et al.,, 2017). However, the distribution of node types is typically
not uniform when a GP population is initialized (e.g., function nodes never
appear as leaves). In fact, this depends on the cardinality of the function
and terminal sets, on the arity of the functions, and on the population
initialization method (e.g., _Full_ , _Grow_ , _Half-and-Half_ , _Ramped Half-
and-Half_ (Luke and Panait,, 2001)). Note that it does not depend on the
particular dataset in consideration (except in that the number of features
determines the size of the terminal set). The lack of uniformity in the
distribution leads to the emergence of mutual information between particular
parts of the genotype. Crucially, this mutual information is natural to the
solution representation, the sets of symbols and the initialization process.

If mutual information is used to represent linkage, then linkage will already
be observed at initialization. However, it is reasonable to expect no linkage
to be present in an initialized population, as evolution did not take place
yet. Figure 3 shows the mutual information matrix between pairs of node
locations in an initial population of $1,000,000$ solutions with maximum
height $h=2$, using _Half-and-Half_ , a function set of size 4 with maximum
number of inputs $r=2$, and a terminal set of size 6 (no ERCs are used). Each
tree contains exactly $7$ nodes. We index node locations with pre-order tree
traversal, i.e., $1$ is the root, $2$ its first child, $5$ its second child,
$3,4$ are (leaves) children of $2$, and $6,7$ are (leaves) children of $5$.
Nodes at locations 2 and 5 can be functions only if a function is sampled at
node 1. It can be seen that the mutual information matrix of location pairs
(correctly) captures the non-uniformity in the initial distribution (i.e.,
larger mutual information values are present between non-leaf nodes). Using
mutual information directly as a proxy for linkage may be undesirable.

$\text{MI},n^{\text{pop}}=10^{6}$
---
Figure 3: Mutual information matrix between pairs of locations in the genotype
(x and y labels). Darker blue represents higher values. The matrix is computed
for an initialized population of size $10^{6}$. The values suggest the
existence of linkage even though no evolution has taken place yet.

###  5.1 Biasing mutual information to represent linkage

We propose to overcome the aforementioned problem by measuring linkage with a
modified version of the mutual information, such that no linkage is measured
at initialization. Our hypothesis is that, if we apply such a correction so
that no patterns are identified at initialization, the truly salient patterns
will have a bigger chance of emerging during evolution, and better results
will be achieved.

Let us consider the scenario where, at initialization, symbols are uniformly
distributed. For example, this typically happens in binary genetic algorithms.
The mutual information between pairs of genotype locations that is expected at
initialization, i.e., at generation $g=1$ before variation and selection, will
then correspond to the identity matrix: $\text{MI}^{g}|_{g=1}=I$ (assuming
binary symbols and mutual information in bits as well as a sufficiently large
population size). This mutual information matrix is suitable to represent
linkage as no linkage should be present at initialization.

We propose to adopt a biased mutual information matrix $\text{MI}_{b}(i,j)$ to
represent the linkage between a pair of genotype locations $(i,j)$, that has
the property:

$\text{MI}^{g}_{b}(i,j)|_{g=1}=I,\vspace{-1mm}$

no matter the actual distribution of the initial population.

To this end, we use Eq. 1, i.e., we manipulate the entropy terms, to represent
maximal randomness to be present at initialization for each genotype location.
In particular, we propose to use biased entropy metrics such that
$\text{H}^{g}_{b}(i)|_{g=1}=1$ and $\text{H}^{g}_{b}(i,j)|_{g=1}=2$ (for
$i\neq j$) , since

$\displaystyle\text{MI}^{g}_{b}(i,j)|_{g=1}$
$\displaystyle=\left(\text{H}^{g}_{b}(i)+\text{H}^{g}_{b}(j)-\text{H}^{g}_{b}(i,j)\right)|_{g=1}$
$\displaystyle=1+1-2=0\text{ \hskip 56.9055pt (for }i\neq j,\text{ else
}1\text{)}.\vspace{-1mm}$

We propose to use linear biasing coefficients $\beta_{i}$ ($\beta_{i,j}$) to
have the general biased entropy for any generation $g$ as
$\text{H}^{g}_{b}(i)=\beta_{i}\text{H}(i)$ and
$\text{H}^{g}_{b}(i,j)=\beta_{i,j}\text{H}(i,j)$, with
$\beta_{i}=\left(\text{H}^{g}_{b}(i)|_{g=1}\right)^{-1}$ and
$\beta_{i,j}=2\left(\text{H}^{g}(i,j)|_{g=1}\right)^{-1}$ to enforce maximal
randomness at initialization.

To determine the beta coefficients _exactly_ means to know the true
distribution inferred by the sampling process used to sample the initial
population, and thus the true initial entropy for each genotype location.
However, this is generally not trivial to determine for GP, since a number of
factors need to be considered. E.g., if the _Ramped Half-and-Half_
initialization method is used, what symbol is sampled at a location depends on
the chance to use _Full_ or _Grow_ , the chance to pick the function or the
terminal set based on the depth, the size of these sets, and possibly other
problem-specific factors. Hence, we propose to simply approximate the $\beta$
coefficients by using the $\text{H}^{g}(i)|_{g=1}$ measured on the initial
population, assuming the population to be large enough.

Summing up, the pairwise linkage estimation we propose to use at generation
$g$, for a pair of locations $(i,j)$, will be:

$\text{MI}^{g}_{\tilde{b}}(i,j)=\beta_{i}\text{H}^{g}(i)+\beta_{j}\text{H}^{g}(j)-\beta_{i,j}\text{H}^{g}(i,j).\vspace{-1mm}$
(2)

The tilde in $\tilde{b}$ is to remark that this is an approximation.

###  5.2 Estimation of linkage by MI$\tilde{b}$

As a preliminary step, we observe what linkage values are obtained between
pairs of genotype locations by using $\text{MI}_{\tilde{b}}$. For conciseness,
in the following we denote $\text{MI}^{g}_{\tilde{b}}(i,j)|_{g=\Gamma}$ with
$\text{MI}^{\Gamma}_{\tilde{b}}(i,j)$. We show the MI matrix computed at the
second generation of a GP-GOMEA run on the dataset Yac
($\text{MI}^{1}_{\tilde{b}}=I$ by construction). We do this for two population
sizes, $n^{\text{pop}}=10$ and $n^{\text{pop}}=10^{6}$. We expect that, the
bigger $n^{\text{pop}}$ is, the closer $\text{MI}^{2}_{\tilde{b}}$ is to $I$.

We use the parameters of Table 1, a terminal set of size 6 (the features of
Yac, no ERC) and $h=2$, i.e. $\ell=7$ nodes per tree. Figure 4 shows the
biased mutual information matrix between location pairs, for the two
population sizes. It can be seen that the values can be lower than 0 or bigger
than 1. However, while this is particularly marked for $n^{\text{pop}}=10$,
with minimum of -0.787 and maximum of 1.032, it becomes less evident for
$n^{\text{pop}}=10^{6}$, with minimum of -0.018 and maximum of 0.989. The fact
that $\text{MI}^{2}_{\tilde{b}}\approx I$ for $n^{\text{pop}}=10^{6}$ is
because, with such a large population size, considerable diversity is still
present in the second generation.

$\text{MI}^{2}_{\tilde{b}},n^{\text{pop}}=10^{1}$ | $\text{MI}^{2}_{\tilde{b}},n^{\text{pop}}=10^{6}$
---|---
|
Figure 4: Mutual information matrices at the second generation using our
biasing method to better represent linkage, with population size of $10$
(left), and of $10^{6}$ (right) for a particular run of GP-GOMEA. The
rightmost matrix is closest to the identity $I$.

###  5.3 Experiment: LT–$\text{MI}_{\tilde{b}}$ vs LT–MI vs RT

We now test the use of $\text{MI}_{\tilde{b}}$ over the standard MI for GP-
GOMEA with the LT. We denote the two configurations with
LT–$\text{MI}_{\tilde{b}}$ and LT–MI. We also consider the RT to see if mutual
information drives variation better than random information.

We set the population size to 2000 as a compromise between having enough
samples for linkage to be learned, and meeting typical literature values,
which range from hundreds to a few thousands. We use the function set of Table
1, and a tree height $h=4$ (thus $\ell=31$). We set a limit of 20 generations,
which corresponds to approximately 1200 generations of traditional GP, as each
solution is evaluated up to $2\ell-2$ times (size of the LT minus its root and
non-meaningful changes, see Sec. 3.2 and 3.3).

Table 3: Median NMSE of 30 runs for GP-GOMEA with LT–$\text{MI}_{\tilde{b}}$,
LT–MI, and RT.

| Training |  $\blacktriangle$ $\blacktriangle$ | Test
---|---|---|---
Dataset | LT–$\text{MI}_{\tilde{b}}$ | LT–MI | RT |  | LT–$\text{MI}_{\tilde{b}}$ | LT–MI | RT
Air | $\blacktriangle$$29.9$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$31.2$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$32.7$ |  $\blacktriangle$ $\blacktriangle$ |  | $\blacktriangle$$31.8$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$34.8$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$34.0$ |  $\blacktriangle$ $\blacktriangle$
Bos |  $\blacktriangle$$15.4$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$15.4$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$17.5$ |  $\blacktriangle$ $\blacktriangle$ |  | $\blacktriangle$$24.0$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$23.0$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$22.5$ | $\blacktriangle$ $\blacktriangle$
Con | $\blacktriangle$$17.5$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$18.5$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$19.0$ |  $\blacktriangle$ $\blacktriangle$ |  | $\blacktriangle$$18.7$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$19.6$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$20.1$ |  $\blacktriangle$ $\blacktriangle$
Dow | $\blacktriangle$$20.9$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$20.3$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$24.0$ |  $\blacktriangle$ $\blacktriangle$ |  | $\blacktriangle$$22.6$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$21.1$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$26.0$ |  $\blacktriangle$ $\blacktriangle$
EnC | $\blacktriangle$$8.42$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$9.68$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$9.09$ |  $\blacktriangle$ $\blacktriangle$ |  | $\blacktriangle$$9.18$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$10.7$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$10.3$ |  $\blacktriangle$ $\blacktriangle$
EnH | $\blacktriangle$$6.24$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$6.44$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$6.40$ |  $\blacktriangle$ $\blacktriangle$ |  | $\blacktriangle$$6.50$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$7.10$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$6.70$ |  $\blacktriangle$ $\blacktriangle$
Tow | $\blacktriangle$$12.5$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$12.5$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$13.1$ |  $\blacktriangle$ $\blacktriangle$ |  | $\blacktriangle$$13.0$ | $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$$12.8$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$13.2$ |  $\blacktriangle$ $\blacktriangle$
WiR | $\blacktriangle$$60.3$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$60.9$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$61.2$ |  $\blacktriangle$ $\blacktriangle$ |  | $\blacktriangle$$62.5$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$63.0$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$63.1$ |  $\blacktriangle$ $\blacktriangle$
WiW | $\blacktriangle$$68.1$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$68.4$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$68.7$ |  $\blacktriangle$ $\blacktriangle$ |  | $\blacktriangle$$69.1$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$69.7$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$69.5$ |  $\blacktriangle$ $\blacktriangle$
Yac | $\blacktriangle$$0.34$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$0.37$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$0.36$ |  $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$$0.58$ | $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$0.62$ |  $\blacktriangle$ $\blacktriangle$ | $\blacktriangle$$0.62$ |  $\blacktriangle$ $\blacktriangle$

###  5.4 Results: LT–$\text{MI}_{\tilde{b}}$ vs LT–MI vs RT

The training and test NMSE performances are reported in Table 3. The Friedman
test results in significant differences along training and test performance.
GP-GOMEA with LT–$\text{MI}_{\tilde{b}}$ is clearly the best performing
algorithm, with significantly lower NMSE compared to LT–MI on 8/10 datasets
when training, and 7/10 at test time. It is always better than using the RT
when training, and in 9/10 cases when testing. The LT–MI is comparable with
the RT for these problems.

The result of this experiment is that the use of the new
$\text{MI}_{\tilde{b}}$ to build the LT simply enables GP-GOMEA to perform a
more competent variation than the use of MI. Also, using the LT this way leads
to better results than when making random changes with the RT. Figure 5 shows
the evolution of the training NMSE for the dataset Yac. It can be seen that
the LT–$\text{MI}_{\tilde{b}}$ allows to quickly reach smaller errors than the
other two FOS types. We observed similar training patterns for the other
datasets (not shown here).

In the remainder, when we write “LT”, we refer to LT–$\text{MI}_{\tilde{b}}$.

Training NMSE |
---|---
|  Generations
Figure 5: Median fitness of the best solution of 30 runs on Yac, for
LT–$\text{MI}_{\tilde{b}}$, LT–MI, and RT ($10^{\text{th}}$ and
$90^{\text{th}}$ percentiles in shaded area).

###  5.5 Experiment: assessing propagation of node patterns

The previous experiment showed that using linkage-driven variation (LT) can be
favorable compared to random variation (RT). This seems to confirm the
hypothesis that, in certain SR problems, salient underlying patterns of nodes
exist in the genotype that can be exploited. Another aspect that can be
considered w.r.t. such hypothesis is how final solutions look: if linkage
learning identifies specific node patterns, it can be expected that their
propagation will lead to the discovery of similar solutions over different
runs.

Therefore, we now want to assess whether the use of the LT has a bigger chance
to lead to the discovery of a particular best-of-run solution, compared to the
use of the RT. We use the same parameter setting as described in Sec. 5.3, but
perform 100 repetitions. While each run uses a different random seed (e.g.,
for population initialization), we fix the dataset split, as changing the
training set results in changing the fitness function. We repeat the 100 runs
on 5 random dataset splits, on the smallest dataset Yac. Together with
$n^{\text{pop}}=2000$ as in the previous experiment, we also consider a
doubled $n^{\text{pop}}=4000$.

Table 4 reports the number of best found solutions that have at least one
duplicate, i.e. their genotype is semantically equivalent (e.g.,
$x_{1}+x_{2}=x_{2}+x_{1}$), along different runs for 5 random splits of Yac
(semantic equivalence was determined by automatic tests444Including the use of
symbolic simplification with https://andrewclausen.net/computing/deriv.html.
followed by manual inspection). It can be seen that the LT finds more
duplicate solutions than the RT, by a margin of around 30% (difference between
averages). Figure 6 shows the distribution of solutions found for the second
dataset split with $n^{\text{pop}}=4000$, i.e. where both the LT and the RT
found a large number of duplicates. The LT has a marked chance of leading to
the discovery of a particular solution, up to one-fourth of the times. When
the RT is used, a same solution is found only up to 6 times out of 100.

This confirms the hypothesis that linkage-based variation can propagate
salient node patterns more than random variation should such patterns exist,
enhancing the likelihood of discovering particular solutions.

Table 4: Percentage of best solutions with duplicates found by GP-GOMEA with
LT and RT for different splits of Yac.

| $n^{\text{pop}}=2000$ | $\blacktriangle$ | $n^{\text{pop}}=4000$
---|---|---|---
Split | LT | RT |  | LT | RT
1 | 36 | 18 |  | 44 | 15
2 | 42 | 12 |  | 49 | 21
3 | 40 | 7 |  | 43 | 8
4 | 43 | 8 |  | 45 | 25
5 | 36 | 16 |  | 49 | 16
Avg. | 39 | 12 |  | 46 | 17

# Duplicates |  |
---|---|---
|  Solutions |  Solutions
Figure 6: Distribution of best found solutions for 100 runs by using the LT
(left) and the RT (right) with $n^{\text{pop}}=4000$ on the second dataset
split of Yac.

##  6 Ephemeral random constants & linkage

In many GP problems, and in particular in SR, the use of ERCs can be very
beneficial (Poli et al.,, 2008). An ERC is a terminal which is set to a
constant only when instantiated in a solution. In SR, this constant is
commonly sampled uniformly at random from a user-defined interval.

Because every node instance of ERC is a different constant, linkage learning
needs to deal with a large number of different symbols. This can lead to two
shortcomings. First, a very large population size may be needed for salient
node patterns to emerge. Second, data structures used to store the frequencies
of symbols grow really big and become slow (e.g., hash maps).

We explore three strategies to deal with this:  (i) all-const: Ignore the
shortcomings, and consider all different constants as different symbols during
linkage learning;  (ii) no-const: Skip all constants during linkage learning,
i.e. set their frequency to zero. This approximation is reasonable since all
constants are unique at initialization, and the respective frequency is almost
zero. However, during evolution some constants will be propagated while others
will be discarded, making this approximation less and less accurate over time;
(iii) bin-const: Perform on-line binning. We set a maximum number $\gamma$ of
constants to consider. After $\gamma$ different constants have been
encountered in frequency counting, any further constant is considered to fall
into the same bin as the closest constant among the first $\gamma$. The
closest constant can be determined with binary search in $\log_{2}(\gamma)$
steps. Contrary to strategy no-const, we expect the error of this
approximation to lower over time, because selection lowers diversity, meaning
that the total number of different constants will be reduced as generations
pass.

Table 5: Median training NMSE and median test NMSE of 30 runs for GP-GOMEA
with the LT using the three strategies all-const, no-const, bin-const, and
with the RT.

| Training NMSE |  $\blacktriangle$ $\blacktriangle$ | Test NMSE
---|---|---|---
Dataset | all-const | no-const | bin-const | RT |  | all-const | no-const | bin-const | RT
Air |  $\blacktriangle$ $27.7$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $28.0$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $27.5$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $31.4$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $28.7$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $29.6$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $27.8$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $32.5$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Bos |  $\blacktriangle$ $15.2$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $15.3$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $15.0$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $17.6$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $24.2$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $23.2$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $21.8$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $24.2$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Con |  $\blacktriangle$ $17.2$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $17.2$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $17.0$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $18.5$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $18.5$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $18.7$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $18.8$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $19.8$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Dow |  $\blacktriangle$ $21.4$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $21.1$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $20.7$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $24.5$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $22.8$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $21.9$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $22.5$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $25.5$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
EnC |  $\blacktriangle$ $5.51$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $5.72$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $5.76$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $6.44$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $6.18$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $6.34$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $6.00$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $6.77$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
EnH |  $\blacktriangle$ $3.00$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $3.14$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $2.80$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $4.10$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $3.28$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $3.33$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $3.11$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $4.67$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Tow |  $\blacktriangle$ $12.3$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $12.2$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $12.3$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $13.2$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $12.9$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $12.8$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $12.8$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $13.5$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
WiR |  $\blacktriangle$ $60.3$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $60.2$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $60.2$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $61.2$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $63.6$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $62.9$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $62.9$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $63.2$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
WiW |  $\blacktriangle$ $67.6$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $68.1$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $68.0$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $68.5$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $68.9$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $69.0$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $69.4$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $69.9$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Yac |  $\blacktriangle$ $0.32$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $0.35$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $0.34$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $0.38$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  |  $\blacktriangle$ $0.55$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $0.61$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $0.52$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $0.63$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$

Table 6: Median time of 30 runs for GP-GOMEA with the LT using the three
strategies all-const, no-const, bin-const, and with the RT.

| Time (s)
---|---
Dataset | all-const | no-const | bin-const | RT
Air |  $\blacktriangle$ $355.4$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $71.4$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $80.0$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $80.1$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Bos |  $\blacktriangle$ $63.4$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $29.4$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $30.9$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $24.5$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Con |  $\blacktriangle$ $154.9$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $56.7$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $59.8$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $58.4$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Dow |  $\blacktriangle$ $53.8$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $51.7$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $54.9$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $37.7$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
EnC |  $\blacktriangle$ $147.2$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $40.5$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $43.5$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $45.6$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
EnH |  $\blacktriangle$ $145.0$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $45.8$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $49.4$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $45.7$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Tow |  $\blacktriangle$ $255.9$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $246.6$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $245.6$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $233.9$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
WiR |  $\blacktriangle$ $126.1$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $67.7$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $80.2$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $70.1$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
WiW |  $\blacktriangle$ $285.0$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $213.3$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $237.2$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $224.1$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$
Yac |  $\blacktriangle$ $236.5$ |  $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $23.9$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $24.8$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$ |  $\blacktriangle$ $22.8$ | $\blacktriangle$ $\blacktriangle$ $\blacktriangle$

###  6.1 Experiment: linkage learning with ERCs

We use the same parameter setup of the experiment in Sec. 5.3, this time
adding an ERC terminal to the terminal set. We compare the three strategies to
handle ERCs when learning the LT. For this experiment and in the rest of the
article, we use $\gamma=100$ in bin-const. We observed that for problems with
a small number of features (e.g., Air and Yac), i.e., where ERC sampling is
more likely and thus more constants are produced, this choice reduces the
number of constant symbols to be considered by linkage learning in the first
generations by a factor of $\sim 50$. We also report the results obtained with
the RT as a baseline, under the hypothesis that using ERCs compromises linkage
learning to the point that random variation becomes equally good or better.

The results of this experiment are shown in Table 5 (training and test NMSE)
and Table 6 (running time). The Friedman test reveals significant differences
among the configurations for train, test, and time performance. Note that the
use of ERCs leads to lower errors compared to not using them (compare with
Table 3).

In terms of training error, the RT is always outperformed by the use of the
LT, no matter the strategy. The all-const strategy is significantly better
than no-const in half of the problems, and never worse. Overall, bin-const
performs best, with 6 out of 10 significantly better results than all-const.
The fact that all-const can be outperformed by bin-const supports the
hypothesis that linkage learning can be compromised by the presence of too
many constants to consider, which hide the true salient patterns. Test results
are overall similar to the training ones, but less comparisons are
significant.

In terms of time, all-const is almost always significantly worse than the
other methods, and often by a consistent margin. This is particularly marked
for problems with a small number of features (i.e., Air, Yac). There, more
random constants are present in the initial population, since the probability
of sampling the ERC from the terminal set is inversely proportional to the
number of features.

Interestingly, despite the lack of a linkage-learning overhead, using the RT
is not always the fastest option. This is because random variation leads to a
slower convergence of the population compared to the linkage-based one, where
salient patterns are quickly propagated, and less variation attempts result in
changes of the genotype that require a fitness evaluation (see Sec. 3.3). The
slower convergence caused by the RT can also be seen in Figure 5 (for the
previous experiment), and was also observed in other work, in terms of
diversity preservation (Medvet et al., 2018b, ).

Between the LT-based strategies, the fastest is no-const, at the cost of a
bigger training error. Although consistently slower than no-const, bin-const
is still quite fast, and achieves the lowest training errors. We found bin-
const to be preferable in test NMSE as well. In the following, we always use
bin-const, with $\gamma=100$.

##  7 Interleaved Multistart Scheme

The Interleaved Multistart Scheme (IMS) is a wrapper for evolutionary runs
largely inspired by the work of (Harik and Lobo,, 1999) on genetic algorithms.
It works by interleaving the execution of several runs of increasing resources
(e.g., population size). The main motivation for using the IMS is to make an
EA much more robust to parameter settings, and alleviate the need for
practitioners to tinker with parameters. In fact, the whole design of GP-GOMEA
attempts to promote the aspects of ease-of-use and robustness: the EA has no
need for parameters that specify how to conduct variation (e.g., crossover or
mutation rates), nor how to conduct selection (e.g., tournament size). The IMS
or similar schemes are often used with MBEAs (Lin and Yu,, 2018; Goldman and
Punch,, 2014), where population size plays a crucial role in determining the
quality of model building. Note that although the IMS has potential to be
parallelized, here it is used in a sequential manner.

An IMS for GP-GOMEA was first proposed in (Virgolin et al.,, 2017), and its
outline is as follows. A collection of parameter settings
$\sigma_{\text{base}}$ is given as input, which will be used in the first run
$R_{1}$. The IMS runs until a termination criterion is met (e.g., number of
generations, time budget). The run $R_{i}$ performs one generation if no run
that precedes it exists (e.g., because it is the first run or because all
previous runs have been terminated), or if the previous run $R_{i-1}$ has
executed $g$ generations. The first time $R_{i}$ is about to execute a
generation, it is initialized using the parameter settings
$\sigma_{\text{base}}$ scaled by the index $i$. For example, the population
size can be set to $2^{i-1}n^{\text{pop}}_{\text{base}}$ (i.e., doubling the
population size of the previous run). Finally, when a run completes a
generation, a check is done to determine if the run should be terminated
(explained below).

###  7.1 An IMS for supervised learning tasks

The first implementation of the IMS for GP-GOMEA was designed to deal with GP
benchmark problems of pure optimization. That implementation therefore scaled
both the population size and the height of trees in an attempt to find the
optimal solution (of unknown size) (Virgolin et al.,, 2017).

In this work, we use the IMS as follows.  (i) _Scaling of parameter settings_
: We scale only the population size. For run $R_{i}$, the population size is
set to $n^{\text{pop}}_{i}=2^{i-1}n^{\text{pop}}_{\text{base}}$.  (ii) _Run
termination_ : A run $R_{i}$ is terminated if the fitness of its best solution
is worse than the one of a run $R_{j}$ initialized later, i.e., with $j>i$, or
if it converges to all identical solutions.

Differently from (Virgolin et al.,, 2017) we no longer scale the tree height
$h$ because in SR, and in supervised learning tasks in general, no optimum is
known beforehand, and it is rather desired to find a solution that generalizes
well to unseen examples. Moreover, $h$ bounds the maximum solution size, which
influences interpretability. Hence $h$ is left as a parameter for the user to
set, and we recommend $h\leq 4$ to increase the chance that solutions will be
interpretable (see Sec. 9).

We set the run termination criteria to be based upon the fitness of best
solutions instead of mean population fitness as done by (Harik and Lobo,,
1999) and (Virgolin et al.,, 2017), because in SR it can happen that the error
of a few solutions becomes so large that it compromises the mean population
fitness. This can trigger the termination criteria even if solutions exist
that are competitive with the ones of other runs. Also differently from the
other versions of the IMS, when terminating a run, we do not automatically
terminate all previous runs. Indeed, some runs with smaller parameter settings
may still be very competitive (e.g., due to the fortunate sampling of
particular constants when using ERCs).

We lastly propose to exploit the fact that many runs are performed within the
IMS to tackle a central problem of learning tasks: generalization. Instead of
discarding the best solutions of terminating runs, we store them in an
archive. When the IMS terminates, we re-compute the fitness of each solution
in the archive using a set of examples different from the training set, i.e.
the validation set, and return the new best performing, i.e., the solution
that generalized best. The final test performance is measured on a third,
separate set of examples (test set).

##  8 Benchmarking GP-GOMEA

We compare GP-GOMEA (using the new LT) with tree-based GP with traditional
subtree crossover and subtree mutation (GP-Trad), tree-based GP using the
state-of-the-art, semantic-aware operator Random Desired Operator (GP-RDO)
(Pawlak et al.,, 2015), and Decision Tree for Regression (DTR) (Breiman et
al.,, 1984).

We consider RDO because, as mentioned in the introduction, semantic-aware
operators have been studied with interest in the last years. Several works
either built upon RDO, or used RDO as a baseline for comparison (see, e.g.,
(Chen et al.,, 2018; Pawlak and Krawiec,, 2018; Virgolin et al.,, 2019)). Yet,
consistently large solutions were found. It is interesting to assess how RDO
fares when rather strict solution size limits are enforced. Because of such
limits, we remark we cannot consider another popular set of semantic-aware
operators, i.e., the operators used by Geometric Semantic Genetic Programming
(GSGP) (Moraglio et al.,, 2012). These operators work by stacking entire
solutions together, necessarily causing extremely large solution growth (even
if smart simplifications are attempted (Martins et al.,, 2018)).

We consider DTR because it is considered among the state-of-the-art algorithms
to learn interpretable models (Doshi-Velez and Kim,, 2017; Guidotti et al.,,
2018). We remark that DTR ensembles (e.g., (Breiman,, 2001; Chen and
Guestrin,, 2016)) are typically markedly more accurate than single DTRs, but
are considered not interpretable.

###  8.1 Experimental setup

For the EAs, we use a fixed time limit of $1,000$ seconds555Experiments were
run on an Intel® Xeon® Processor E5-2650 v2.. We choose a time-based
comparison because GP-GOMEA performs more evaluations per generation than
other GP algorithms (up to $2\ell-2$ evaluations per generation with the LT),
and so that the overhead of learning the LT (which does not involve
evaluations) is taken into account.

We consider maximum solution sizes $\ell=15,31,63$ (tree nodes), i.e.
corresponding to $h=3,4,5$ respectively, for full $r$-ary trees. The EAs are
run with a typical fixed population size $n^{\text{pop}}=1000$ and also with
the IMS, considering three values for the number of generations in between
runs $g$: 4, 6, and 8. For the fixed population size, if the population of GP-
GOMEA converges before the time limit, since there is no mutation, it is
randomly re-started. Choices of $g$ between 4 and 8 are standards from
literature (Bouter et al.,, 2017; Virgolin et al.,, 2017).

Our implementation of GP-Trad and GP-RDO mostly follows the one of (Pawlak et
al.,, 2015). The population is initialized with the _Ramped Half-and-Half_
method, with tree height between 2 and $h$. Selection is performed with
tournament of size 7. GP-Trad uses a rate of $0.9$ for subtree crossover, and
of $0.1$ for subtree mutation. GP-RDO uses the population-based library of
subtrees, a rate of $0.9$ for RDO, and of $0.1$ for subtree mutation. Subtree
roots to be variated are chosen with the _uniform depth mutation_ method,
which makes nodes of all depths equally likely to be selected (Pawlak et al.,,
2015). Elitism is ensured by cloning the best solution into the next
generation. All EAs are implemented in C++, and the code is available at:
https://goo.gl/15tMV7.

For GP-Trad we consider two versions, to account for different types of
solution size limitation. In the first version, called GP-Trad$h$, we force
trees to be constrained within a maximum height ($h=3,4$), as done for GP-
GOMEA. This way, we can see which algorithm searches better in the same
representation space. In the second version, GP-Trad$\ell$, we allow more
freedom in tree shape, by only bounding the number of tree nodes. This limit
is set to the maximum number of nodes obtainable in a full $r$-ary tree of
height $h$ ($\ell=15$ for $h=3$, $\ell=31$ for $h=4$). As indicated by
previous literature (Gathercole and Ross,, 1996; Langdon and Poli,, 1997), and
as will be shown later in the results, GP-Trad$\ell$ outperforms GP-Trad$h$.
We found that the same holds also for GP-RDO, and present here only its best
configuration, i.e., a version where the number of tree nodes is limited like
for GP-Trad$\ell$.

We use the Python Scikit-learn implementation of DTR (Pedregosa et al.,,
2011), with 5-fold cross-validation grid-search over the training set to tune
the following hyper-parameters: _splitter_ $\in$ {‘ _best_ ’,‘ _random_ ’};
_max_features_ $\in$ {$\frac{1}{2},\frac{3}{4},1$}; _max_depth_ $\in$
{3,4,5,6} (documentation available at http://goo.gl/hbyFq2). We do not allow
larger depth values because, like for GP solutions, excessively large decision
trees are uninterpretable. The best generalizing model found by cross-
validation is then used on the test set.

Table 7: Median validation and test NMSE of 30 runs with $\ell=15$ for GP-
GOMEA (G), GP-Trad$h$ (T$\ell$), GP-Trad$h$ (T$\ell$), GP-RDO (R) with
$n^{\text{pop}}=1000$ and IMS with $g\in\\{4,6,8\\}$, and DTR. Significance is
assessed within each population scheme w.r.t. GP-GOMEA. The last row reports
the number of times the EA performs significantly better (B) and worse (W)
than GP-GOMEA.

Validation $\ell=15$
---
| $n^{\text{pop}}=1000$ | $\blacktriangle$ $\blacktriangle$ | IMS $g=4$ | $\blacktriangle$ $\blacktriangle$ | IMS $g=6$ | $\blacktriangle$ $\blacktriangle$ | IMS $g=8$ |
$\blacktriangle$ | G | T$h$ | T$\ell$ | R |  | G | T$h$ | T$\ell$ | R |  | G | T$h$ | T$\ell$ | R |  | G | T$h$ | T$\ell$ | R | D
Air |  $\blacktriangle$39.2 $\blacktriangle$ | $\blacktriangle$$40.6$ |  $\blacktriangle$ | $\blacktriangle$$35.0$ | $\blacktriangle$ | $\blacktriangle$$44.0$ |  $\blacktriangle$ |  |  $\blacktriangle$34.7 $\blacktriangle$ | $\blacktriangle$$38.3$ |  $\blacktriangle$ | $\blacktriangle$$31.4$ | $\blacktriangle$ | $\blacktriangle$$42.5$ |  $\blacktriangle$ |  |  $\blacktriangle$34.9 $\blacktriangle$ | $\blacktriangle$$39.7$ |  $\blacktriangle$ | $\blacktriangle$$33.6$ | $\blacktriangle$ | $\blacktriangle$$42.0$ |  $\blacktriangle$ |  |  $\blacktriangle$34.4 $\blacktriangle$ | $\blacktriangle$$39.4$ |  $\blacktriangle$ | $\blacktriangle$$32.0$ | $\blacktriangle$ | $\blacktriangle$$42.3$ |  $\blacktriangle$ | $\blacktriangle$$31.1$ | $\blacktriangle$
Bos |  $\blacktriangle$21.1 $\blacktriangle$ |  $\blacktriangle$$23.4$ | $\blacktriangle$ | $\blacktriangle$$25.3$ |  $\blacktriangle$ | $\blacktriangle$$25.7$ |  $\blacktriangle$ |  |  $\blacktriangle$18.2 $\blacktriangle$ | $\blacktriangle$$21.2$ |  $\blacktriangle$ | $\blacktriangle$$19.0$ |  $\blacktriangle$ | $\blacktriangle$$20.8$ |  $\blacktriangle$ |  |  $\blacktriangle$19.2 $\blacktriangle$ | $\blacktriangle$$21.2$ |  $\blacktriangle$ | $\blacktriangle$$20.4$ | $\blacktriangle$ | $\blacktriangle$$20.9$ |  $\blacktriangle$ |  |  $\blacktriangle$19.4 $\blacktriangle$ | $\blacktriangle$$21.6$ |  $\blacktriangle$ | $\blacktriangle$$19.9$ |  $\blacktriangle$ | $\blacktriangle$$22.5$ |  $\blacktriangle$ | $\blacktriangle$$22.9$ |  $\blacktriangle$
Con |  $\blacktriangle$23.2 $\blacktriangle$ | $\blacktriangle$$25.3$ |  $\blacktriangle$ | $\blacktriangle$$23.4$ | $\blacktriangle$ | $\blacktriangle$$27.0$ |  $\blacktriangle$ |  |  $\blacktriangle$20.3 $\blacktriangle$ | $\blacktriangle$$23.1$ |  $\blacktriangle$ | $\blacktriangle$$19.4$ | $\blacktriangle$ | $\blacktriangle$$26.4$ |  $\blacktriangle$ |  |  $\blacktriangle$20.2 $\blacktriangle$ | $\blacktriangle$$23.3$ |  $\blacktriangle$ | $\blacktriangle$$19.9$ | $\blacktriangle$ | $\blacktriangle$$26.2$ |  $\blacktriangle$ |  |  $\blacktriangle$19.4 $\blacktriangle$ | $\blacktriangle$$23.2$ |  $\blacktriangle$ | $\blacktriangle$$19.3$ | $\blacktriangle$ | $\blacktriangle$$26.9$ |  $\blacktriangle$ | $\blacktriangle$$22.7$ |  $\blacktriangle$
Dow |  $\blacktriangle$26.7 $\blacktriangle$ | $\blacktriangle$$28.5$ |  $\blacktriangle$ | $\blacktriangle$$27.5$ | $\blacktriangle$ | $\blacktriangle$$30.6$ |  $\blacktriangle$ |  |  $\blacktriangle$24.2 $\blacktriangle$ | $\blacktriangle$$26.8$ |  $\blacktriangle$ |  $\blacktriangle$$24.2$ | $\blacktriangle$ | $\blacktriangle$$32.3$ |  $\blacktriangle$ |  |  $\blacktriangle$24.6 $\blacktriangle$ | $\blacktriangle$$26.4$ |  $\blacktriangle$ | $\blacktriangle$$24.8$ |  $\blacktriangle$ | $\blacktriangle$$31.0$ |  $\blacktriangle$ |  |  $\blacktriangle$24.5 $\blacktriangle$ | $\blacktriangle$$26.3$ |  $\blacktriangle$ | $\blacktriangle$$25.2$ |  $\blacktriangle$ | $\blacktriangle$$31.0$ |  $\blacktriangle$ | $\blacktriangle$$30.6$ |  $\blacktriangle$
EnC |  $\blacktriangle$8.72 $\blacktriangle$ | $\blacktriangle$$10.6$ |  $\blacktriangle$ | $\blacktriangle$$7.34$ | $\blacktriangle$ | $\blacktriangle$$11.0$ |  $\blacktriangle$ |  |  $\blacktriangle$5.86 $\blacktriangle$ | $\blacktriangle$$10.2$ |  $\blacktriangle$ | $\blacktriangle$$6.49$ |  $\blacktriangle$ | $\blacktriangle$$10.7$ |  $\blacktriangle$ |  |  $\blacktriangle$6.01 $\blacktriangle$ | $\blacktriangle$$10.3$ |  $\blacktriangle$ | $\blacktriangle$$6.24$ | $\blacktriangle$ | $\blacktriangle$$10.5$ |  $\blacktriangle$ |  |  $\blacktriangle$5.87 $\blacktriangle$ | $\blacktriangle$$10.2$ |  $\blacktriangle$ | $\blacktriangle$$6.10$ |  $\blacktriangle$ | $\blacktriangle$$10.8$ |  $\blacktriangle$ | $\blacktriangle$$4.23$ | $\blacktriangle$
EnH |  $\blacktriangle$4.95 $\blacktriangle$ | $\blacktriangle$$7.45$ |  $\blacktriangle$ | $\blacktriangle$$3.83$ | $\blacktriangle$ | $\blacktriangle$$7.65$ |  $\blacktriangle$ |  |  $\blacktriangle$3.33 $\blacktriangle$ | $\blacktriangle$$7.19$ |  $\blacktriangle$ | $\blacktriangle$$3.74$ |  $\blacktriangle$ | $\blacktriangle$$7.34$ |  $\blacktriangle$ |  |  $\blacktriangle$3.28 $\blacktriangle$ | $\blacktriangle$$7.30$ |  $\blacktriangle$ | $\blacktriangle$$3.76$ |  $\blacktriangle$ |  $\blacktriangle$$7.42$ |  $\blacktriangle$ |  |  $\blacktriangle$3.23 $\blacktriangle$ | $\blacktriangle$$7.24$ |  $\blacktriangle$ | $\blacktriangle$$3.72$ |  $\blacktriangle$ | $\blacktriangle$$7.54$ |  $\blacktriangle$ | $\blacktriangle$$0.43$ | $\blacktriangle$
Tow |  $\blacktriangle$12.9 $\blacktriangle$ | $\blacktriangle$$14.4$ |  $\blacktriangle$ | $\blacktriangle$$13.9$ |  $\blacktriangle$ | $\blacktriangle$$20.1$ |  $\blacktriangle$ |  |  $\blacktriangle$12.8 $\blacktriangle$ | $\blacktriangle$$13.6$ |  $\blacktriangle$ | $\blacktriangle$$13.6$ |  $\blacktriangle$ | $\blacktriangle$$20.5$ |  $\blacktriangle$ |  |  $\blacktriangle$12.7 $\blacktriangle$ | $\blacktriangle$$14.0$ |  $\blacktriangle$ | $\blacktriangle$$13.5$ |  $\blacktriangle$ | $\blacktriangle$$20.4$ |  $\blacktriangle$ |  |  $\blacktriangle$13.0 $\blacktriangle$ |  $\blacktriangle$$14.0$ |  $\blacktriangle$ | $\blacktriangle$$13.4$ |  $\blacktriangle$ | $\blacktriangle$$20.1$ |  $\blacktriangle$ | $\blacktriangle$$11.2$ | $\blacktriangle$
WiR |  $\blacktriangle$65.3 $\blacktriangle$ | $\blacktriangle$$64.8$ | $\blacktriangle$ | $\blacktriangle$$64.9$ | $\blacktriangle$ | $\blacktriangle$$66.5$ |  $\blacktriangle$ |  |  $\blacktriangle$63.9 $\blacktriangle$ | $\blacktriangle$$64.7$ |  $\blacktriangle$ | $\blacktriangle$$64.4$ | $\blacktriangle$ | $\blacktriangle$$65.1$ |  $\blacktriangle$ |  |  $\blacktriangle$63.6 $\blacktriangle$ | $\blacktriangle$$63.9$ |  $\blacktriangle$ | $\blacktriangle$$64.4$ |  $\blacktriangle$ | $\blacktriangle$$64.9$ |  $\blacktriangle$ |  |  $\blacktriangle$63.9 $\blacktriangle$ | $\blacktriangle$$63.9$ |  $\blacktriangle$ | $\blacktriangle$$64.2$ | $\blacktriangle$ | $\blacktriangle$$65.7$ |  $\blacktriangle$ |  $\blacktriangle$$71.7$ |  $\blacktriangle$
WiW |  $\blacktriangle$71.4 $\blacktriangle$ | $\blacktriangle$$71.3$ | $\blacktriangle$ | $\blacktriangle$$70.9$ | $\blacktriangle$ | $\blacktriangle$$72.6$ |  $\blacktriangle$ |  |  $\blacktriangle$70.8 $\blacktriangle$ | $\blacktriangle$$71.2$ |  $\blacktriangle$ | $\blacktriangle$$70.7$ |  $\blacktriangle$ | $\blacktriangle$$72.3$ |  $\blacktriangle$ |  |  $\blacktriangle$70.7 $\blacktriangle$ | $\blacktriangle$$71.5$ |  $\blacktriangle$ | $\blacktriangle$$70.8$ |  $\blacktriangle$ | $\blacktriangle$$72.6$ |  $\blacktriangle$ |  |  $\blacktriangle$71.2 $\blacktriangle$ | $\blacktriangle$$71.4$ |  $\blacktriangle$ | $\blacktriangle$$71.2$ |  $\blacktriangle$ | $\blacktriangle$$72.6$ |  $\blacktriangle$ | $\blacktriangle$$72.2$ |  $\blacktriangle$
Yac |  $\blacktriangle$1.25 $\blacktriangle$ | $\blacktriangle$$1.22$ | $\blacktriangle$ | $\blacktriangle$$0.70$ | $\blacktriangle$ | $\blacktriangle$$0.96$ | $\blacktriangle$ |  |  $\blacktriangle$0.89 $\blacktriangle$ | $\blacktriangle$$1.04$ |  $\blacktriangle$ | $\blacktriangle$$0.61$ | $\blacktriangle$ | $\blacktriangle$$0.67$ | $\blacktriangle$ |  |  $\blacktriangle$0.92 $\blacktriangle$ | $\blacktriangle$$1.01$ |  $\blacktriangle$ | $\blacktriangle$$0.61$ | $\blacktriangle$ | $\blacktriangle$$0.73$ | $\blacktriangle$ |  |  $\blacktriangle$0.95 $\blacktriangle$ | $\blacktriangle$$1.03$ |  $\blacktriangle$ | $\blacktriangle$$0.62$ | $\blacktriangle$ | $\blacktriangle$$0.76$ | $\blacktriangle$ | $\blacktriangle$$0.88$ | $\blacktriangle$
B/W | — | 0/6 | 3/2 | 1/9 |  | — | 0/10 | 3/5 | 1/9 |  | — | 0/10 | 3/5 | 1/9 |  | — | 0/10 | 2/6 | 1/9 | 5/5

Test $\ell=15$ $n^{\text{pop}}=1000$ $\blacktriangle$ $\blacktriangle$ IMS
$g=4$ $\blacktriangle$ $\blacktriangle$ IMS $g=6$ $\blacktriangle$
$\blacktriangle$ IMS $g=8$ $\blacktriangle$ G T$h$ T$\ell$ R G T$h$ T$\ell$ R
G T$h$ T$\ell$ R G T$h$ T$\ell$ R D

Air  $\blacktriangle$38.5 $\blacktriangle$ $\blacktriangle$40.7
$\blacktriangle$ $\blacktriangle$35.3 $\blacktriangle$ $\blacktriangle$44.1
$\blacktriangle$ $\blacktriangle$35.8 $\blacktriangle$ $\blacktriangle$39.5
$\blacktriangle$ $\blacktriangle$32.5 $\blacktriangle$ $\blacktriangle$43.3
$\blacktriangle$ $\blacktriangle$35.2 $\blacktriangle$ $\blacktriangle$39.3
$\blacktriangle$ $\blacktriangle$33.2 $\blacktriangle$ $\blacktriangle$42.4
$\blacktriangle$ $\blacktriangle$35.4 $\blacktriangle$ $\blacktriangle$39.7
$\blacktriangle$ $\blacktriangle$32.8 $\blacktriangle$ $\blacktriangle$42.8
$\blacktriangle$ $\blacktriangle$30.8 $\blacktriangle$ Bos
$\blacktriangle$22.7 $\blacktriangle$ $\blacktriangle$23.3 $\blacktriangle$
$\blacktriangle$24.3 $\blacktriangle$ $\blacktriangle$26.7 $\blacktriangle$
$\blacktriangle$22.5 $\blacktriangle$ $\blacktriangle$23.1 $\blacktriangle$
$\blacktriangle$23.3 $\blacktriangle$ $\blacktriangle$22.9 $\blacktriangle$
$\blacktriangle$21.7 $\blacktriangle$ $\blacktriangle$23.6 $\blacktriangle$
$\blacktriangle$22.6 $\blacktriangle$ $\blacktriangle$25.0 $\blacktriangle$
$\blacktriangle$22.1 $\blacktriangle$ $\blacktriangle$22.5 $\blacktriangle$
$\blacktriangle$23.6 $\blacktriangle$ $\blacktriangle$23.3 $\blacktriangle$
$\blacktriangle$26.1 $\blacktriangle$ Con  $\blacktriangle$23.1
$\blacktriangle$ $\blacktriangle$26.1 $\blacktriangle$ $\blacktriangle$23.9
$\blacktriangle$ $\blacktriangle$27.0 $\blacktriangle$ $\blacktriangle$20.8
$\blacktriangle$ $\blacktriangle$23.9 $\blacktriangle$ $\blacktriangle$19.3
$\blacktriangle$ $\blacktriangle$27.7 $\blacktriangle$ $\blacktriangle$21.2
$\blacktriangle$ $\blacktriangle$23.9 $\blacktriangle$ $\blacktriangle$19.9
$\blacktriangle$ $\blacktriangle$26.4 $\blacktriangle$ $\blacktriangle$20.4
$\blacktriangle$ $\blacktriangle$24.3 $\blacktriangle$ $\blacktriangle$19.3
$\blacktriangle$ $\blacktriangle$27.8 $\blacktriangle$ $\blacktriangle$21.3
$\blacktriangle$ Dow  $\blacktriangle$26.3 $\blacktriangle$
$\blacktriangle$27.5 $\blacktriangle$ $\blacktriangle$26.4 $\blacktriangle$
$\blacktriangle$31.0 $\blacktriangle$ $\blacktriangle$24.8 $\blacktriangle$
$\blacktriangle$26.1 $\blacktriangle$ $\blacktriangle$24.7 $\blacktriangle$
$\blacktriangle$30.7 $\blacktriangle$ $\blacktriangle$24.5 $\blacktriangle$
$\blacktriangle$26.6 $\blacktriangle$ $\blacktriangle$24.5 $\blacktriangle$
$\blacktriangle$30.1 $\blacktriangle$ $\blacktriangle$24.3 $\blacktriangle$
$\blacktriangle$26.8 $\blacktriangle$ $\blacktriangle$25.1 $\blacktriangle$
$\blacktriangle$31.6 $\blacktriangle$ $\blacktriangle$28.0 $\blacktriangle$
EnC  $\blacktriangle$9.72 $\blacktriangle$ $\blacktriangle$11.2
$\blacktriangle$ $\blacktriangle$7.86 $\blacktriangle$ $\blacktriangle$11.8
$\blacktriangle$ $\blacktriangle$6.36 $\blacktriangle$ $\blacktriangle$10.6
$\blacktriangle$ $\blacktriangle$6.80 $\blacktriangle$ $\blacktriangle$11.5
$\blacktriangle$ $\blacktriangle$6.37 $\blacktriangle$ $\blacktriangle$10.5
$\blacktriangle$ $\blacktriangle$6.18 $\blacktriangle$ $\blacktriangle$10.9
$\blacktriangle$ $\blacktriangle$6.02 $\blacktriangle$ $\blacktriangle$10.5
$\blacktriangle$ $\blacktriangle$6.33 $\blacktriangle$ $\blacktriangle$11.7
$\blacktriangle$ $\blacktriangle$4.47 $\blacktriangle$ EnH
$\blacktriangle$5.03 $\blacktriangle$ $\blacktriangle$7.19 $\blacktriangle$
$\blacktriangle$4.04 $\blacktriangle$ $\blacktriangle$7.85 $\blacktriangle$
$\blacktriangle$3.45 $\blacktriangle$ $\blacktriangle$7.57 $\blacktriangle$
$\blacktriangle$3.88 $\blacktriangle$ $\blacktriangle$7.62 $\blacktriangle$
$\blacktriangle$3.28 $\blacktriangle$ $\blacktriangle$7.64 $\blacktriangle$
$\blacktriangle$3.88 $\blacktriangle$ $\blacktriangle$7.59 $\blacktriangle$
$\blacktriangle$3.51 $\blacktriangle$ $\blacktriangle$7.56 $\blacktriangle$
$\blacktriangle$3.86 $\blacktriangle$ $\blacktriangle$7.65 $\blacktriangle$
$\blacktriangle$0.33 $\blacktriangle$ Tow  $\blacktriangle$13.4
$\blacktriangle$ $\blacktriangle$14.4 $\blacktriangle$ $\blacktriangle$13.9
$\blacktriangle$ $\blacktriangle$20.3 $\blacktriangle$ $\blacktriangle$13.0
$\blacktriangle$ $\blacktriangle$14.1 $\blacktriangle$ $\blacktriangle$14.0
$\blacktriangle$ $\blacktriangle$20.8 $\blacktriangle$ $\blacktriangle$12.9
$\blacktriangle$ $\blacktriangle$14.1 $\blacktriangle$ $\blacktriangle$13.7
$\blacktriangle$ $\blacktriangle$20.7 $\blacktriangle$ $\blacktriangle$13.0
$\blacktriangle$ $\blacktriangle$14.3 $\blacktriangle$ $\blacktriangle$13.3
$\blacktriangle$ $\blacktriangle$20.5 $\blacktriangle$ $\blacktriangle$11.2
$\blacktriangle$ WiR  $\blacktriangle$63.1 $\blacktriangle$
$\blacktriangle$63.7 $\blacktriangle$ $\blacktriangle$62.4 $\blacktriangle$
$\blacktriangle$64.6 $\blacktriangle$ $\blacktriangle$63.3 $\blacktriangle$
$\blacktriangle$63.4 $\blacktriangle$ $\blacktriangle$63.2 $\blacktriangle$
$\blacktriangle$64.4 $\blacktriangle$ $\blacktriangle$63.6 $\blacktriangle$
$\blacktriangle$63.5 $\blacktriangle$ $\blacktriangle$63.2 $\blacktriangle$
$\blacktriangle$64.3 $\blacktriangle$ $\blacktriangle$63.4 $\blacktriangle$
$\blacktriangle$63.8 $\blacktriangle$ $\blacktriangle$63.3 $\blacktriangle$
$\blacktriangle$63.7 $\blacktriangle$ $\blacktriangle$72.6 $\blacktriangle$
WiW  $\blacktriangle$70.5 $\blacktriangle$ $\blacktriangle$70.5
$\blacktriangle$ $\blacktriangle$70.1 $\blacktriangle$ $\blacktriangle$71.3
$\blacktriangle$ $\blacktriangle$70.4 $\blacktriangle$ $\blacktriangle$70.0
$\blacktriangle$ $\blacktriangle$70.3 $\blacktriangle$ $\blacktriangle$71.6
$\blacktriangle$ $\blacktriangle$69.7 $\blacktriangle$ $\blacktriangle$70.5
$\blacktriangle$ $\blacktriangle$70.1 $\blacktriangle$ $\blacktriangle$71.0
$\blacktriangle$ $\blacktriangle$70.2 $\blacktriangle$ $\blacktriangle$70.5
$\blacktriangle$ $\blacktriangle$70.3 $\blacktriangle$ $\blacktriangle$71.8
$\blacktriangle$ $\blacktriangle$72.2 $\blacktriangle$ Yac
$\blacktriangle$1.23 $\blacktriangle$ $\blacktriangle$1.23 $\blacktriangle$
$\blacktriangle$0.78 $\blacktriangle$ $\blacktriangle$0.95 $\blacktriangle$
$\blacktriangle$1.16 $\blacktriangle$ $\blacktriangle$1.24 $\blacktriangle$
$\blacktriangle$0.73 $\blacktriangle$ $\blacktriangle$0.77 $\blacktriangle$
$\blacktriangle$1.17 $\blacktriangle$ $\blacktriangle$1.24 $\blacktriangle$
$\blacktriangle$0.73 $\blacktriangle$ $\blacktriangle$0.77 $\blacktriangle$
$\blacktriangle$1.17 $\blacktriangle$ $\blacktriangle$1.23 $\blacktriangle$
$\blacktriangle$0.71 $\blacktriangle$ $\blacktriangle$0.86 $\blacktriangle$
$\blacktriangle$0.91 $\blacktriangle$ B/W — 0/8 4/2 1/9 — 0/8 4/5 1/9 — 0/8
4/4 1/9 — 0/9 3/5 1/9 5/5

Table 8: Median validation and test NMSE of 30 runs with $\ell=31$. Details as
in Table 8.1.

Validation $\ell=31$
---
| $n^{\text{pop}}=1000$ | $\blacktriangle$ $\blacktriangle$ | IMS $g=4$ | $\blacktriangle$ $\blacktriangle$ | IMS $g=6$ | $\blacktriangle$ $\blacktriangle$ | IMS $g=8$ |
$\blacktriangle$ | G | T$h$ | T$\ell$ | R |  | G | T$h$ | T$\ell$ | R |  | G | T$h$ | T$\ell$ | R |  | G | T$h$ | T$\ell$ | R | D
Air |  $\blacktriangle$26.4 $\blacktriangle$ | $\blacktriangle$$33.8$ |  $\blacktriangle$ | $\blacktriangle$$32.1$ |  $\blacktriangle$ | $\blacktriangle$$36.0$ |  $\blacktriangle$ |  |  $\blacktriangle$24.9 $\blacktriangle$ | $\blacktriangle$$25.9$ |  $\blacktriangle$ | $\blacktriangle$$23.2$ | $\blacktriangle$ | $\blacktriangle$$37.0$ |  $\blacktriangle$ |  |  $\blacktriangle$25.0 $\blacktriangle$ | $\blacktriangle$$27.1$ |  $\blacktriangle$ | $\blacktriangle$$24.9$ | $\blacktriangle$ | $\blacktriangle$$37.6$ |  $\blacktriangle$ |  |  $\blacktriangle$24.8 $\blacktriangle$ | $\blacktriangle$$28.4$ |  $\blacktriangle$ | $\blacktriangle$$24.8$ | $\blacktriangle$ | $\blacktriangle$$37.1$ |  $\blacktriangle$ | $\blacktriangle$$31.1$ |  $\blacktriangle$
Bos |  $\blacktriangle$22.3 $\blacktriangle$ |  $\blacktriangle$$21.1$ | $\blacktriangle$ | $\blacktriangle$$19.2$ | $\blacktriangle$ | $\blacktriangle$$24.8$ |  $\blacktriangle$ |  |  $\blacktriangle$16.7 $\blacktriangle$ | $\blacktriangle$$18.8$ |  $\blacktriangle$ | $\blacktriangle$$16.2$ |  $\blacktriangle$ | $\blacktriangle$$20.4$ |  $\blacktriangle$ |  |  $\blacktriangle$17.4 $\blacktriangle$ | $\blacktriangle$$18.3$ |  $\blacktriangle$ | $\blacktriangle$$17.3$ |  $\blacktriangle$ | $\blacktriangle$$20.6$ |  $\blacktriangle$ |  |  $\blacktriangle$17.3 $\blacktriangle$ | $\blacktriangle$$18.4$ |  $\blacktriangle$ | $\blacktriangle$$17.6$ |  $\blacktriangle$ | $\blacktriangle$$20.4$ |  $\blacktriangle$ | $\blacktriangle$$22.9$ |  $\blacktriangle$
Con |  $\blacktriangle$17.3 $\blacktriangle$ | $\blacktriangle$$18.6$ |  $\blacktriangle$ | $\blacktriangle$$17.9$ |  $\blacktriangle$ | $\blacktriangle$$20.8$ |  $\blacktriangle$ |  |  $\blacktriangle$16.0 $\blacktriangle$ | $\blacktriangle$$17.6$ |  $\blacktriangle$ | $\blacktriangle$$16.7$ |  $\blacktriangle$ | $\blacktriangle$$20.5$ |  $\blacktriangle$ |  |  $\blacktriangle$16.6 $\blacktriangle$ | $\blacktriangle$$18.1$ |  $\blacktriangle$ | $\blacktriangle$$16.4$ |  $\blacktriangle$ | $\blacktriangle$$20.1$ |  $\blacktriangle$ |  |  $\blacktriangle$16.1 $\blacktriangle$ | $\blacktriangle$$18.3$ |  $\blacktriangle$ | $\blacktriangle$$17.2$ |  $\blacktriangle$ | $\blacktriangle$$20.2$ |  $\blacktriangle$ | $\blacktriangle$$22.7$ |  $\blacktriangle$
Dow |  $\blacktriangle$21.3 $\blacktriangle$ | $\blacktriangle$$22.6$ |  $\blacktriangle$ | $\blacktriangle$$22.6$ | $\blacktriangle$ | $\blacktriangle$$24.3$ |  $\blacktriangle$ |  |  $\blacktriangle$19.4 $\blacktriangle$ | $\blacktriangle$$21.6$ |  $\blacktriangle$ |  $\blacktriangle$$19.2$ | $\blacktriangle$ | $\blacktriangle$$25.6$ |  $\blacktriangle$ |  |  $\blacktriangle$19.4 $\blacktriangle$ | $\blacktriangle$$21.2$ |  $\blacktriangle$ | $\blacktriangle$$19.4$ |  $\blacktriangle$ | $\blacktriangle$$25.4$ |  $\blacktriangle$ |  |  $\blacktriangle$19.2 $\blacktriangle$ | $\blacktriangle$$21.9$ |  $\blacktriangle$ | $\blacktriangle$$20.1$ |  $\blacktriangle$ | $\blacktriangle$$25.8$ |  $\blacktriangle$ | $\blacktriangle$$30.6$ |  $\blacktriangle$
EnC |  $\blacktriangle$5.14 $\blacktriangle$ | $\blacktriangle$$5.60$ |  $\blacktriangle$ | $\blacktriangle$$4.99$ | $\blacktriangle$ | $\blacktriangle$$7.62$ |  $\blacktriangle$ |  |  $\blacktriangle$4.62 $\blacktriangle$ | $\blacktriangle$$5.51$ |  $\blacktriangle$ | $\blacktriangle$$4.82$ |  $\blacktriangle$ | $\blacktriangle$$8.04$ |  $\blacktriangle$ |  |  $\blacktriangle$4.35 $\blacktriangle$ | $\blacktriangle$$6.04$ |  $\blacktriangle$ | $\blacktriangle$$4.56$ |  $\blacktriangle$ | $\blacktriangle$$8.48$ |  $\blacktriangle$ |  |  $\blacktriangle$4.37 $\blacktriangle$ | $\blacktriangle$$5.65$ |  $\blacktriangle$ | $\blacktriangle$$4.73$ |  $\blacktriangle$ | $\blacktriangle$$7.81$ |  $\blacktriangle$ | $\blacktriangle$$4.23$ | $\blacktriangle$
EnH |  $\blacktriangle$2.29 $\blacktriangle$ | $\blacktriangle$$2.54$ |  $\blacktriangle$ | $\blacktriangle$$1.75$ | $\blacktriangle$ | $\blacktriangle$$6.21$ |  $\blacktriangle$ |  |  $\blacktriangle$1.95 $\blacktriangle$ | $\blacktriangle$$3.05$ |  $\blacktriangle$ | $\blacktriangle$$1.72$ | $\blacktriangle$ | $\blacktriangle$$4.97$ |  $\blacktriangle$ |  |  $\blacktriangle$2.00 $\blacktriangle$ | $\blacktriangle$$2.84$ |  $\blacktriangle$ | $\blacktriangle$$1.65$ | $\blacktriangle$ |  $\blacktriangle$$5.93$ |  $\blacktriangle$ |  |  $\blacktriangle$1.88 $\blacktriangle$ | $\blacktriangle$$3.10$ |  $\blacktriangle$ | $\blacktriangle$$1.62$ | $\blacktriangle$ | $\blacktriangle$$6.11$ |  $\blacktriangle$ | $\blacktriangle$$0.43$ | $\blacktriangle$
Tow |  $\blacktriangle$12.0 $\blacktriangle$ | $\blacktriangle$$13.0$ |  $\blacktriangle$ | $\blacktriangle$$12.6$ |  $\blacktriangle$ | $\blacktriangle$$17.5$ |  $\blacktriangle$ |  |  $\blacktriangle$11.8 $\blacktriangle$ | $\blacktriangle$$12.3$ |  $\blacktriangle$ | $\blacktriangle$$11.9$ | $\blacktriangle$ | $\blacktriangle$$17.8$ |  $\blacktriangle$ |  |  $\blacktriangle$11.7 $\blacktriangle$ | $\blacktriangle$$12.2$ |  $\blacktriangle$ | $\blacktriangle$$12.2$ |  $\blacktriangle$ | $\blacktriangle$$16.6$ |  $\blacktriangle$ |  |  $\blacktriangle$12.0 $\blacktriangle$ |  $\blacktriangle$$12.4$ |  $\blacktriangle$ | $\blacktriangle$$11.8$ | $\blacktriangle$ | $\blacktriangle$$17.6$ |  $\blacktriangle$ | $\blacktriangle$$11.2$ | $\blacktriangle$
WiR |  $\blacktriangle$64.2 $\blacktriangle$ | $\blacktriangle$$64.7$ |  $\blacktriangle$ | $\blacktriangle$$64.7$ |  $\blacktriangle$ | $\blacktriangle$$65.9$ |  $\blacktriangle$ |  |  $\blacktriangle$62.8 $\blacktriangle$ | $\blacktriangle$$62.4$ |  $\blacktriangle$ | $\blacktriangle$$62.6$ | $\blacktriangle$ | $\blacktriangle$$64.5$ |  $\blacktriangle$ |  |  $\blacktriangle$62.3 $\blacktriangle$ | $\blacktriangle$$63.6$ |  $\blacktriangle$ | $\blacktriangle$$62.1$ | $\blacktriangle$ | $\blacktriangle$$64.1$ |  $\blacktriangle$ |  |  $\blacktriangle$62.6 $\blacktriangle$ | $\blacktriangle$$62.9$ |  $\blacktriangle$ | $\blacktriangle$$61.8$ | $\blacktriangle$ | $\blacktriangle$$64.6$ |  $\blacktriangle$ |  $\blacktriangle$$71.7$ |  $\blacktriangle$
WiW |  $\blacktriangle$70.2 $\blacktriangle$ | $\blacktriangle$$70.4$ |  $\blacktriangle$ | $\blacktriangle$$70.9$ | $\blacktriangle$ | $\blacktriangle$$71.4$ |  $\blacktriangle$ |  |  $\blacktriangle$69.6 $\blacktriangle$ | $\blacktriangle$$69.7$ | $\blacktriangle$ | $\blacktriangle$$69.7$ | $\blacktriangle$ | $\blacktriangle$$71.1$ |  $\blacktriangle$ |  |  $\blacktriangle$70.0 $\blacktriangle$ | $\blacktriangle$$70.2$ |  $\blacktriangle$ | $\blacktriangle$$70.0$ | $\blacktriangle$ | $\blacktriangle$$71.0$ |  $\blacktriangle$ |  |  $\blacktriangle$70.0 $\blacktriangle$ | $\blacktriangle$$70.1$ |  $\blacktriangle$ | $\blacktriangle$$69.6$ | $\blacktriangle$ | $\blacktriangle$$71.2$ |  $\blacktriangle$ | $\blacktriangle$$72.2$ |  $\blacktriangle$
Yac |  $\blacktriangle$0.46 $\blacktriangle$ | $\blacktriangle$$0.59$ |  $\blacktriangle$ | $\blacktriangle$$0.42$ | $\blacktriangle$ | $\blacktriangle$$0.57$ |  $\blacktriangle$ |  |  $\blacktriangle$0.37 $\blacktriangle$ | $\blacktriangle$$0.51$ |  $\blacktriangle$ | $\blacktriangle$$0.40$ |  $\blacktriangle$ | $\blacktriangle$$0.59$ |  $\blacktriangle$ |  |  $\blacktriangle$0.38 $\blacktriangle$ | $\blacktriangle$$0.56$ |  $\blacktriangle$ | $\blacktriangle$$0.38$ | $\blacktriangle$ | $\blacktriangle$$0.54$ |  $\blacktriangle$ |  |  $\blacktriangle$0.40 $\blacktriangle$ | $\blacktriangle$$0.54$ |  $\blacktriangle$ | $\blacktriangle$$0.42$ |  $\blacktriangle$ | $\blacktriangle$$0.52$ |  $\blacktriangle$ | $\blacktriangle$$0.88$ |  $\blacktriangle$
B/W | — | 0/9 | 3/4 | 0/10 |  | — | 0/9 | 2/4 | 0/10 |  | — | 0/10 | 1/5 | 0/10 |  | — | 0/10 | 0/5 | 0/10 | 3/7

Test $\ell=31$ $n^{\text{pop}}=1000$ $\blacktriangle$ $\blacktriangle$ IMS
$g=4$ $\blacktriangle$ $\blacktriangle$ IMS $g=6$ $\blacktriangle$
$\blacktriangle$ IMS $g=8$ $\blacktriangle$ G T$h$ T$\ell$ R G T$h$ T$\ell$ R
G T$h$ T$\ell$ R G T$h$ T$\ell$ R D

Air  $\blacktriangle$26.4 $\blacktriangle$ $\blacktriangle$33.5
$\blacktriangle$ $\blacktriangle$30.8 $\blacktriangle$ $\blacktriangle$37.1
$\blacktriangle$ $\blacktriangle$25.9 $\blacktriangle$ $\blacktriangle$26.5
$\blacktriangle$ $\blacktriangle$23.3 $\blacktriangle$ $\blacktriangle$37.6
$\blacktriangle$ $\blacktriangle$24.9 $\blacktriangle$ $\blacktriangle$27.1
$\blacktriangle$ $\blacktriangle$24.7 $\blacktriangle$ $\blacktriangle$39.2
$\blacktriangle$ $\blacktriangle$24.9 $\blacktriangle$ $\blacktriangle$28.8
$\blacktriangle$ $\blacktriangle$26.1 $\blacktriangle$ $\blacktriangle$38.2
$\blacktriangle$ $\blacktriangle$30.8 $\blacktriangle$ Bos
$\blacktriangle$21.4 $\blacktriangle$ $\blacktriangle$22.8 $\blacktriangle$
$\blacktriangle$21.6 $\blacktriangle$ $\blacktriangle$26.2 $\blacktriangle$
$\blacktriangle$20.1 $\blacktriangle$ $\blacktriangle$21.3 $\blacktriangle$
$\blacktriangle$21.8 $\blacktriangle$ $\blacktriangle$23.4 $\blacktriangle$
$\blacktriangle$20.9 $\blacktriangle$ $\blacktriangle$21.2 $\blacktriangle$
$\blacktriangle$22.2 $\blacktriangle$ $\blacktriangle$23.2 $\blacktriangle$
$\blacktriangle$20.2 $\blacktriangle$ $\blacktriangle$22.3 $\blacktriangle$
$\blacktriangle$22.6 $\blacktriangle$ $\blacktriangle$26.0 $\blacktriangle$
$\blacktriangle$26.1 $\blacktriangle$ Con  $\blacktriangle$17.6
$\blacktriangle$ $\blacktriangle$18.7 $\blacktriangle$ $\blacktriangle$17.8
$\blacktriangle$ $\blacktriangle$21.5 $\blacktriangle$ $\blacktriangle$16.9
$\blacktriangle$ $\blacktriangle$18.1 $\blacktriangle$ $\blacktriangle$17.1
$\blacktriangle$ $\blacktriangle$21.2 $\blacktriangle$ $\blacktriangle$16.7
$\blacktriangle$ $\blacktriangle$18.8 $\blacktriangle$ $\blacktriangle$16.9
$\blacktriangle$ $\blacktriangle$21.1 $\blacktriangle$ $\blacktriangle$17.2
$\blacktriangle$ $\blacktriangle$18.3 $\blacktriangle$ $\blacktriangle$17.0
$\blacktriangle$ $\blacktriangle$21.5 $\blacktriangle$ $\blacktriangle$21.3
$\blacktriangle$ Dow  $\blacktriangle$20.3 $\blacktriangle$
$\blacktriangle$21.9 $\blacktriangle$ $\blacktriangle$22.2 $\blacktriangle$
$\blacktriangle$24.4 $\blacktriangle$ $\blacktriangle$19.2 $\blacktriangle$
$\blacktriangle$20.7 $\blacktriangle$ $\blacktriangle$19.1 $\blacktriangle$
$\blacktriangle$24.4 $\blacktriangle$ $\blacktriangle$18.9 $\blacktriangle$
$\blacktriangle$21.4 $\blacktriangle$ $\blacktriangle$18.6 $\blacktriangle$
$\blacktriangle$24.4 $\blacktriangle$ $\blacktriangle$18.7 $\blacktriangle$
$\blacktriangle$22.2 $\blacktriangle$ $\blacktriangle$20.2 $\blacktriangle$
$\blacktriangle$25.5 $\blacktriangle$ $\blacktriangle$28.0 $\blacktriangle$
EnC  $\blacktriangle$5.28 $\blacktriangle$ $\blacktriangle$5.91
$\blacktriangle$ $\blacktriangle$4.76 $\blacktriangle$ $\blacktriangle$7.00
$\blacktriangle$ $\blacktriangle$4.43 $\blacktriangle$ $\blacktriangle$5.76
$\blacktriangle$ $\blacktriangle$4.79 $\blacktriangle$ $\blacktriangle$7.69
$\blacktriangle$ $\blacktriangle$4.44 $\blacktriangle$ $\blacktriangle$6.05
$\blacktriangle$ $\blacktriangle$4.71 $\blacktriangle$ $\blacktriangle$8.73
$\blacktriangle$ $\blacktriangle$4.60 $\blacktriangle$ $\blacktriangle$5.62
$\blacktriangle$ $\blacktriangle$4.77 $\blacktriangle$ $\blacktriangle$7.94
$\blacktriangle$ $\blacktriangle$4.47 $\blacktriangle$ EnH
$\blacktriangle$2.29 $\blacktriangle$ $\blacktriangle$2.49 $\blacktriangle$
$\blacktriangle$1.83 $\blacktriangle$ $\blacktriangle$5.98 $\blacktriangle$
$\blacktriangle$2.05 $\blacktriangle$ $\blacktriangle$3.20 $\blacktriangle$
$\blacktriangle$1.58 $\blacktriangle$ $\blacktriangle$5.12 $\blacktriangle$
$\blacktriangle$2.10 $\blacktriangle$ $\blacktriangle$3.07 $\blacktriangle$
$\blacktriangle$1.75 $\blacktriangle$ $\blacktriangle$5.77 $\blacktriangle$
$\blacktriangle$2.00 $\blacktriangle$ $\blacktriangle$2.91 $\blacktriangle$
$\blacktriangle$1.55 $\blacktriangle$ $\blacktriangle$6.51 $\blacktriangle$
$\blacktriangle$0.33 $\blacktriangle$ Tow  $\blacktriangle$12.2
$\blacktriangle$ $\blacktriangle$13.2 $\blacktriangle$ $\blacktriangle$13.1
$\blacktriangle$ $\blacktriangle$18.7 $\blacktriangle$ $\blacktriangle$12.1
$\blacktriangle$ $\blacktriangle$12.6 $\blacktriangle$ $\blacktriangle$12.0
$\blacktriangle$ $\blacktriangle$18.2 $\blacktriangle$ $\blacktriangle$12.1
$\blacktriangle$ $\blacktriangle$12.4 $\blacktriangle$ $\blacktriangle$12.3
$\blacktriangle$ $\blacktriangle$16.8 $\blacktriangle$ $\blacktriangle$12.2
$\blacktriangle$ $\blacktriangle$12.7 $\blacktriangle$ $\blacktriangle$12.0
$\blacktriangle$ $\blacktriangle$17.2 $\blacktriangle$ $\blacktriangle$11.2
$\blacktriangle$ WiR  $\blacktriangle$62.1 $\blacktriangle$
$\blacktriangle$63.1 $\blacktriangle$ $\blacktriangle$62.1 $\blacktriangle$
$\blacktriangle$63.5 $\blacktriangle$ $\blacktriangle$62.7 $\blacktriangle$
$\blacktriangle$63.1 $\blacktriangle$ $\blacktriangle$61.9 $\blacktriangle$
$\blacktriangle$63.9 $\blacktriangle$ $\blacktriangle$62.4 $\blacktriangle$
$\blacktriangle$62.9 $\blacktriangle$ $\blacktriangle$63.3 $\blacktriangle$
$\blacktriangle$64.2 $\blacktriangle$ $\blacktriangle$61.9 $\blacktriangle$
$\blacktriangle$63.0 $\blacktriangle$ $\blacktriangle$62.9 $\blacktriangle$
$\blacktriangle$63.4 $\blacktriangle$ $\blacktriangle$72.6 $\blacktriangle$
WiW  $\blacktriangle$69.0 $\blacktriangle$ $\blacktriangle$69.7
$\blacktriangle$ $\blacktriangle$69.8 $\blacktriangle$ $\blacktriangle$70.2
$\blacktriangle$ $\blacktriangle$69.4 $\blacktriangle$ $\blacktriangle$69.3
$\blacktriangle$ $\blacktriangle$69.2 $\blacktriangle$ $\blacktriangle$70.6
$\blacktriangle$ $\blacktriangle$69.1 $\blacktriangle$ $\blacktriangle$69.4
$\blacktriangle$ $\blacktriangle$69.2 $\blacktriangle$ $\blacktriangle$70.7
$\blacktriangle$ $\blacktriangle$69.1 $\blacktriangle$ $\blacktriangle$69.6
$\blacktriangle$ $\blacktriangle$69.3 $\blacktriangle$ $\blacktriangle$70.5
$\blacktriangle$ $\blacktriangle$72.2 $\blacktriangle$ Yac
$\blacktriangle$0.52 $\blacktriangle$ $\blacktriangle$0.66 $\blacktriangle$
$\blacktriangle$0.49 $\blacktriangle$ $\blacktriangle$0.66 $\blacktriangle$
$\blacktriangle$0.50 $\blacktriangle$ $\blacktriangle$0.58 $\blacktriangle$
$\blacktriangle$0.47 $\blacktriangle$ $\blacktriangle$0.67 $\blacktriangle$
$\blacktriangle$0.50 $\blacktriangle$ $\blacktriangle$0.64 $\blacktriangle$
$\blacktriangle$0.48 $\blacktriangle$ $\blacktriangle$0.63 $\blacktriangle$
$\blacktriangle$0.53 $\blacktriangle$ $\blacktriangle$0.63 $\blacktriangle$
$\blacktriangle$0.48 $\blacktriangle$ $\blacktriangle$0.70 $\blacktriangle$
$\blacktriangle$0.91 $\blacktriangle$ B/W — 0/8 3/6 0/10 — 0/8 3/3 0/10 — 0/10
2/3 0/10 — 0/10 2/4 0/10 3/7

###  8.2 Results: benchmarking GP-GOMEA

We consider validation and test NMSE. We now show validation rather than
training error because the IMS returns the solution which better generalizes
to the validation set among the ones found by different runs (same for DTR due
to cross-validation). Tables 8.1, 8.1, and 8.2 show the results for maximum
sizes $\ell=15,31,63$ ($h=3,4,5$) respectively. On each set of results, the
Friedman test reveals significant differences among the algorithms. As we are
only interested in benchmarking GP-GOMEA, we test whether significant
performance differences exist only between GP-GOMEA and the other algorithms
(with Bonferroni-corrected Wilcoxon signed-rank test).

We begin with some general results. Overall, error magnitudes are lower for
larger values of $\ell$. This is not surprising: limiting solution size limits
the complexity of relationships that can be modeled. Another general result is
that errors on validation and test set are generally close. Likely, the
validation data is a sufficiently accurate surrogate of the test data in these
datasets, and solution size limitations make over-fitting unlikely. Finally,
note that the results for DTR are the same in all tables.

We now compare GP-GOMEA with GP-Trad$h$, focusing on statistical significance
tests (see rows “B/W” of the tables), over all size limit configurations.
Recall that these two algorithms work with the same type of limitation, i.e.,
based on maximum tree height. No matter the population sizing method, GP-GOMEA
is almost always significantly better than GP-Trad$h$. GP-GOMEA relies on the
LT with improved linkage learning, which we showed to be superior to using the
RT, i.e., blind variation, in the previous series of experiments (Sec. 5.3,
6.1). Subtree crossover and subtree mutation are blind as well, and can only
swap subtrees, which may be a limitation.

GP-GOMEA and GP-Trad$\ell$ are compared next. Recall that GP-Trad$\ell$ is
allowed to evolve any tree shape, as long as the limit in number of nodes is
respected. Having this extra freedom, GP-Trad$\ell$ performs better than GP-
Trad$h$ (not explicitly reported in the tables), which confirms previous
literature results (Gathercole and Ross,, 1996; Langdon and Poli,, 1997). No
marked difference exists between GP-GOMEA and GP-Trad$\ell$ along different
configurations. By counting the number of times one EA is found to be
significantly better than the other along _all_ 240 comparisons, GP-GOMEA
beats GP-Trad$\ell$ by a small margin: 87 significantly lower error
distributions vs. 65 (88 draws).

For the traditional use of a single population ($n^{\text{pop}}=1000$), GP-
Trad$\ell$ is slightly better than GP-GOMEA for $\ell=15$ (Table 8.1),
slightly worse for $\ell=31$ (Table 8.1), and similar for $\ell=63$ (Table
8.2), on both validation and test errors. The performance of the two (and also
of the other EAs) improves when using the IMS. Although not explicitly shown
in the tables, using the IMS is typically significantly better than not using
it. When using a single fixed population size and a single run, only a single
best-found solution is found. Depending on the configuration of that run, in
particular the size of the population, that final solution may be underfitted
or overfitted. When using a scheme such as the IMS, multiple solutions are
marked best in the different interleaved runs. These solutions can
subsequently be compared more in terms of generalization merits, i.e., by
observing the associated performance on the validation set. The best
performing solution can then ultimately be returned. Essentially, this thus
provides a means to mitigate to some extent the problem of underfitting or
overfitting. It should be noted, however, that the extent to which the setup
of the IMS, particularly in terms of growing population sizes, contributes to
this is not immediately clear. This could be studied by comparing with a
scheme in which multiple runs are also performed, but all with a single
population size. The final results of these runs can then also first be tested
against the validation set. Likely, the use of a scheme like the IMS has an
advantage because multiple population sizes will be tried. Therefore, likely a
larger variety of results will be produced to test against the validation set,
but a closer examination of this impact is left for future work.

The comparisons between GP-Trad$\ell$ and GP-GOMEA tend to shift in favor of
the latter when using the IMS, particularly for larger values of $g$. For
$g=4$, outcomes are still overall mixed along different $\ell$ limits. For
$g=8$, GP-GOMEA is preferable, with moderately more significant wins for
$\ell=15$, several more wins for $\ell=31$, and slightly more wins for
$\ell=63$.

To investigate further the comparison between GP-GOMEA and GP-Trad$\ell$, we
consider the effect of $g$ of the IMS for $\ell=31$ (similar results are found
for the other size limits). Figure 7 shows the median maximum population size
reached by the IMS for different values of $g$ in GP-GOMEA and GP-Trad$\ell$.
As can be expected, the bigger $g$, the less runs and the smaller populations
at play. GP-Trad$\ell$ reaches much bigger population sizes than GP-GOMEA when
$g=4$ (on average 3 times bigger). This is because GP-Trad$\ell$ executes
generations much faster than GP-GOMEA: it does not learn a linkage model, and
performs $n^{\text{pop}}$ evaluations per generation. GP-GOMEA performs
$(2\ell-2)n^{\text{pop}}$ variation steps (size of LT excluding its root times
the population size) and up to $(2\ell-2)n^{\text{pop}}$ evaluations per
generation (only meaningful variation steps are evaluated).

Max population size |
---|---
|  Time
Figure 7: Maximum population size reached (vertical axis) in time (seconds,
horizontal axis) with the IMS for GP-GOMEA ($h=4$ limit) and GP-Trad$\ell$
($\ell=31$ limit), for $g\in\\{4,6,8\\}$. The median among problems and
repetitions is shown.

GP-Trad$\ell$ performs well for small values of $g$ due to huge populations
being instantiated with trees of various shape, i.e., expensive random search.
Note that this behavior may be problematic when limited memory is available,
especially if caching mechanisms are desirable to reduce the number of
expensive evaluations (e.g., caching the output of each node as in (Pawlak et
al.,, 2015; Virgolin et al.,, 2017)). On the other hand, GP-GOMEA works fairly
well with much smaller populations, as long as they are big enough to enable
effective linkage learning (the fixed $n^{\text{pop}}=1000$ is smaller than
the population sizes reached with the IMS). Despite the disadvantage of
adhering to a specific tree shape, GP-GOMEA is typically preferable than GP-
Trad$\ell$ for larger values of $g$. Furthermore, Figure 7 shows that GP-GOMEA
population scaling behaves sensibly w.r.t. $g$, i.e., it does not grow
abruptly when $g$ becomes small, nor shrink excessively when $g$ becomes
larger. This latter aspect is because in GP-GOMEA populations ultimately
converge to a same solution, and are terminated, allowing for bigger runs to
start. In GP-Trad$\ell$ this is unlikely to happen, because of the use of
mutation and stochastic (tournament) selection, stalling the IMS. For the
larger $g=8$, GP-GOMEA reaches on average 1.6 times bigger populations than
GP-Trad$\ell$.

GP-RDO, although allowed to evolve trees of different shape like GP-
Trad$\ell$, performs poorly on all problems, with all settings. It performs
significantly worse than GP-GOMEA almost everywhere (it is also worse than GP-
Trad$\ell$). It is known that GP-RDO normally finds big solutions, and it is
also reasonable to expect that it needs big solutions to work well, e.g., to
build a large set of diverse subtrees for the internal library queried by RDO
(Virgolin et al.,, 2019). The strict size limitation basically breaks GP-RDO.
However, we remark that this EA was never designed to work under these
circumstances. In fact, when solution size is not strictly limited, GP-RDO
achieves excellent performance (Pawlak et al.,, 2015).

DTR is compared with GP-GOMEA using the IMS with $g=8$. Although GP-GOMEA is
not optimized (e.g., by tuning the function set), it performs on par with
tuned DTR for $\ell=15$, and better for $\ell=31,63$, on both validation and
test sets. Where one algorithm outperforms the other, the magnitude of
difference in errors are relatively large compared to the ones between EAs.
This is because GP and DTR synthesize models of completely different nature
(decision trees only use if-then-else statements).

Table 9: Median validation and test NMSE of 30 runs with $\ell=63$. Details as
in Table 8.1.

Validation $\ell=63$
---
| $n^{\text{pop}}=1000$ | $\blacktriangle$ $\blacktriangle$ | IMS $g=4$ | $\blacktriangle$ $\blacktriangle$ | IMS $g=6$ | $\blacktriangle$ $\blacktriangle$ | IMS $g=8$ |
$\blacktriangle$ | G | T$h$ | T$\ell$ | R |  | G | T$h$ | T$\ell$ | R |  | G | T$h$ | T$\ell$ | R |  | G | T$h$ | T$\ell$ | R | D
Air |  $\blacktriangle$22.6 $\blacktriangle$ | $\blacktriangle$$25.3$ |  $\blacktriangle$ | $\blacktriangle$$25.0$ |  $\blacktriangle$ | $\blacktriangle$$33.0$ |  $\blacktriangle$ |  |  $\blacktriangle$20.6 $\blacktriangle$ | $\blacktriangle$$22.4$ |  $\blacktriangle$ | $\blacktriangle$$20.8$ | $\blacktriangle$ | $\blacktriangle$$35.1$ |  $\blacktriangle$ |  |  $\blacktriangle$20.7 $\blacktriangle$ | $\blacktriangle$$23.3$ |  $\blacktriangle$ | $\blacktriangle$$21.3$ |  $\blacktriangle$ | $\blacktriangle$$34.3$ |  $\blacktriangle$ |  |  $\blacktriangle$20.8 $\blacktriangle$ | $\blacktriangle$$24.5$ |  $\blacktriangle$ | $\blacktriangle$$20.1$ | $\blacktriangle$ | $\blacktriangle$$34.2$ |  $\blacktriangle$ | $\blacktriangle$$31.1$ |  $\blacktriangle$
Bos |  $\blacktriangle$21.1 $\blacktriangle$ |  $\blacktriangle$$19.5$ | $\blacktriangle$ | $\blacktriangle$$21.9$ | $\blacktriangle$ | $\blacktriangle$$22.1$ | $\blacktriangle$ |  |  $\blacktriangle$16.5 $\blacktriangle$ | $\blacktriangle$$16.8$ |  $\blacktriangle$ | $\blacktriangle$$15.7$ | $\blacktriangle$ | $\blacktriangle$$19.7$ |  $\blacktriangle$ |  |  $\blacktriangle$16.3 $\blacktriangle$ | $\blacktriangle$$17.6$ |  $\blacktriangle$ | $\blacktriangle$$15.4$ | $\blacktriangle$ | $\blacktriangle$$18.9$ |  $\blacktriangle$ |  |  $\blacktriangle$16.2 $\blacktriangle$ | $\blacktriangle$$18.5$ |  $\blacktriangle$ | $\blacktriangle$$16.7$ |  $\blacktriangle$ | $\blacktriangle$$21.2$ |  $\blacktriangle$ | $\blacktriangle$$22.9$ |  $\blacktriangle$
Con |  $\blacktriangle$16.6 $\blacktriangle$ | $\blacktriangle$$17.4$ |  $\blacktriangle$ | $\blacktriangle$$16.6$ | $\blacktriangle$ | $\blacktriangle$$18.5$ |  $\blacktriangle$ |  |  $\blacktriangle$15.2 $\blacktriangle$ | $\blacktriangle$$16.1$ |  $\blacktriangle$ | $\blacktriangle$$15.7$ |  $\blacktriangle$ | $\blacktriangle$$18.5$ |  $\blacktriangle$ |  |  $\blacktriangle$15.5 $\blacktriangle$ | $\blacktriangle$$16.5$ |  $\blacktriangle$ | $\blacktriangle$$15.6$ |  $\blacktriangle$ | $\blacktriangle$$19.6$ |  $\blacktriangle$ |  |  $\blacktriangle$15.3 $\blacktriangle$ | $\blacktriangle$$16.3$ |  $\blacktriangle$ | $\blacktriangle$$15.9$ |  $\blacktriangle$ | $\blacktriangle$$19.0$ |  $\blacktriangle$ | $\blacktriangle$$22.7$ |  $\blacktriangle$
Dow |  $\blacktriangle$18.6 $\blacktriangle$ | $\blacktriangle$$19.0$ | $\blacktriangle$ | $\blacktriangle$$18.8$ |  $\blacktriangle$ | $\blacktriangle$$21.7$ |  $\blacktriangle$ |  |  $\blacktriangle$17.4 $\blacktriangle$ | $\blacktriangle$$17.8$ |  $\blacktriangle$ |  $\blacktriangle$$16.7$ | $\blacktriangle$ | $\blacktriangle$$24.1$ |  $\blacktriangle$ |  |  $\blacktriangle$17.7 $\blacktriangle$ | $\blacktriangle$$18.2$ |  $\blacktriangle$ | $\blacktriangle$$17.0$ | $\blacktriangle$ | $\blacktriangle$$24.3$ |  $\blacktriangle$ |  |  $\blacktriangle$17.8 $\blacktriangle$ | $\blacktriangle$$19.8$ | $\blacktriangle$ | $\blacktriangle$$17.6$ | $\blacktriangle$ | $\blacktriangle$$22.4$ |  $\blacktriangle$ | $\blacktriangle$$30.6$ |  $\blacktriangle$
EnC |  $\blacktriangle$4.66 $\blacktriangle$ | $\blacktriangle$$5.15$ |  $\blacktriangle$ | $\blacktriangle$$4.26$ | $\blacktriangle$ | $\blacktriangle$$5.55$ |  $\blacktriangle$ |  |  $\blacktriangle$3.67 $\blacktriangle$ | $\blacktriangle$$4.37$ |  $\blacktriangle$ | $\blacktriangle$$4.14$ |  $\blacktriangle$ | $\blacktriangle$$6.92$ |  $\blacktriangle$ |  |  $\blacktriangle$3.85 $\blacktriangle$ | $\blacktriangle$$4.50$ |  $\blacktriangle$ | $\blacktriangle$$4.02$ |  $\blacktriangle$ | $\blacktriangle$$7.08$ |  $\blacktriangle$ |  |  $\blacktriangle$3.76 $\blacktriangle$ | $\blacktriangle$$4.88$ |  $\blacktriangle$ | $\blacktriangle$$3.99$ |  $\blacktriangle$ | $\blacktriangle$$6.78$ |  $\blacktriangle$ | $\blacktriangle$$4.23$ |  $\blacktriangle$
EnH |  $\blacktriangle$1.65 $\blacktriangle$ | $\blacktriangle$$1.52$ |  $\blacktriangle$ | $\blacktriangle$$1.13$ | $\blacktriangle$ | $\blacktriangle$$2.63$ |  $\blacktriangle$ |  |  $\blacktriangle$0.69 $\blacktriangle$ | $\blacktriangle$$1.54$ |  $\blacktriangle$ | $\blacktriangle$$0.84$ |  $\blacktriangle$ | $\blacktriangle$$4.02$ |  $\blacktriangle$ |  |  $\blacktriangle$0.92 $\blacktriangle$ | $\blacktriangle$$1.78$ |  $\blacktriangle$ | $\blacktriangle$$1.02$ |  $\blacktriangle$ |  $\blacktriangle$$3.81$ |  $\blacktriangle$ |  |  $\blacktriangle$0.87 $\blacktriangle$ | $\blacktriangle$$1.78$ |  $\blacktriangle$ | $\blacktriangle$$0.80$ | $\blacktriangle$ | $\blacktriangle$$3.68$ |  $\blacktriangle$ | $\blacktriangle$$0.43$ | $\blacktriangle$
Tow |  $\blacktriangle$11.5 $\blacktriangle$ | $\blacktriangle$$11.7$ |  $\blacktriangle$ | $\blacktriangle$$11.7$ |  $\blacktriangle$ | $\blacktriangle$$15.7$ |  $\blacktriangle$ |  |  $\blacktriangle$11.3 $\blacktriangle$ | $\blacktriangle$$10.9$ | $\blacktriangle$ | $\blacktriangle$$11.1$ | $\blacktriangle$ | $\blacktriangle$$16.1$ |  $\blacktriangle$ |  |  $\blacktriangle$11.4 $\blacktriangle$ | $\blacktriangle$$11.3$ | $\blacktriangle$ | $\blacktriangle$$10.9$ | $\blacktriangle$ | $\blacktriangle$$17.0$ |  $\blacktriangle$ |  |  $\blacktriangle$11.3 $\blacktriangle$ |  $\blacktriangle$$11.9$ |  $\blacktriangle$ | $\blacktriangle$$11.2$ | $\blacktriangle$ | $\blacktriangle$$16.6$ |  $\blacktriangle$ | $\blacktriangle$$11.2$ | $\blacktriangle$
WiR |  $\blacktriangle$64.4 $\blacktriangle$ | $\blacktriangle$$64.6$ | $\blacktriangle$ | $\blacktriangle$$65.2$ |  $\blacktriangle$ | $\blacktriangle$$64.3$ | $\blacktriangle$ |  |  $\blacktriangle$63.0 $\blacktriangle$ | $\blacktriangle$$62.4$ | $\blacktriangle$ | $\blacktriangle$$62.5$ | $\blacktriangle$ | $\blacktriangle$$63.8$ |  $\blacktriangle$ |  |  $\blacktriangle$62.3 $\blacktriangle$ | $\blacktriangle$$62.9$ | $\blacktriangle$ | $\blacktriangle$$62.8$ | $\blacktriangle$ | $\blacktriangle$$64.6$ |  $\blacktriangle$ |  |  $\blacktriangle$62.7 $\blacktriangle$ | $\blacktriangle$$62.9$ |  $\blacktriangle$ | $\blacktriangle$$62.5$ |  $\blacktriangle$ | $\blacktriangle$$64.5$ |  $\blacktriangle$ |  $\blacktriangle$$71.7$ |  $\blacktriangle$
WiW |  $\blacktriangle$70.1 $\blacktriangle$ | $\blacktriangle$$70.1$ | $\blacktriangle$ | $\blacktriangle$$68.8$ | $\blacktriangle$ | $\blacktriangle$$70.9$ |  $\blacktriangle$ |  |  $\blacktriangle$69.2 $\blacktriangle$ | $\blacktriangle$$69.2$ | $\blacktriangle$ | $\blacktriangle$$68.7$ | $\blacktriangle$ | $\blacktriangle$$71.1$ |  $\blacktriangle$ |  |  $\blacktriangle$68.9 $\blacktriangle$ | $\blacktriangle$$69.3$ |  $\blacktriangle$ | $\blacktriangle$$69.4$ | $\blacktriangle$ | $\blacktriangle$$71.6$ |  $\blacktriangle$ |  |  $\blacktriangle$69.1 $\blacktriangle$ | $\blacktriangle$$69.7$ |  $\blacktriangle$ | $\blacktriangle$$69.6$ | $\blacktriangle$ | $\blacktriangle$$71.4$ |  $\blacktriangle$ | $\blacktriangle$$72.2$ |  $\blacktriangle$
Yac |  $\blacktriangle$0.46 $\blacktriangle$ | $\blacktriangle$$0.45$ | $\blacktriangle$ | $\blacktriangle$$0.37$ | $\blacktriangle$ | $\blacktriangle$$0.46$ | $\blacktriangle$ |  |  $\blacktriangle$0.32 $\blacktriangle$ | $\blacktriangle$$0.38$ |  $\blacktriangle$ | $\blacktriangle$$0.33$ | $\blacktriangle$ | $\blacktriangle$$0.40$ |  $\blacktriangle$ |  |  $\blacktriangle$0.32 $\blacktriangle$ | $\blacktriangle$$0.39$ |  $\blacktriangle$ | $\blacktriangle$$0.33$ | $\blacktriangle$ | $\blacktriangle$$0.44$ |  $\blacktriangle$ |  |  $\blacktriangle$0.33 $\blacktriangle$ | $\blacktriangle$$0.40$ |  $\blacktriangle$ | $\blacktriangle$$0.33$ | $\blacktriangle$ | $\blacktriangle$$0.48$ |  $\blacktriangle$ | $\blacktriangle$$0.88$ |  $\blacktriangle$
B/W | — | 1/5 | 4/4 | 1/7 |  | — | 0/7 | 2/3 | 0/10 |  | — | 0/8 | 3/4 | 0/10 |  | — | 0/9 | 3/4 | 0/10 | 2/8

Test $\ell=63$ $n^{\text{pop}}=1000$ $\blacktriangle$ $\blacktriangle$ IMS
$g=4$ $\blacktriangle$ $\blacktriangle$ IMS $g=6$ $\blacktriangle$
$\blacktriangle$ IMS $g=8$ $\blacktriangle$ G T$h$ T$\ell$ R G T$h$ T$\ell$ R
G T$h$ T$\ell$ R G T$h$ T$\ell$ R D

Air  $\blacktriangle$23.0 $\blacktriangle$ $\blacktriangle$25.5
$\blacktriangle$ $\blacktriangle$25.9 $\blacktriangle$ $\blacktriangle$31.5
$\blacktriangle$ $\blacktriangle$21.1 $\blacktriangle$ $\blacktriangle$22.5
$\blacktriangle$ $\blacktriangle$19.6 $\blacktriangle$ $\blacktriangle$34.9
$\blacktriangle$ $\blacktriangle$21.7 $\blacktriangle$ $\blacktriangle$22.4
$\blacktriangle$ $\blacktriangle$21.9 $\blacktriangle$ $\blacktriangle$33.8
$\blacktriangle$ $\blacktriangle$21.2 $\blacktriangle$ $\blacktriangle$23.4
$\blacktriangle$ $\blacktriangle$21.6 $\blacktriangle$ $\blacktriangle$34.1
$\blacktriangle$ $\blacktriangle$30.8 $\blacktriangle$ Bos
$\blacktriangle$22.0 $\blacktriangle$ $\blacktriangle$20.0 $\blacktriangle$
$\blacktriangle$21.2 $\blacktriangle$ $\blacktriangle$21.9 $\blacktriangle$
$\blacktriangle$19.2 $\blacktriangle$ $\blacktriangle$20.7 $\blacktriangle$
$\blacktriangle$20.4 $\blacktriangle$ $\blacktriangle$24.1 $\blacktriangle$
$\blacktriangle$21.5 $\blacktriangle$ $\blacktriangle$20.3 $\blacktriangle$
$\blacktriangle$20.3 $\blacktriangle$ $\blacktriangle$25.0 $\blacktriangle$
$\blacktriangle$19.8 $\blacktriangle$ $\blacktriangle$19.7 $\blacktriangle$
$\blacktriangle$21.4 $\blacktriangle$ $\blacktriangle$25.8 $\blacktriangle$
$\blacktriangle$26.1 $\blacktriangle$ Con  $\blacktriangle$15.9
$\blacktriangle$ $\blacktriangle$17.1 $\blacktriangle$ $\blacktriangle$16.5
$\blacktriangle$ $\blacktriangle$18.3 $\blacktriangle$ $\blacktriangle$15.3
$\blacktriangle$ $\blacktriangle$16.2 $\blacktriangle$ $\blacktriangle$15.5
$\blacktriangle$ $\blacktriangle$19.1 $\blacktriangle$ $\blacktriangle$15.3
$\blacktriangle$ $\blacktriangle$16.3 $\blacktriangle$ $\blacktriangle$15.8
$\blacktriangle$ $\blacktriangle$19.9 $\blacktriangle$ $\blacktriangle$15.3
$\blacktriangle$ $\blacktriangle$16.6 $\blacktriangle$ $\blacktriangle$16.1
$\blacktriangle$ $\blacktriangle$18.9 $\blacktriangle$ $\blacktriangle$21.3
$\blacktriangle$ Dow  $\blacktriangle$18.3 $\blacktriangle$
$\blacktriangle$18.6 $\blacktriangle$ $\blacktriangle$17.4 $\blacktriangle$
$\blacktriangle$22.3 $\blacktriangle$ $\blacktriangle$17.5 $\blacktriangle$
$\blacktriangle$17.9 $\blacktriangle$ $\blacktriangle$17.0 $\blacktriangle$
$\blacktriangle$23.7 $\blacktriangle$ $\blacktriangle$17.6 $\blacktriangle$
$\blacktriangle$18.2 $\blacktriangle$ $\blacktriangle$17.2 $\blacktriangle$
$\blacktriangle$24.6 $\blacktriangle$ $\blacktriangle$17.7 $\blacktriangle$
$\blacktriangle$18.2 $\blacktriangle$ $\blacktriangle$17.9 $\blacktriangle$
$\blacktriangle$22.6 $\blacktriangle$ $\blacktriangle$28.0 $\blacktriangle$
EnC  $\blacktriangle$4.49 $\blacktriangle$ $\blacktriangle$4.70
$\blacktriangle$ $\blacktriangle$4.24 $\blacktriangle$ $\blacktriangle$5.63
$\blacktriangle$ $\blacktriangle$3.77 $\blacktriangle$ $\blacktriangle$4.37
$\blacktriangle$ $\blacktriangle$3.99 $\blacktriangle$ $\blacktriangle$6.94
$\blacktriangle$ $\blacktriangle$3.93 $\blacktriangle$ $\blacktriangle$4.42
$\blacktriangle$ $\blacktriangle$3.95 $\blacktriangle$ $\blacktriangle$7.42
$\blacktriangle$ $\blacktriangle$3.95 $\blacktriangle$ $\blacktriangle$4.85
$\blacktriangle$ $\blacktriangle$4.20 $\blacktriangle$ $\blacktriangle$7.37
$\blacktriangle$ $\blacktriangle$4.47 $\blacktriangle$ EnH
$\blacktriangle$1.60 $\blacktriangle$ $\blacktriangle$1.59 $\blacktriangle$
$\blacktriangle$1.12 $\blacktriangle$ $\blacktriangle$2.74 $\blacktriangle$
$\blacktriangle$0.80 $\blacktriangle$ $\blacktriangle$1.52 $\blacktriangle$
$\blacktriangle$0.89 $\blacktriangle$ $\blacktriangle$3.73 $\blacktriangle$
$\blacktriangle$0.88 $\blacktriangle$ $\blacktriangle$1.67 $\blacktriangle$
$\blacktriangle$0.94 $\blacktriangle$ $\blacktriangle$4.12 $\blacktriangle$
$\blacktriangle$0.89 $\blacktriangle$ $\blacktriangle$1.92 $\blacktriangle$
$\blacktriangle$0.93 $\blacktriangle$ $\blacktriangle$3.71 $\blacktriangle$
$\blacktriangle$0.33 $\blacktriangle$ Tow  $\blacktriangle$11.6
$\blacktriangle$ $\blacktriangle$12.2 $\blacktriangle$ $\blacktriangle$12.1
$\blacktriangle$ $\blacktriangle$15.9 $\blacktriangle$ $\blacktriangle$11.5
$\blacktriangle$ $\blacktriangle$11.4 $\blacktriangle$ $\blacktriangle$11.4
$\blacktriangle$ $\blacktriangle$16.8 $\blacktriangle$ $\blacktriangle$11.6
$\blacktriangle$ $\blacktriangle$11.5 $\blacktriangle$ $\blacktriangle$11.2
$\blacktriangle$ $\blacktriangle$16.7 $\blacktriangle$ $\blacktriangle$11.4
$\blacktriangle$ $\blacktriangle$12.2 $\blacktriangle$ $\blacktriangle$11.4
$\blacktriangle$ $\blacktriangle$17.1 $\blacktriangle$ $\blacktriangle$11.2
$\blacktriangle$ WiR  $\blacktriangle$63.1 $\blacktriangle$
$\blacktriangle$63.0 $\blacktriangle$ $\blacktriangle$64.4 $\blacktriangle$
$\blacktriangle$62.9 $\blacktriangle$ $\blacktriangle$62.9 $\blacktriangle$
$\blacktriangle$62.5 $\blacktriangle$ $\blacktriangle$61.7 $\blacktriangle$
$\blacktriangle$62.5 $\blacktriangle$ $\blacktriangle$62.5 $\blacktriangle$
$\blacktriangle$63.0 $\blacktriangle$ $\blacktriangle$62.3 $\blacktriangle$
$\blacktriangle$63.6 $\blacktriangle$ $\blacktriangle$62.7 $\blacktriangle$
$\blacktriangle$63.0 $\blacktriangle$ $\blacktriangle$61.8 $\blacktriangle$
$\blacktriangle$63.2 $\blacktriangle$ $\blacktriangle$72.6 $\blacktriangle$
WiW  $\blacktriangle$68.7 $\blacktriangle$ $\blacktriangle$69.0
$\blacktriangle$ $\blacktriangle$68.0 $\blacktriangle$ $\blacktriangle$69.9
$\blacktriangle$ $\blacktriangle$68.3 $\blacktriangle$ $\blacktriangle$68.6
$\blacktriangle$ $\blacktriangle$68.3 $\blacktriangle$ $\blacktriangle$70.2
$\blacktriangle$ $\blacktriangle$69.1 $\blacktriangle$ $\blacktriangle$69.4
$\blacktriangle$ $\blacktriangle$68.2 $\blacktriangle$ $\blacktriangle$70.6
$\blacktriangle$ $\blacktriangle$68.2 $\blacktriangle$ $\blacktriangle$69.3
$\blacktriangle$ $\blacktriangle$69.0 $\blacktriangle$ $\blacktriangle$70.3
$\blacktriangle$ $\blacktriangle$72.2 $\blacktriangle$ Yac
$\blacktriangle$0.44 $\blacktriangle$ $\blacktriangle$0.46 $\blacktriangle$
$\blacktriangle$0.40 $\blacktriangle$ $\blacktriangle$0.46 $\blacktriangle$
$\blacktriangle$0.41 $\blacktriangle$ $\blacktriangle$0.49 $\blacktriangle$
$\blacktriangle$0.40 $\blacktriangle$ $\blacktriangle$0.45 $\blacktriangle$
$\blacktriangle$0.41 $\blacktriangle$ $\blacktriangle$0.45 $\blacktriangle$
$\blacktriangle$0.42 $\blacktriangle$ $\blacktriangle$0.52 $\blacktriangle$
$\blacktriangle$0.46 $\blacktriangle$ $\blacktriangle$0.46 $\blacktriangle$
$\blacktriangle$0.44 $\blacktriangle$ $\blacktriangle$0.50 $\blacktriangle$
$\blacktriangle$0.91 $\blacktriangle$ B/W — 0/6 5/4 0/7 — 0/7 3/3 0/10 — 0/6
4/3 0/10 — 0/7 2/4 0/10 2/8

##  9 Discussion & Conclusion

We built upon previous work on model-based GP, in particular on GP-GOMEA, to
find accurate solutions when a strict limitation on their size is imposed, in
the domain of SR. We focused on small solutions, in particular much smaller
solutions than typically reported in literature, to prevent solutions becoming
too large to be (easily) interpretable, a key reason to justify the use of GP
in many practical applications.

A first limitation of this work is that to truly _achieve_ interpretability
may well require different measures. Interpretation is mostly subjective, and
many other factors besides solution size are important, including the
intuitiveness of the subfunctions composing the solution, potential
decompositions into understandable repeating sub-modules, the number of
features considered, and the meaning of these features (Lipton,, 2018; Doshi-
Velez and Kim,, 2017). Nonetheless, much current research on GP for SR is far
from delivering any interpretable results precisely because the size of
solutions is far too large (see, e.g., the work of (Martins et al.,, 2018)).

We considered solution sizes up to $\ell=63$ (corresponding to $h=5$ for GP-
GOMEA with subfunctions of arity $\leq 2$). In our opinion, the limit of
$\ell=31$ ($h=4$) is particularly interesting, as interpreting some solutions
at this level can already be non-trivial at times. For example, we show the
(manually simplified) best test solution found by GP-GOMEA (IMS $g=8$) for
Tower and Yacht, i.e. the biggest and smallest dataset respectively, in Figure
8. The solution for Tower is arguably easier to understand than the one for
Yacht. We found solutions with $\ell=63$ ($h=5$) to be overly long to attempt
interpreting, and solutions with $\ell=15$ ($h=3$) to be mostly readable and
understandable. We report other example solutions at: http://bit.ly/2IrUFyQ.

We believe future work should address the aforementioned limitation: effort
should be put towards reaching some form of interpretability notions, that go
beyond solution size or other custom metrics (e.g., (Vladislavleva et al.,,
2009)). User studies involving the end users of the model (e.g., medical
doctors for a diagnosis model) could guide the design of notions of
interpretability. If an objective that represents interpretability can be
defined, the design of multi-objective (model-based) GP algorithms may lead to
very interesting results.

Another limitation of this work lies in the fact that we did not study how
linkage learning behaves in GP for SR in depth. In fact, it would be