# On the Nature of the Phenotype in Tree Genetic Programming

Wolfgang Banzhaf
Department of Computer Science and Engineering
Michigan State University
East Lansing, MI 48824
<EMAIL_ADDRESS>
Illya Bakurov
Department of Computer Science and Engineering
Michigan State University
East Lansing, MI 48824
<EMAIL_ADDRESS>
###### Abstract

In this contribution, we discuss the basic concepts of genotypes and
phenotypes in tree-based GP (TGP), and then analyze their behavior using five
benchmark datasets. We show that TGP exhibits the same behavior that we can
observe in other GP representations: At the genotypic level trees show
frequently unchecked growth with seemingly ineffective code, but on the
phenotypic level, much smaller trees can be observed. To generate phenotypes,
we provide a unique technique for removing semantically ineffective code from
GP trees. The approach extracts considerably simpler phenotypes while not
being limited to local operations in the genotype. We generalize this
transformation based on a problem-independent parameter that enables a further
simplification of the exact phenotype by coarse-graining to produce
approximate phenotypes. The concept of these phenotypes (exact and
approximate) allows us to clarify what evolved solutions truly predict, making
GP models considered at the phenotypic level much better interpretable.

_Keywords_ Genetic Programming $\cdot$ Genotype-Phenotype Mapping $\cdot$
Bloat

##  1 Introduction

Since early in its development, GP has been associated with Machine Learning
tasks (Koza, 1992; Banzhaf et al., 1998). What is special about GP compared to
other EC approaches is that its expected result is an active solution (the
program, algorithm, formula, model, etc.) that itself behaves in some way to
process inputs into outputs. Thus it is not enough to simply consider a static
solution to an optimization problem, but what is required is the ability to
modify the solution in both its content and its complexity. The genetic
operators for GP must therefore be able to grow and shrink the complexity of
solutions in the evolutionary process, an ability that comes with its
particular challenges.

All this is well known and has led to some surprises early on in the history
of GP (Koza, 1992; Angeline, 1994; Banzhaf et al., 1998): To the bafflement of
many researchers, a substantial portion of the code produced by GP was
ineffective (neutral, non-effective, intron code, junk, etc.), which did not
seem to play a role in the actual behavior of the evolved algorithms, but
nevertheless was produced by the evolutionary process. Researchers found that
if they waited long enough in evolutionary runs, the overwhelming majority of
the code was of this type, a phenomenon coined ’bloat’.

Several theories have been put forward as to what the reasons are for this
apparent waste of code material with its attendant strain on computational
resources of the evolutionary process (both memory and compute cycles). A very
interesting consequence of ineffective code in GP is that it necessitates the
discernment of genetic material (genotypes) and behavioral determinants
(phenotypes). Allowing for some of the genetic material to not having an
impact on behavior requires the introduction of this difference and a mapping
between genotypes and phenotypes. In contrast to popular belief, most GP
representations today have such a mapping, even if it is somewhat hidden from
view.

Three of the most typical representations used in GP are expression trees in
tree GP (TGP), linear sequences of instructions in linear GP (LGP) and
circuit-type graphs in cartesian GP (CGP). Here we shall be mostly concerned
with TGP, and want to only briefly touch the other two representations. All
three require genotypes (expression trees in TGP, numbers encoding
instructions in LGP, numbers encoding graphs in CGP) and phenotypes
(expression trees in TGP, instruction sequences in LGP and graphs in CGP). To
draw a clear distinction: genotypes are manipulated by genetic operations
while phenotype are the encoded structures that provide the behavioral
function of the algorithms. Because the genotypes are normally larger than the
phenotypes, taking into account that some of the code is non-effective or
neutral (either structurally or semantically), it is the phenotypes that can
provide an understanding of what the algorithms do.

In a Machine Learning (ML) context, GP provides a user with a completely
different experience in terms of transparency and interpretability of the
final models when compared to "black-box" models of, say, deep neural
networks. By manipulating discrete structures, the inner workings of the model
are clearer, and the relationships between features and predictions are
explicitly defined in GP. As a result, evolved solutions can offer insights
into how the model arrives at its predictions, allowing humans to understand
the decision-making process. Although GP is not the only "white-box" method in
the spectrum of ML methods, it allows for an unprecedented degree of
flexibility of representations and modularity, making it suitable for numerous
different ML tasks: classification (Ingalalli et al., 2014; Muñoz et al.,
2015; La Cava et al., 2019), regression (Moraglio et al., 2012; Castelli and
Manzoni, 2019; La Cava et al., 2016), feature engineering (Neshatian et al.,
2012; Tran et al., 2019), manifold learning (Lensen et al., 2022), active
learning (Haut et al., 2023), image classification (Tackett, 1994; Zhang and
Smart, 2004; Ul Ain et al., 2017; Iqbal et al., 2017), image segmentation
(Bakurov et al., 2023b), image enhancement (Correia et al., 2022, 2021),
automatic generation of ML pipelines (Olson and Moore, 2019) and even neural
architecture search (Goncalves et al., 2015; Assunção et al., 2019). The area
of explainable AI is consistently receiving more attention from both
practitioners and researchers (Markus et al., 2021; Vainio-Pekka et al., 2023)
and GP has gained popularity where human-interpretable solutions are
paramount. Real-world examples include medical image segmentation (Cortacero
et al., 2023), prediction of human oral bioavailability of drugs (Silva and
Vanneschi, 2012), skin cancer classification from lesion images (Ain et al.,
2022), and even conception of models of visual perception (Bakurov et al.,
2023a), etc. Besides being able to provide interpretable models, there is
evidence that GP can also help to unlock the behaviour of black-box models
(Evans et al., 2019; Bakurov et al., 2023b).

Given that GP phenotypes are even smaller than genotypes, interpretability is
enhanced by focussing on phenotypes when analysing GP models. In this
contribution, we therefore study the relationship between genotypes and
phenotypes in TGP, and develop a unique simplification technique that allows
us to remove semantically ineffective code from GP genotype trees based on
numerical simplification. Particularly, in this work, we show that:

  * •

Trees of TGP represent both the genotype and phenotype of individuals.

  * •

Phenotypes are hidden within the larger genotypic trees but can be extracted
via simplification without affecting their behavior, which facilitates
understanding of the models.

  * •

Phenotypes can be further simplified to shrink model size but this might
impact generalization ability.

  * •

We observe the population dynamics of genotypes and phenotypes throughout the
evolutionary process to facilitate our understanding of the genotype-phenotype
relationship.

The paper is organized as follows: Section 2 introduces the necessary
theoretical background by providing a brief discussion of the bloat phenomenon
in TGP, an analogy to phenomena in living systems, some approaches to remedy
this situation and a generic look at the difference between genotypes and
phenotypes. Section 3 describes our algorithm to extract phenotypes from
genotypes in TGP. We also introduce the notion of an approximate phenotype.
Section 4 characterizes the datasets used in our study, discusses the hyper-
parameters used, and shows the results obtained. Finally, Section 5 draws the
main conclusions and proposes future research ideas.

##  2 Background

As a natural result of genetic operators applied to tree genotypes, GP trees
tend to grow in size during evolution in search for a better match to the
desired behaviour. However, this growth is not always justified by an
improvement in performance (such as the generalization ability on unseen
data). It has long been observed that standard TGP tends to produce
excessively large and redundant trees without a corresponding improvement in
terms of fitness (Koza, 1992; Angeline, 1994). Moreover, it was shown that
beyond a certain program length, the fitness distribution of individuals
converges to a limit (Langdon and Poli, 2002). The apparent unnecessary growth
of GP trees is often called the bloat phenomenon and several justifications
were proposed for its existence. For decades, researchers tried to address
this problem. We briefly review part of this voluminous literature here, but
cannot address it in its full breadth.

The consequences of bloat in TGP are hard to underestimate: the amount of
computer memory to store a population grows and concomitantly the evaluation
time of trees increases, making the system less attractive for real-time
applications. Moreover, unnecessarily large trees (genotypes) make visual
inspection and interpretation difficult, if not impossible. In LGP and CGP the
mechanisms for bloat result mainly in structural ineffective code. The
difficulty for TGP is that its bloat is mostly semantic (Banzhaf et al.,
2024).

###  2.1 Bloat

In binary-string Genetic Algorithms (GAs), it was found that highly fit
building blocks become attached, by coincidence, to adjacent unfit building
blocks. As a result, these joint entities were propagated throughout the
population using recombination, subsequently preventing highly fit building
blocks at adjacent locations from joining (Mitchell et al., 1993). W. Tackett
demonstrated that this phenomenon, called ’hitchhiking’, also exists in TGP
and that it was a consequence of recombination acting in concert with fitness-
based selection (Tackett, 1994).

In (Langdon and Poli, 1998a, b), W. Langdon and R. Poli show that fitness-
based selection makes the evolutionary search converge to mainly finding
candidate solutions with the same fitness as previously found solutions. In
the absence of improved solutions, the search may become a random search for
new representations of the best-so-far solution. Given the fact that the
variable-length representation of TGP allows many more representations of a
given behaviour to be longer, these solutions are expected to occur more often
and representation length naturally tends to increase. In other words, a
straightforward fitness-based approach contributes to bloat. These findings
are in agreement with the earlier findings of W. Tacket (Tackett, 1994) who
concluded that (i) the average growth in size is proportional to the
underlying selection pressure, and that (ii) bloat does not occur when the
fitness is completely ignored.

In (Dignum and Poli, 2007) the authors provide a theoretical model of program
length distribution in the population assuming a repeated application of
subtree crossover (i.e., crossover with a uniform selection of points) on a
flat fitness landscape. The model is validated empirically and it is proved
that the reproduction process has a strong bias to sample shorter programs
when crossover with a uniform selection of points is applied. It was
demonstrated that, if a reasonable minimum program size exists for relatively
fit programs, the repeated application of fitness-based selection and subtree
crossover will cause bloat to occur and that this phenomenon will be more
acute if allowing crossover to distribute a population before applying
fitness-based selection.

A number of researchers demonstrated that bloat is an evolutionary response to
protect solutions from the destructive effects of operators, with crossover
the main focus of their studies (McPhee and Miller, 1995; Blickle and Thiele,
1994; Altenberg, 1994; Nordin and Banzhaf, 1995; Soule and Heckendorn, 2002).
In particular, when a program contains large sections of code that do not have
a significant effect on its behaviour (introns), the application of a given
genetic operator in that section is expected to have no overall effect on the
program’s behaviour (i.e., it is neutral). Several studies demonstrate that
genetic operators are more likely to deteriorate offspring fitness than
increase it and that a large proportion of recombinations are fitness-neutral
(Nordin et al., 1996; Langdon et al., 1999; Soule and Heckendorn, 2002). Thus,
by increasing the proportion of introns to effective sections of code (exons),
evolution increases the likelihood that the product of genetic operators will
be neutral in terms of fitness (Banzhaf and Langdon, 2002). However, if bloat
makes it more difficult to deteriorate the fitness of a solution, it also
makes it harder to improve it. In this sense, bloat constitutes a serious
problem for a sustainable evolutionary process.

###  2.2 A Biological Analogy

EAs are strongly inspired by evolutionary biology and it is not surprising
that the topic addressed in this manuscript can be also found there. The
analogue for the "redundancy" or "bloat" in genetics is called non-coding DNA
and it refers to all DNA that is not involved in the coding for amino acids
(i.e., does not provide instructions for making proteins). It is considered
that the non-coding DNA makes up 97-99% of total DNA (Wu and Lindsay, 1996;
Litwack, 2022). Initially, biologists thought that it had no function and
referred to the non-coding DNA as "junk". Later, it was found that many of the
non-coding sequences are repeated movable elements that facilitate genomic
rearrangements; also, it was found to contain sequences that act as regulatory
elements, determining when and where genes are turned on and off (C., 2017).
Finally, it was found that alternative splicing of sequences at exon/intron
boundaries (Gilbert, 1978) can provide for a combinatorial variety of proteins
derived from the same gene sequence.

All of this suggests that non-coding DNA is of evolutionary importance.
Otherwise, one would expect it to have been eliminated by natural selection
long ago due to the extra energy it requires for sustaining and processing (Wu
and Lindsay, 1996). In turn, one could suspect that the non-coding regions of
GP genotypes might also serve a useful role in artificial evolution, which
gives support to the neutrality for protection hypothesis.

###  2.3 Simplification

Here we consider the concept of the phenotype in TGP as that part of an
individuum that produces overall behavior. We use a simplification algorithm
to extract the phenotype tree from a genotype tree, and keep them side by side
so as to be able to monitor their development over the course of evolution.
Simplification algorithms have been traditionally used in TGP, but not with a
concept of phenotype in mind. We divide such contributions into two
categories: (i) those that have no effect on the evolutionary trajectory of a
run (observing approaches); and (ii) those that do affect the evolutionary
trajectory (intervening approaches). As pointed out in (Javed et al., 2022),
historically, the former approaches were first, but quickly overtaken by the
latter. Javed et al. call the former ’offline’ approaches vs. the latter
called ’online’.

Under category (i), we count ”offline simplification”, properly defined as
"the analysis and reduction in complexity" of an individual outside the
evolutionary run, e.g. at the end of a run (Koza, 1992; Jackson, 2010; Spector
and Helmuth, 2014; Rockett, 2020), or during a run, but not given back to
evolution - the latter we call ”monitoring” (Nordin and Banzhaf, 1995; Mori et
al., 2008). What researchers have done here, without saying it, is to observe
the phenotype of an individual similar to what we do here, without explicitly
calling it that.

Under category (ii), we count ”online simplification” or ”pruning” (Wong and
Zhang, 2006; Nguyen and Chu, 2020; Kinzett et al., 2009; Alfaro-Cid et al.,
2010; Jackson, 2010), as well as limiting the size of individuals in various
ways (Koza, 1992; Langdon et al., 1999; Dignum and Poli, 2007, 2008a; Silva
and Costa, 2009), operator equalization and its variants (Dignum and Poli,
2008b; Silva, 2011; Silva and Vanneschi, 2009), time-based approaches to
controlling bloat (de Vega et al., 2020a, b), fitness and selection approaches
(like double tournaments etc.) (Poli, 2003; Luke and Panait, 2002), and
elitism (Poli et al., 2008; Whigham and Dick, 2009). All of these methods work
directly on the genotype, with the result of modifying that genotype and
intervening with the evolutionary process.

A recent review of simplification and bloat control techniques can be found in
(Javed et al., 2022). Here, we focus on the former category of approaches,
that are observing the runs, rather than intervening, because we believe that
understanding the underlying phenomena is important to engineer better and
faster evolutionary processes.

###  2.4 Genotype and Phenotype - Definitions and Relations

It is useful to recall a crisp definition of the genotype and of the phenotype
in Genetic Programming. In this line of work, we discern them sharply by
asking the following questions:

  * •

Which structure is manipulated by the genetic operators (mutation, crossover
or other variation operators)? This we define as the genotype.

  * •

Which structure determines behavior, i.e. has an impact on the output of the
program/algorithm? This we define as the phenotype.

The situation is depicted in Figure 1. The phenotype determines the behavior
of an individual which in turn is judged by the fitness function.

Figure 1: The relation between genotype, phenotype and behavior in Genetic
Programming

In Biology, the notion of phenotype is somewhat vague. Anything that can be
observed is considered the phenotype (de Vienne, 2022). So the definition of
phenotype is relative to the intent of an observer. It could be one specific
trait that is under observation, and thus the phenotype is restricted to that
trait. Or it can be the entire organism. But in GP we can actually tie the
phenotype to the part of the algorithm that makes a semantic contribution to
the output. Thus we can tie it to the behavior of the algorithm that is then
judged by the fitness function.

Between genotype and phenotype is the so-called genotype-phenotype map (GPM).
In GP, this is normally a relatively simple many-to-one mapping between
genotypes and phenotypes. In Biology, however, the GPM can be much more
complicated and typically is dynamic, a feature that few GP GPMs have (see
(Cussat-Blanc et al., 2019) for examples). It has been argued that the GPM is
a key ingredient in evolvability in living organisms (Kirschner and Gerhart,
2005). The GPM in GP, the mapping is normally many-to-one, because there are
many more genotypes that lead to the same structure with its subsequent
behavior.

It is easy to see the difference in a linear GP approach (Brameier and
Banzhaf, 2007). As is well known, LGP individuals consist of sequences of
instructions, some of which might not impact the overall behavior of an
individual. In LGP this comes about because such non-effective instructions
manipulate registers that have no impact on the output of a program. We can
easily identify those instructions, and they do not belong to the phenotype of
that individual. A similar, if less frequent phenomenon has been termed
”dormant nodes” (Jackson, 2010) in tree GP. Only what is effective in terms of
causing effective behavior is relevant and thus belongs to the phenotype.

The problem for tree GP is that the parse trees we see under evolution are
genotypes, not phenotypes, but somewhat hidden within such parse trees are the
phenotypes of the TGP individuals. Thus, it is only a subset of nodes in a
tree that effectively impacts its semantics or behavior, and it is that subset
we are interested in when we want to understand what an individual evolving in
TGP does. The problem of bloat in TGP is actually a problem of the growth of
genotypes under evolution, not of the phenotypes. Provided we have a means to
extract phenotypes from genotypes, we can hope to understand the solution
semantics on the phenotype level.

The next section will describe an algorithm for extracting the phenotype of a
TGP individual from its genotype. We shall use this algorithm and its variants
(which extract approximations to the phenotype) to argue that the relevant
part of a GP individual, i.e., the part that requires explanation and
understanding when solving a problem is actually only the phenotype and its
behavior. Everything else is a distraction, perhaps necessary for the
evolution of a solution, but not relevant for its behavior.

##  3 The Phenotype in Tree Genetic Programming

Most researchers consider the size of the tree representation as an
approximate measure of the complexity of a candidate solution. Thus, a
simplification procedure that can extract the phenotype from a genotype can
reduce the complexity of a tree and enhance the potential interpretability of
a solution while not changing the behavior, at least not significantly. In
this study, the quality of a solution is measured as generalisation ability on
real-world regression problems. For each tree under evolution (genotype) we
shall derive its phenotype and judge its behavior.

The impact of the simplification algorithm on the behavior of a solution will
depend on the type of simplifications we apply to the genotype, and can be
two-fold: (i) the behaviour is preserved, since the removed code has
absolutely no impact on the behaviour, or (ii) the behaviour is changed, as
the removed code contributed measurably to the behavior. In this study, we
refer to the former as exact simplification, whereas the latter is referred to
as approximate simplification. For approximate simplification, a problem-
independent parameter $t$ is introduced to control for different levels of
approximation accuracy and represents the percentile of the distance
distribution within a tree (see Section 3.1 for more details).

Consider a tree $T$ implemented as a list of program elements. Given a set of
training $n$ instances, the corresponding $n$-dimensional output vector is
represented by $\hat{y}$ and is called its semantics. Let $T_{s}$ represent a
given subtree in $T$, rooted at node $s$, and $\hat{y}_{s}$ the respective
semantics. During fitness evaluation, calculating $\hat{y}$ requires
calculating $\hat{y}_{s}$ for each $T_{s}$ in $T$. Specifically, the algorithm
recursively traverses the tree in a bottom-up manner, starting from the
deepest levels of $T$ and computes the outputs for each $T_{s}$ in $T$ up the
tree.

  1. 1.

Compute $\hat{y}_{s}\ \forall\ T_{s}\ \in\ T$.

  2. 2.

Given some similarity measure $f(x,y)$, create $M$.

  3. 3.

Given some value of $t\geq 0$, reduce $M$ to semantically equivalent pairs
(i.e., $\forall\ (\hat{y}_{s_{i}},\hat{y}_{s_{j}}),\
f(\hat{y}_{s_{i}},\hat{y}_{s_{j}})\leq p(t)$).

  4. 4.

While $M$ has entries:

    1. (a)

Select the largest tree $T_{s_{i}}\in M$.

    2. (b)

Select the smallest semantically equivalent tree $T_{s_{j}}$ for $T_{s_{i}}$.

    3. (c)

Replace $T_{s_{i}}$ with $T_{s_{j}}$.

    4. (d)

Remove all trees contained by $T_{s_{i}}$ (i.e., $\forall\ T_{s_{i_{j}}}\in
T_{s_{i}}$).

    5. (e)

Remove $T_{s_{i}}$ from $M$.

Algorithm 1 Pseudo-code for the proposed simplification method.

The proposed simplification algorithm capitalizes upon the mechanics of the
fitness-evaluation algorithm. In this way, we can avoid redundant function
calls and calculations. In particular, when $\hat{y}_{s}$ is calculated for
each $T_{s}$, the semantics are temporarily stored in a dictionary $D$ of the
form $D=\\{idx_{s}:\ y_{s}\\}$, where $idx_{s}$ represents the index of the
node $s$ (the root of $T_{s}$). Note that any terminal node in $T$ should be
also regarded as a subtree. We use $D$ to create a similarity matrix $M$
between every pair of semantics $y_{s_{i}}$ and $y_{s_{j}}$. In practice, we
only calculate and store the lower triangular matrix since we assume that
similarity
$f(\hat{y}_{s_{i}},\hat{y}_{s_{j}})=f(\hat{y}_{s_{j}},\hat{y}_{s_{i}})$ and
$f(\hat{y}_{s_{i}},\hat{y}_{s_{i}})=0$, where $f(x,\ y)$ is some similarity
measure. Then, $M$ is filtered to store only semantically equivalent pairs.
When the exact simplification is desired, $T_{s_{j}}$ is said to be equivalent
to $T_{s_{i}}$ if $f(\hat{y}_{s_{i}},\hat{y}_{s_{j}})\cong 0$, where $\cong$
denotes equality within floating-point rounding errors. In the case of an
approximation, the equivalence means $f(\hat{y}_{s_{i}},\hat{y}_{s_{j}})\leq
p(t)$, $t>0$. We denote the exact equivalence (the exact phenotype) with
$t=0$. Additional meta-data is provided with $M$: the length of each subtree
and whether one subtree contains another.

The proposed algorithm will then use this information as follows: First, the
largest tree $T_{s_{i}}$ is selected from $M$ and, for it, the smallest
semantically equivalent tree $T_{s_{j}}$ is chosen. Second, $T_{s_{i}}$ is
replaced by $T_{s_{j}}$. Finally, $T_{s_{i}}$ is removed from $M$ along with
the subtrees it contained. The procedure is iterated while $M$ has entries.
Algorithm 1 describes the proposed simplification.

###  3.1 Approximate simplification accuracy

We introduce a relaxation on the exact simplification condition which
translates into an additional degree of simplification by coarse-graining the
genotype. This is achieved via problem-independent parameter $t$ representing
the $t^{th}$ percentile of the similarity distribution generated when pruning
a given tree $T$. Specifically, when $M$ is constructed for a given tree, the
values it contains represent a similarity distribution. In this sense, $p(t)$
is the value of the $t^{th}$ percentile of that distribution and inversely
represents the approximation accuracy for the phenotype extraction. In our
experiments, we explore four different values of $t$: 2.5%, 5%, 10% and 20%.
Thus $T_{s_{j}}$ is said to be compatible to $T_{s_{i}}$ if
$f(\hat{y}_{s_{i}},\hat{y}_{s_{j}})\leq p(t)$. Given the fact that the input
data for different regression problems have different distributions, including
the range of values of the target, by defining $p(t)$ as the $t^{th}$
percentile of the similarity distribution, a robust and problem-independent
approach for approximate simplification is achieved. From this perspective,
the exact simplification corresponds to $t=0$. To accommodate for the
floating-point rounding error, in our experiments, two semantics vectors are
considered equal if the similarity between them, after being rounded to five
decimals, equals zero.

Figure 2 provides an example demonstrating the method’s functioning. It is
divided into three areas: $G$, $P_{t=0}$ and $P_{t=10}$. The $G$ area depicts
the genotype, while the other two represent different phenotypes,
simplifications depending on the value of $t$. For $t=0$, we perform exact
simplification, thus extracting the true phenotype. For $t=10$, we perform
approximate simplification. From the figure, $t=0$ requires only three
iterations of the algorithm (represented in red, blue and green subtrees,
respectively). Note that, however, more redundancies are present within the
subtrees. For example, at the bottom of the red subtree, on the right, we find
the expression $0\times 3\times X_{1}=0$. However, $X_{0}$ is the smallest
semantically compatible subtree of the big red subtree. Thus, the algorithm
will first replace the red subtree with $X_{0}$, avoiding an unnecessary
replacement of $0\times 3\times X_{1}$ with $0$. Additionally, the algorithm
can perform simplification by leveraging information from different branches.
Look at the subtrees in blue. The semantics of the subtree $3\times X_{1}$ is
the same as that of $X_{1}+X_{1}+X_{1}$. Although both subtrees are on
different branches, this method still identifies this redundancy and replaces
the smallest with the largest.

Figure 2: Illustrative mapping from genotype to phenotype. The genotype is
represented with $G$ (left box), whereas the exact and approximate phenotypes
are represented with $P_{t=0}$ and $P_{t=10}$ (right boxes).

To understand what happens when $t=10$, let’s assume that the result of adding
$X_{3}$ to $X_{0}$ has a small effect on the overall behavior of $T$ because
$X_{3}$ has small values. Formally, $f(\hat{y}_{X_{0}},\hat{y}_{+})\leq
p(10)$; whereas $f(\hat{y}_{X_{3}},\hat{y}_{+})>p(10)$. Thus, $X_{0}$ will
replace the subtree rooted at $+$, resulting in a further simplification. Note
that this time, however, we arrive at an approximation to the phenotype,
smaller but semantically different from that obtained through exact
simplification of the genotype.

##  4 Experiments

###  4.1 Datasets

We assessed our method on five real-world regression problems, which were
standardized to zero mean and a standard deviation of one. Major
characteristics of these datasets can be found in Table 1.

Table 1: Five datasets used in the empirical study. Dataset | #Instances | #Features | Target range
---|---|---|---
Boston (Harrison and Rubinfeld, 1978) | 506 | 13 | [5, 50]
Bioav (Archetti et al., 2006) | 358 | 241 | [0.4, 100.0]
Heating (Tsanas and Xifara, 2012) | 768 | 8 | [6.01, 43.1]
Slump (Yeh, 2009) | 103 | 7 | [0, 29]
Strength (Yeh, 2007) | 1005 | 8 | [0, 1145]

###  4.2 Experimental settings

Table 2 lists the hyper-parameters (HPs) used in this study, along with cross-
validation settings. The HPs were selected following the common practice found
across the literature to avoid a computationally demanding tuning phase. No
limit to tree depth was applied during evolution in order not to interfere
with the evolutionary process and to allow bloat to reveal itself in all its
splendour. Although this resulted in a heavy computational demand during the
experiments, it allowed us to perform an unbiased assessment of monitoring the
phenotypes. We used two sets of experiments: (i) one with a low mutation rate
and high crossover, and (ii) another with a high mutation rate and low
crossover. A low mutation / high crossover encourages a more exploitative
search, whereas a high mutation / low crossover tends towards exploration.
These cases have different implications on the genotype of candidate
solutions: High recombination of already existing genetic material in the
former, and a higher disruption and novelty in the latter. Following previous
studies about bloat (Nordin and Banzhaf, 1995; Nordin et al., 1996), we
expected to observe more bloat to occur with higher crossover rates.

We rely on GPOL (Bakurov et al., 2021) to conduct our experiments. GPOL is a
flexible and efficient multi-purpose optimization library in Python that
covers a wide range of stochastic iterative search algorithms, including GP.
Its modular implementation allows for solving optimization problems, like the
one in this study, and easily incorporates new methods. The library is open-
source and can be found by following  this link. The implementation of the
proposed approach can be found there.

Table 2: Summary of the hyper-parameters. Note that $P(C)$ and $P(M)$ indicate
the crossover and the mutation probabilities, respectively.

Parameters | Values
---|---
№Train/test split | 70/30%
№Cross-validation | Monte-Carlo
№runs | 30
№ generations | 100
Population’s size | 100
Functions ($F$) | {+, -, x, /}
Initialization | RHH (max depth limit of 5)
Selection | tournament with 4% pressure
Genetic operators | {swap crossover, subtree mutation}
$P(C)$ | {0.8, 0.2}
$P(M)$ | {0.2, 0.8}
Maximum depth limit | Not applied
Stopping criteria | Maximum № generations

###  4.3 Experimental findings

This section demonstrates the effects of the GPM on the population dynamics
across five perspectives: size, diversity, fitness, deviation between the
genotype and phenotype semantics, and variation of the proportion of
terminals. Each perspective is studied with two different mutation/crossover
rates (low/high and high/low), provided as sub-figures. The figures report
different perspectives aggregated across all the problems, allowing therefore
for a problem-independent analysis and interpretation. The genotype is
represented by standard TGP, and it is used as a baseline. In the plots, it is
represented as a gray line. The exact phenotype is represented with a black
dashed line, whereas the approximate phenotypes are shown in green, red, blue
and black solid lines, referring to different degrees of approximation (2.5%,
5%, 10%, 20%, respectively).

####  4.3.1 Size

Figure 3 shows the average population length over 100 generations. The subplot
on the left shows the low mutation/high crossover HP setting. On the right,
high mutation/low crossover setting can be found. The inception plots provide
a closer look at the first 5 generations. Analysis of the figure suggests
that:

  * •

Trees in S-TGP (here, the genotype) grow quickly, except for the first 1-2
generations.

  * •

Phenotypes also grow after some generations, but much slower, with the
approximate phenotypes ordered according to the approximation accuracy $t$.

  * •

In early generations, however, average length of the individuals decreases
quickly then slower for phenotypes, but genotypes (what is observed in
standard GP) only from the random start population to the first generation.

  * •

The average length of the individuals is larger when a higher mutation rate is
used for both genotypes and phenotypes.

  * •

The latter observation suggests to us that mutation, unlike what was expected,
is more destructive than crossover for the applications considered. This makes
the evolutionary process foster bloat as a protective measure. Similar results
were found by (Soule and Heckendorn, 2002) where higher mutation provoked
larger growth.

  * •

Monitoring the exact phenotype shows a reduction in average length of
individuals by a factor of 2-3, compared to the genotype.

  * •

Approximate phenotypes show a 10 to 20-fold reduction in average length of
individuals.

  * •

The sudden drop in the size of individuals in the first generation is an
indication that selection prefers small and fitter individuals out of the
randomly composed trees by Ramped-Half-and-Half. Phenotypes stay close or drop
even further in subsequent generations.

Figure 3: Growing average population length of genotypes, exact and
approximate phenotypes, except for first generations (inset). Left: low
mutation/high crossover; Right: high mutation/low crossover.

####  4.3.2 Semantics of Approximate Phenotypes

Figure 4 depicts the semantics mean absolute deviation (SMAD) between the
genotype ($T$) and the respective phenotype approximations ($T_{t},\
t\in\\{2.5,\ 5,\ 10,\ 20\\}$). Specifically, given the training dataset $X$
with $n$ training instances, and the respective outputs of $T$ and $T_{t}$,
represented as $\hat{y}_{T}$ and $\hat{y}_{T_{t}}$, $MAD(\hat{y_{T}},\
\hat{y_{T_{t}}})=\frac{\sum|\hat{y}_{T}-\hat{y}_{T_{t}}|}{n}$. To enhance the
patterns, we neglect the line markers and apply a higher degree of
transparency to those lines representing the intermediate approximations
($t=5\%$ and $t=10\%$). On the left, the low mutation/high crossover HP
setting is shown, whereas the high mutation/low crossover setting can be found
on the right. From the figure, one can notice that:

  * •

In all cases, there is a notable decrease in SMAD in the first generations.
This can be associated with the fact early in evolution that trees are still
more random combinations of program elements rather than refined input-output
mappings. Thus, even mild modification of their structure results in
substantial semantic perturbations when compared to those in later stages of
the evolution.

  * •

In general terms, SMAD exhibits an exponential decay. For $P(M)=0.2$, it is
more pronounced whereas for $P(M)=0.8$ the decay is slower.

  * •

For both mutation rates, one can conclude that the larger the degree of
phenotypic approximation, the larger the SMAD.

  * •

The difference between $t=2.5\%$ and $t=20\%$ is particularly notable: a
higher degree of approximation results in bolder simplification and, thus
larger SMAD.

  * •

When $P(M)=0.8$, the SMAD tends to exhibit significantly larger values, see
the scale of subfigure is different by an order of magnitude.

  * •

This fact might unveil the nature of redundancies between different HPs.
Recall that when $P(M)=0.2$, one expects less exploration diversity, while
with $P(M)=0.8$, a larger diversity is expected.

  * •

More disruptive changes in behavior happen when the search is more
explorative.

Figure 4: Mean absolute deviation between the semantics of the genotype and
the approximated phenotypes. Note the difference in scale.

####  4.3.3 Diversity

Population diversity has been long considered an important characteristic of
the evolutionary process. Losing diversity, especially at the beginning of the
evolution, frequently translates into premature convergence. We here examine
the genotypic diversity and it is defined as the number of unique trees per
generation. Figure 5 depicts the mean of genotypic diversity with columns
representing the two HP settings: low mutation/high crossover on the left, and
high mutation/low crossover on the right.

Analysis of the figure suggests that:

  * •

During the first few generations we find a notable decrease in genotypic
diversity. The decrease is more dramatic, however, for $P(M)=0.2$ as less
exploration takes place.

  * •

Different lines seem to stack one upon the other and the order is a function
of the approximation degree. In other words, the larger the phenotype
approximation, the smaller the diversity of the resulting population.

  * •

In general terms, the diversity exhibits an exponential decay. For a higher
mutation setting, the decay is slower as more exploration takes place.

  * •

There is an exception to the trend lines, however, when looking at the
genotypic diversity for $P(M)=0.8$. There, the individual genotypes tend to be
distinct in terms of their genomes across the evolutionary run.

  * •

After 40-50 generations of the evolutionary process, the number of unique
trees for the approximated phenotypes converges to a small range, around
15-25. This is observed for both for $P(M)=0.2$ and $P(M)=0.8$. In other
words, the genotypic diversity of the populations consisting of the
approximated phenotype converges to the same level, regardless of the
crossover/mutation rates.

  * •

We can observe a growing trend for the exact phenotype (black dashed line)
after 20 generations. This can be an indication that even the phenotype is not
protected against bloat. Note that this phenomenon is more pronounced in the
high-mutation setup, which was found to be associated with higher bloat in
Figure 3 (possibly caused by destructive effects of the mutation operator).

Figure 5: Diversity across evolutionary runs. Genotyic diversity stays high
for high mutation scenario.

####  4.3.4 Fitness

For each generation, we record the average population fitness, for both
training and test data. Fitness here is error, so smaller is better. Figure 6
depicts median values for the two different mutation/crossover rates,
represented here in distinct rows. Different columns represent distinct data
partitions: training data on the left, and test on the right. The line markers
were removed and a higher line transparency was used for intermediate levels
of phenotype approximations to highlight the trend. The analysis of the figure
suggests that:

  * •

There is a dramatic improvement in population fitness in the first few
generations, which can be related to diversity loss.

  * •

In general terms, fitness/error exhibits an exponential reduction. For a
higher mutation setting, the decay is slower as more exploration takes place.

  * •

The smaller the phenotype approximation accuracy, the better the fitness of
the resulting individuals. That is to say, approximated phenotypes in the
population tend to exhibit better fitness.

  * •

Fitness progress achieved with $P(M)=0.8$ are notably larger than those
observed for $P(M)=0.2$, particularly in the first half of runs.

  * •

The conclusions hold for both training and test data.

Figure 6: Median fitness in the population. Approximate phenotypes exhibit
better fitness.

Figure 7 shows the median fitness of the best/elite individuals (selected on
the training data). The structure of the figure conforms to that of Figure 6.
Unlike what was observed with population fitness, larger phenotypic
approximation results in virtually no progress in elite fitness.

Figure 7: Median fitness of elite individuals. The fitness of phenotypes
deteriorates with approximation.

It is important to clarify the nature of the overlap between the lines
representing the exact phenotype (black dashed line) and the genotype (gray
solid line): Their semantics are expected to be the same. There is, however,
some rare mismatch as a consequence of minor floating-point rounding errors
that occasionally occur in large trees, percolating through the tree. From all
the generated results, these correspond to 1% of cases and mostly regard one
of the problems.

####  4.3.5 Structure

Figure 8 shows the proportion of terminals (input features and constants) in
trees during evolutionary runs. The rest of the nodes are operators. We can
observe that:

  * •

Genotypes exhibit a notable reduction of terminal proportion in the first few
generations. This is associated with a growth in tree depth, reflected in a
larger amount of function nodes.

  * •

Later in the search, the proportion of terminals stabilizes around 35-40%.

  * •

As was previously observed in other figures, lines tend to follow an order as
a function of the approximation degree.

  * •

The rougher the approximation, the larger the proportion of terminals to
functions. This is expected since rougher approximation results in smaller
phenotypic trees, with a smaller number of levels and fewer function nodes.

  * •

A larger proportion of terminals in the phenotypes can be observed with a
higher mutation rate (suplot on the right). We consider this to be related to
the fact that the extent of simplification is larger for this setting, as it
was already observed in Figure 3.

Figure 8: Terminal nodes percentage in the elite trees. Being smaller,
phenotypes have a higher percentage of terminals.

Figure 9 provides an example of the exact ($t=0$) and approximated
($t=\\{2.5,5,10,20\\}$) phenotype(s) for the elite observed at generation 95
of run 2 for the Slump problem. The genotype ($G$) is represented in the gray
box. The exact phenotype is represented in the upper left box ($P_{\\{0,\
2.5\\}}$), obtained by removing the red subtree, due to zero constant
multiplication (nodes circled red). This happens to be the same phenotype as
for the approximate phenotype with $t=2.5\%$ which did not produce a smaller
tree. The rougher approximations consist of single-node trees, which are of
small utility for this application.

Figure 9: Genotype and exact/approximated phenotypes from a run on the Slump
problem. See text for details.

##  5 Conclusions

Traditionally, only the genotype has been considered in Tree Genetic
Programming (TGP). Here we study the notion of phenotype and its relationship
to the genotype in TGP to clarify what evolved solutions truly predict. We
developed a unique simplification method that maps a genotype to its phenotype
by removing semantically ineffective code from the genotype. This mapping
shows that phenotypes are hidden within the larger genotypic trees but can be
extracted via simplification, achieving a size reduction of up to 20 folds,
which facilitates understanding. We also study how simplification affects
population dynamics. Particularly, analysis of the diversity suggests that the
genotype population is normally based on a small number of unique phenotypes,
even when evolution is more explorative. Moreover, when the approximated
phenotype is extracted, larger semantic perturbations are observed in the
early stages of evolution. Finally, approximated phenotypes allow for better
population fitness, although elite solutions show deterioration when
approximated. While this constitutes valuable insights for future research
directions, such as the development of new bloat control methods, we are now
working on improving the efficiency of the simplification algorithm.

## References

  * Ain et al. [2022] Qurrat Ul Ain, Harith Al-Sahaf, Bing Xue, and Mengjie Zhang.  Genetic programming for automatic skin cancer image classification.  _Expert Systems with Applications_ , 197:116680, 2022.  ISSN 0957-4174.  doi:https://doi.org/10.1016/j.eswa.2022.116680.  URL https://www.sciencedirect.com/science/article/pii/S0957417422001634.
  * Alfaro-Cid et al. [2010] Eva Alfaro-Cid, JJ Merelo, F Fernández de Vega, Anna Isabel Esparcia-Alcázar, and Ken Sharman.  Bloat control operators and diversity in genetic programming: A comparative study.  _Evolutionary Computation_ , 18(2):305–332, 2010.
  * Altenberg [1994] Lee Altenberg.  The Evolution of Evolvability in Genetic Programming.  In _Advances in Genetic Programming, Volume 1_ , pages 47–74. The MIT Press, 01 1994.  ISBN 9780262277181.  doi:10.7551/mitpress/1108.003.0008.  URL https://doi.org/10.7551/mitpress/1108.003.0008.
  * Angeline [1994] Peter J. Angeline.  _Genetic Programming and Emergent Intelligence_ , page 75–97.  MIT Press, Cambridge, MA, USA, 1994.  ISBN 0262111888.
  * Archetti et al. [2006] Francesco Archetti, Stefano Lanzeni, Enza Messina, and Leonardo Vanneschi.  Genetic programming for human oral bioavailability of drugs.  GECCO ’06, page 255–262, New York, NY, USA, 2006. Association for Computing Machinery.  ISBN 1595931864.  doi:10.1145/1143997.1144042.  URL https://doi.org/10.1145/1143997.1144042.
  * Assunção et al. [2019] Filipe Assunção, Nuno Lourenço, Penousal Machado, and Bernardete Ribeiro.  Denser: deep evolutionary network structured representation.  _Genetic Programming and Evolvable Machines_ , 20(1):5–35, March 1 2019.  ISSN 1573-7632.  doi:10.1007/s10710-018-9339-y.  URL https://doi.org/10.1007/s10710-018-9339-y.
  * Bakurov et al. [2021] Illya Bakurov, Marco Buzzelli, Mauro Castelli, Leonardo Vanneschi, and Raimondo Schettini.  General purpose optimization library (gpol): A flexible and efficient multi-purpose optimization library in python.  _Applied Sciences_ , 11(11), 2021.  ISSN 2076-3417.  doi:10.3390/app11114774.  URL https://www.mdpi.com/2076-3417/11/11/4774.
  * Bakurov et al. [2023a] Illya Bakurov, Marco Buzzelli, Raimondo Schettini, Mauro Castelli, and Leonardo Vanneschi.  Full-reference image quality expression via genetic programming.  _IEEE Transactions on Image Processing_ , 32:1458–1473, 2023a.  doi:10.1109/TIP.2023.3244662.
  * Bakurov et al. [2023b] Illya Bakurov, Marco Buzzelli, Raimondo Schettini, Mauro Castelli, and Leonardo Vanneschi.  Semantic segmentation network stacking with genetic programming.  _Genetic Programming and Evolvable Machines_ , 24(2):Article number: 15, December 2023b.  ISSN 1389-2576.  doi:doi:10.1007/s10710-023-09464-0.  URL https://rdcu.be/drZeF.  Special Issue on Highlights of Genetic Programming 2022 Events.
  * Banzhaf and Langdon [2002] Wolfgang Banzhaf and William B. Langdon.  Some considerations on the reason for bloat.  _Genetic Programming and Evolvable Machines_ , 3:81–91, 2002.
  * Banzhaf et al. [1998] Wolfgang Banzhaf, Frank D. Francone, Robert E. Keller, and Peter Nordin.  _Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications_.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1998.  ISBN 155860510X.
  * Banzhaf et al. [2024] Wolfgang Banzhaf, Ting Hu, and Gabriela Ochoa.  How the combinatorics of neutral spaces leads genetic programming to discover simple solutions.  _Genetic Programming Theory and Practice XX_ , pages 1–22, 2024.
  * Blickle and Thiele [1994] Tobias Blickle and Lothar Thiele.  Genetic programming and redundancy.  In J. Hopf, editor, _Genetic Algorithms within the Framework of Evolutionary Computation (Workshop at KI-94, Saarbrücken)_ , pages 33–38, Im Stadtwald, Building 44, D-66123 Saarbrücken, Germany, 1994. Max-Planck-Institut für Informatik (MPI-I-94-241).  URL http://www.tik.ee.ethz.ch/~tec/publications/bt94/GPandRedundancy.ps.gz.
  * Brameier and Banzhaf [2007] M.F. Brameier and W. Banzhaf.  _Linear Genetic Programming_.  Genetic and Evolutionary Computation. Springer US, 2007.  ISBN 9780387310305.  URL https://books.google.com/books?id=AhZJ9SIChnQC.
  * C. [2017] Richard Boland C.  Non-coding rna: It’s not junk.  _Digestive Diseases and Sciences_ , 62(4):1107–1109, 2017.  doi:10.1007/s10620-017-4506-1.  URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5433430/.
  * Castelli and Manzoni [2019] Mauro Castelli and Luca Manzoni.  Gsgp-c++ 2.0: A geometric semantic genetic programming framework.  _SoftwareX_ , 10:100313, 2019.  ISSN 2352-7110.  doi:https://doi.org/10.1016/j.softx.2019.100313.  URL https://www.sciencedirect.com/science/article/pii/S2352711019301736.
  * Correia et al. [2022] João Correia, Daniel Lopes, Leonardo Vieira, Nereida Rodriguez-Fernandez, Adrian Carballal, Juan Romero, and Penousal Machado.  Experiments in evolutionary image enhancement with elaine.  _Genetic Programming and Evolvable Machines_ , 23(4):557–579, dec 2022.  ISSN 1389-2576.  doi:10.1007/s10710-022-09445-9.  URL https://doi.org/10.1007/s10710-022-09445-9.
  * Correia et al. [2021] João Correia, Leonardo Vieira, Nereida Rodriguez-Fernandez, Juan Romero, and Penousal Machado.  Evolving image enhancement pipelines.  In Juan Romero, Tiago Martins, and Nereida Rodríguez-Fernández, editors, _Artificial Intelligence in Music, Sound, Art and Design_ , pages 82–97, Cham, 2021. Springer International Publishing.  ISBN 978-3-030-72914-1.
  * Cortacero et al. [2023] Kévin Cortacero, Brienne McKenzie, Sabina Müller, Roxana Khazen, Fanny Lafouresse, Gaëlle Corsaut, Nathalie Van Acker, François-Xavier Frenois, Laurence Lamant, Nicolas Meyer, Béatrice Vergier, Dennis G. Wilson, Hervé Luga, Oskar Staufer, Michael L. Dustin, Salvatore Valitutti, and Sylvain Cussat-Blanc.  Evolutionary design of explainable algorithms for biomedical image segmentation.  _Nature Communications_ , 14(1):7112, 2023.  ISSN 2041-1723.  doi:10.1038/s41467-023-42664-x.  URL https://doi.org/10.1038/s41467-023-42664-x.
  * Cussat-Blanc et al. [2019] Sylvain Cussat-Blanc, Kyle Harrington, and Wolfgang Banzhaf.  Artificial gene regulatory networks—a review.  _Artificial life_ , 24(4):296–328, 2019.
  * de Vega et al. [2020a] Francisco Fernández de Vega, Gustavo Olague, Francisco Chávez, Daniel Lanza, Wolfgang Banzhaf, and Erik Goodman.  It is time for new perspectives on how to fight bloat in gp.  _Genetic Programming Theory and Practice XVII_ , pages 25–38, 2020a.
  * de Vega et al. [2020b] Francisco Fernández de Vega, Gustavo Olague, Daniel Lanza, Wolfgang Banzhaf, Erik Goodman, Jose Menendez-Clavijo, Axel Martinez, et al.  Time and individual duration in genetic programming.  _IEEE Access_ , 8:38692–38713, 2020b.
  * de Vienne [2022] Dominique de Vienne.  What is a phenotype? history and new developments of the concept.  _Genetica_ , 150(3):153–158, 2022.
  * Dignum and Poli [2007] Stephen Dignum and Riccardo Poli.  Generalisation of the limiting distribution of program sizes in tree-based genetic programming and analysis of its effects on bloat.  In _Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation_ , GECCO ’07, page 1588–1595, New York, NY, USA, 2007. Association for Computing Machinery.  ISBN 9781595936974.  doi:10.1145/1276958.1277277.  URL https://doi.org/10.1145/1276958.1277277.
  * Dignum and Poli [2008a] Stephen Dignum and Riccardo Poli.  Crossover, sampling, bloat and the harmful effects of size limits.  In Michael O’Neill, Leonardo Vanneschi, Steven Gustafson, Anna Isabel Esparcia Alcázar, Ivanoe De Falco, Antonio Della Cioppa, and Ernesto Tarantino, editors, _Genetic Programming_ , pages 158–169, Berlin, Heidelberg, 2008a. Springer Berlin Heidelberg.  ISBN 978-3-540-78671-9.
  * Dignum and Poli [2008b] Stephen Dignum and Riccardo Poli.  Operator equalisation and bloat free gp.  In _European Conference on Genetic Programming_ , 2008b.  URL https://api.semanticscholar.org/CorpusID:1863814.
  * Evans et al. [2019] Benjamin P. Evans, Bing Xue, and Mengjie Zhang.  What’s inside the black-box? a genetic programming method for interpreting complex machine learning models.  GECCO ’19, page 1012–1020, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450361118.  doi:10.1145/3321707.3321726.  URL https://doi.org/10.1145/3321707.3321726.
  * Gilbert [1978] Walter Gilbert.  Why genes in pieces?  _Nature_ , 271, 1978.  ISSN 1476-4687.  doi:10.1038/271501a0.  URL https://doi.org/10.1038/271501a0.
  * Goncalves et al. [2015] Ivo Goncalves, Sara Silva, and Carlos M. Fonseca.  Semantic learning machine: A feedforward neural network construction algorithm inspired by geometric semantic genetic programming.  In Francisco C. Pereira, Penousal Machado, Ernesto Costa, and Amilcar Cardoso, editors, _Progress in Artificial Intelligence - 17th Portuguese Conference on Artificial Intelligence, EPIA 2015_ , volume 9273 of _Lecture Notes in Computer Science_ , pages 280–285, Coimbra, Portugal, September 8-11 2015. Springer.  doi:doi:10.1007/978-3-319-23485-4_28.  URL http://dx.doi.org/10.1007/978-3-319-23485-4.
  * Harrison and Rubinfeld [1978] David Harrison and Daniel L Rubinfeld.  Hedonic housing prices and the demand for clean air.  _Journal of Environmental Economics and Management_ , 5(1):81–102, 1978.  ISSN 0095-0696.  doi:https://doi.org/10.1016/0095-0696(78)90006-2.  URL https://www.sciencedirect.com/science/article/pii/0095069678900062.
  * Haut et al. [2023] Nathan Haut, Bill Punch, and Wolfgang Banzhaf.  Active learning informs symbolic regression model development in genetic programming.  In _Proceedings of the Companion Conference on Genetic and Evolutionary Computation_ , GECCO ’23 Companion, page 587–590, New York, NY, USA, 2023. Association for Computing Machinery.  ISBN 9798400701207.  doi:10.1145/3583133.3590577.  URL https://doi.org/10.1145/3583133.3590577.
  * Ingalalli et al. [2014] Vijay Ingalalli, Sara Silva, Mauro Castelli, and Leonardo Vanneschi.  A multi-dimensional genetic programming approach for multi-class classification problems.  In Miguel Nicolau, Krzysztof Krawiec, Malcolm I. Heywood, Mauro Castelli, Pablo García-Sánchez, Juan J. Merelo, Victor M. Rivas Santos, and Kevin Sim, editors, _Genetic Programming_ , pages 48–60, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.  ISBN 978-3-662-44303-3.
  * Iqbal et al. [2017] Muhammad Iqbal, Bing Xue, Harith Al-Sahaf, and Mengjie Zhang.  Cross-domain reuse of extracted knowledge in genetic programming for image classification.  _IEEE Transactions on Evolutionary Computation_ , 21(4):569–587, 2017.  doi:10.1109/TEVC.2017.2657556.
  * Jackson [2010] David Jackson.  The identification and exploitation of dormancy in genetic programming.  _Genetic Programming and Evolvable Machines_ , 11(1):89–121, mar 2010.  ISSN 1389-2576.  doi:10.1007/s10710-009-9086-1.  URL https://doi.org/10.1007/s10710-009-9086-1.
  * Javed et al. [2022] Noman Javed, Fernand Gobet, and Peter Lane.  Simplification of genetic programs: a literature survey.  _Data Mining and Knowledge Discovery_ , 36(4):1279–1300, 07 2022.  doi:10.1007/s10618-022-00830-7.  URL https://doi.org/10.1007/s10618-022-00830-7.
  * Kinzett et al. [2009] David Kinzett, Mark Johnston, and Mengjie Zhang.  Numerical simplification for bloat control and analysis of building blocks in genetic programming.  _Evolutionary Intelligence_ , 2:151–168, 2009.
  * Kirschner and Gerhart [2005] Marc W Kirschner and John C Gerhart.  _The plausibility of life: Resolving Darwin’s dilemma_.  Yale University Press, 2005.
  * Koza [1992] J.R. Koza.  _Genetic Programming: On the Programming of Computers by Means of Natural Selection_.  MIT Press, 1992.
  * La Cava et al. [2016] William La Cava, Lee Spector, and Kourosh Danai.  Epsilon-lexicase selection for regression.  In _Proceedings of the Genetic and Evolutionary Computation Conference 2016_ , GECCO ’16, page 741–748, New York, NY, USA, 2016. Association for Computing Machinery.  ISBN 9781450342063.  doi:10.1145/2908812.2908898.  URL https://doi.org/10.1145/2908812.2908898.
  * La Cava et al. [2019] William La Cava, Sara Silva, Kourosh Danai, Lee Spector, Leonardo Vanneschi, and Jason H. Moore.  Multidimensional genetic programming for multiclass classification.  _Swarm and Evolutionary Computation_ , 44:260–272, 2019.  ISSN 2210-6502.  doi:https://doi.org/10.1016/j.swevo.2018.03.015.  URL https://www.sciencedirect.com/science/article/pii/S2210650217309136.
  * Langdon and Poli [1998a] W. B. Langdon and R. Poli.  Fitness causes bloat.  In P. K. Chawdhry, R. Roy, and R. K. Pant, editors, _Soft Computing in Engineering Design and Manufacturing_ , pages 13–22, London, 1998a. Springer London.  ISBN 978-1-4471-0427-8.
  * Langdon and Poli [1998b] W. B. Langdon and R. Poli.  Fitness causes bloat: Mutation.  In Wolfgang Banzhaf, Riccardo Poli, Marc Schoenauer, and Terence C. Fogarty, editors, _Genetic Programming_ , pages 37–48, Berlin, Heidelberg, 1998b. Springer Berlin Heidelberg.  ISBN 978-3-540-69758-9.
  * Langdon et al. [1999] W. B. Langdon, T. Soule, R. Poli, and J. A . Foster.  The Evolution of Size and Shape.  In _Advances in Genetic Programming, Volume 3_. The MIT Press, 07 1999.  ISBN 9780262284127.  doi:10.7551/mitpress/1110.003.0012.  URL https://doi.org/10.7551/mitpress/1110.003.0012.
  * Langdon and Poli [2002] William B. Langdon and Riccardo Poli.  _Foundations of Genetic Programming_.  2002\.  URL https://api.semanticscholar.org/CorpusID:13348347.
  * Lensen et al. [2022] Andrew Lensen, Bing Xue, and Mengjie Zhang.  Genetic programming for manifold learning: Preserving local topology.  _IEEE Transactions on Evolutionary Computation_ , 26(4):661–675, 2022.  doi:10.1109/TEVC.2021.3106672.
  * Litwack [2022] Gerald Litwack.  Chapter 10 - nucleic acids and molecular genetics.  In Gerald Litwack, editor, _Human Biochemistry (Second Edition)_ , pages 287–356. Academic Press, Boston, second edition edition, 2022.  ISBN 978-0-323-85718-5.  doi:https://doi.org/10.1016/B978-0-323-85718-5.00010-8.  URL https://www.sciencedirect.com/science/article/pii/B9780323857185000108.
  * Luke and Panait [2002] Sean Luke and Liviu Panait.  Fighting bloat with nonparametric parsimony pressure.  In Juan Julián Merelo Guervós, Panagiotis Adamidis, Hans-Georg Beyer, Hans-Paul Schwefel, and José-Luis Fernández-Villacañas, editors, _Parallel Problem Solving from Nature — PPSN VII_ , pages 411–421, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.  ISBN 978-3-540-45712-1.
  * Markus et al. [2021] Aniek F. Markus, Jan A. Kors, and Peter R. Rijnbeek.  The role of explainability in creating trustworthy artificial intelligence for health care: A comprehensive survey of the terminology, design choices, and evaluation strategies.  _Journal of Biomedical Informatics_ , 113:103655, 2021.  ISSN 1532-0464.  doi:https://doi.org/10.1016/j.jbi.2020.103655.  URL https://www.sciencedirect.com/science/article/pii/S1532046420302835.
  * McPhee and Miller [1995] Nicholas Freitag McPhee and Justin Darwin Miller.  Accurate replication in genetic programming.  In _Proceedings of the 6th International Conference on Genetic Algorithms_ , page 303–309, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.  ISBN 1558603700.
  * Mitchell et al. [1993] Melanie Mitchell, John Holland, and Stephanie Forrest.  When will a genetic algorithm outperform hill climbing.  In J. Cowan, G. Tesauro, and J. Alspector, editors, _Advances in Neural Information Processing Systems_ , volume 6. Morgan-Kaufmann, 1993.  URL https://proceedings.neurips.cc/paper_files/paper/1993/file/ab88b15733f543179858600245108dd8-Paper.pdf.
  * Moraglio et al. [2012] Alberto Moraglio, Krzysztof Krawiec, and Colin G. Johnson.  Geometric semantic genetic programming.  In Carlos A. Coello Coello, Vincenzo Cutello, Kalyanmoy Deb, Stephanie Forrest, Giuseppe Nicosia, and Mario Pavone, editors, _Parallel Problem Solving from Nature - PPSN XII_ , pages 21–31, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.  ISBN 978-3-642-32937-1.
  * Mori et al. [2008] Naoki Mori, Bob McKay, Nguyen Xuan Hoai, Daryl Essam, and Saori Takeuchi.  A new method for simplifying algebraic expressions in genetic programming called equivalent decision simplification.  In _SCIS & ISIS SCIS & ISIS 2008_, pages 1671–1676. Japan Society for Fuzzy Theory and Intelligent Informatics, 2008.
  * Muñoz et al. [2015] Luis Muñoz, Sara Silva, and Leonardo Trujillo.  M3gp – multiclass classification with gp.  In Penousal Machado, Malcolm I. Heywood, James McDermott, Mauro Castelli, Pablo García-Sánchez, Paolo Burelli, Sebastian Risi, and Kevin Sim, editors, _Genetic Programming_ , pages 78–91, Cham, 2015. Springer International Publishing.  ISBN 978-3-319-16501-1.
  * Neshatian et al. [2012] Kourosh Neshatian, Mengjie Zhang, and Peter Andreae.  A filter approach to multiple feature construction for symbolic learning classifiers using genetic programming.  _IEEE Transactions on Evolutionary Computation_ , 16(5):645–661, 2012.  doi:10.1109/TEVC.2011.2166158.
  * Nguyen and Chu [2020] Quang Uy Nguyen and Thi Huong Chu.  Semantic approximation for reducing code bloat in genetic programming.  _Swarm and Evolutionary Computation_ , 58:100729, 2020.
  * Nordin and Banzhaf [1995] Peter Nordin and W. Banzhaf.  Complexity compression and evolution.  In _International Conference on Genetic Algorithms_ , pages 310–317, 1995.  URL https://api.semanticscholar.org/CorpusID:16415863.
  * Nordin et al. [1996] Peter Nordin, Frank Francone, and Wolfgang Banzhaf.  Explicitly Defined Introns and Destructive Crossover in Genetic Programming.  In _Advances in Genetic Programming, Volume 2_. The MIT Press, 10 1996.  ISBN 9780262290791.  doi:10.7551/mitpress/1109.003.0010.  URL https://doi.org/10.7551/mitpress/1109.003.0010.
  * Olson and Moore [2019] Randal S. Olson and Jason H. Moore.  _TPOT: A Tree-Based Pipeline Optimization Tool for Automating Machine Learning_ , pages 151–160.  Springer International Publishing, Cham, 2019.  ISBN 978-3-030-05318-5.  doi:10.1007/978-3-030-05318-5_8.  URL https://doi.org/10.1007/978-3-030-05318-5_8.
  * Poli [2003] Riccardo Poli.  A simple but theoretically-motivated method to control bloat in genetic programming.  In _European Conference on Genetic Programming_ , pages 204–217. Springer, 2003.
  * Poli et al. [2008] Riccardo Poli, Nicholas Freitag McPhee, and Leonardo Vanneschi.  Elitism reduces bloat in genetic programming.  In _Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation_ , GECCO ’08, page 1343–1344, New York, NY, USA, 2008. Association for Computing Machinery.  ISBN 9781605581309.  doi:10.1145/1389095.1389355.  URL https://doi.org/10.1145/1389095.1389355.
  * Rockett [2020] Peter Rockett.  Pruning of genetic programming trees using permutation tests.  _Evolutionary Intelligence_ , 13(4):649–661, 2020.  doi:doi:10.1007/s12065-020-00379-8.  URL https://rdcu.be/cU470.
  * Silva [2011] Sara Silva.  Reassembling operator equalisation: A secret revealed.  In _Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation_ , GECCO ’11, page 1395–1402, New York, NY, USA, 2011. Association for Computing Machinery.  ISBN 9781450305570.  doi:10.1145/2001576.2001764.  URL https://doi.org/10.1145/2001576.2001764.
  * Silva and Costa [2009] Sara Silva and Ernesto Costa.  Dynamic limits for bloat control in genetic programming and a review of past and current bloat theories.  _Genetic Programming and Evolvable Machines_ , 10:141–179, 2009.  URL https://api.semanticscholar.org/CorpusID:10925054.
  * Silva and Vanneschi [2009] Sara Silva and Leonardo Vanneschi.  Operator equalisation, bloat and overfitting: A study on human oral bioavailability prediction.  In _Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation_ , GECCO ’09, page 1115–1122, New York, NY, USA, 2009. Association for Computing Machinery.  ISBN 9781605583259.  doi:10.1145/1569901.1570051.  URL https://doi.org/10.1145/1569901.1570051.
  * Silva and Vanneschi [2012] Sara Silva and Leonardo Vanneschi.  Bloat free genetic programming: Application to human oral bioavailability prediction.  _Int. J. Data Min. Bioinformatics_ , 6(6):585–601, nov 2012.  ISSN 1748-5673.  doi:10.1504/IJDMB.2012.050266.  URL https://doi.org/10.1504/IJDMB.2012.050266.
  * Soule and Heckendorn [2002] Terence Soule and Robert B. Heckendorn.  An analysis of the causes of code growth in genetic programming.  _Genetic Programming and Evolvable Machines_ , 3(3):283–309, September 2002.  ISSN 1389-2576.  doi:doi:10.1023/A:1020115409250.
  * Spector and Helmuth [2014] Lee Spector and Thomas Helmuth.  Effective simplification of evolved push programs using a simple, stochastic hill-climber.  In _Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation_ , pages 147–148, 2014.
  * Tackett [1994] Walter Alden Tackett.  _Recombination, Selection, and the Genetic Construction of Computer Programs_.  PhD thesis, USA, 1994.
  * Tran et al. [2019] Binh Tran, Bing Xue, and Mengjie Zhang.  Genetic programming for multiple-feature construction on high-dimensional classification.  _Pattern Recognition_ , 93:404–417, 2019.  ISSN 0031-3203.  doi:https://doi.org/10.1016/j.patcog.2019.05.006.  URL https://www.sciencedirect.com/science/article/pii/S0031320319301815.
  * Tsanas and Xifara [2012] Athanasios Tsanas and Angeliki Xifara.  Accurate quantitative estimation of energy performance of residential buildings using statistical machine learning tools.  _Energy and Buildings_ , 49:560–567, 2012.  ISSN 0378-7788.  doi:https://doi.org/10.1016/j.enbuild.2012.03.003.  URL https://www.sciencedirect.com/science/article/pii/S037877881200151X.
  * Ul Ain et al. [2017] Qurrat Ul Ain, Bing Xue, Harith Al-Sahaf, and Mengjie Zhang.  Genetic programming for skin cancer detection in dermoscopic images.  In _2017 IEEE Congress on Evolutionary Computation (CEC)_ , page 2420–2427. IEEE Press, 2017.  doi:10.1109/CEC.2017.7969598.  URL https://doi.org/10.1109/CEC.2017.7969598.
  * Vainio-Pekka et al. [2023] Heidi Vainio-Pekka, Mamia Ori-Otse Agbese, Marianna Jantunen, Ville Vakkuri, Tommi Mikkonen, Rebekah Rousi, and Pekka Abrahamsson.  The role of explainable ai in the research field of ai ethics.  _ACM Trans. Interact. Intell. Syst._ , 13(4), dec 2023.  ISSN 2160-6455.  doi:10.1145/3599974.  URL https://doi.org/10.1145/3599974.
  * Whigham and Dick [2009] Peter A Whigham and Grant Dick.  Implicitly controlling bloat in genetic programming.  _IEEE Transactions on Evolutionary Computation_ , 14(2):173–190, 2009.
  * Wong and Zhang [2006] Phillip Wong and Mengjie Zhang.  Algebraic simplification of gp programs during evolution.  In _Proc. 8th Annual Conference on Genetic and Evolutionary Computation (GECCO-2006)_ , pages 927–934. ACM Press, New York, 2006.
  * Wu and Lindsay [1996] Annie S. Wu and Robert K. Lindsay.  A survey of intron research in genetics.  In Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, and Hans-Paul Schwefel, editors, _Parallel Problem Solving from Nature — PPSN IV_ , pages 101–110, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg.  ISBN 978-3-540-70668-7.
  * Yeh [2007] I-Cheng Yeh.  Concrete Compressive Strength.  UCI Machine Learning Repository, 2007.  DOI: https://doi.org/10.24432/C5PK67.
  * Yeh [2009] I-Cheng Yeh.  Concrete Slump Test.  UCI Machine Learning Repository, 2009.  DOI: https://doi.org/10.24432/C5FG7D.
  * Zhang and Smart [2004] Mengjie Zhang and Will Smart.  Multiclass object classification using genetic programming.  In Günther R. Raidl, Stefano Cagnoni, Jürgen Branke, David Wolfe Corne, Rolf Drechsler, Yaochu Jin, Colin G. Johnson, Penousal Machado, Elena Marchiori, Franz Rothlauf, George D. Smith, and Giovanni Squillero, editors, _Applications of Evolutionary Computing_ , pages 369–378, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.  ISBN 978-3-540-24653-4.