Year: 2021

Abstract:
Genetic Programming (GP) represents a powerful paradigm in diverse real-world applications. While GP can reach optimal (or at least “good-enough”) solutions for many problems, such solutions are not without deficiencies. A frequent issue stems from the representation perspective where GP evolves solutions that contain unnecessary parts, known as program bloat. This paper first investigates a combination of deterministic and random simplification to simplify the solutions while having a (relatively) small influence on the solution fitness. Afterward, we use the solutions to extract their subtrees, which we denote as winning trees. The winning trees can be used to initialize the population for the new GP run and result in improved convergence and fitness, provided some conditions on the size of solutions and winning trees are fulfilled. To experimentally validate our approach, we consider several synthetic benchmark problems and real-world symbolic regression problems.

heading: 1 INTRODUCTION
text: Genetic programming (GP) is an evolutionary algorithm (EA) used to automatically generate computer programs to solve specific tasks (Koza, 1992). Up to now, GP has been used in diverse domains like image analysis (Varniab et al., 2020), cybersecurity (Picek et al., 2018), or scheduling (Nguyen et al., 2017). What differentiates GP from other types of evolutionary algorithms is the fact that the solutions are commonly represented as expression trees. Naturally, due to a specific solution representation, appropriate variation operators need to be used. Unfortunately, while being very successful in diverse domains, GP also faces certain representation-specific problems. Indeed, the GP process will introduce redundancy and functionally useless sections of programs, commonly denoted as program bloat (Koza, 1992; Blickle et al., 1994).
Program bloat can cause various issues to the GP process. As a consequence of bloat, the evolution process can prematurely terminate and explore large parts of the search space that are not promising. Since the solutions with program bloat will be more complex than needed, the interpretability of solutions will suffer. Additionally, program bloat can be connected with some forms of building blocks, i.e., parts of the solutions that can be combined to form even more fit solutions.
As there are no universal ways to deal with program bloat, this problem is difficult. Commonly used methods are mostly based on applying various forms of simplification to reduce the complexity of a solution and eliminate any useless details. While such techniques can reduce program bloat, there are further questions to consider. For instance, simplification can be done at the end of the evolution process (Hooper & Flann, 1996) but also during the evolution process (Wong & Zhang, 2006; 2007). As simplification will reduce redundancy, it can also have negative effects on the diversity of the obtained solutions and decrease the protection of useful building blocks within solutions from the destructive nature of the crossover operator (Blickle et al., 1994).
Numerous works have explored the issues of program bloat or how to simplify the GP solutions as discussed in Section 2. What is more, multiple works have discussed the notion of building blocks for GP (Langdon & Poli, 2002), but a widely accepted definition for building blocks is still not agreed upon. A somewhat similar concept to building blocks has been recently discussed in the deep learning community. There, the Lottery Ticket Hypothesis for artificial neural networks discussed
how “...a randomly initialized dense neural network contains a sub-network that is initialized such that, when trained in isolation, can match the test accuracy of the original network after training for at most the same number of iterations.”, which surmises the existence of a “winning ticket” for neural networks (Frankle & Carbin, 2019). This opens up the question of the existence of something like winning tickets for GP.
This work considers simplifications (both exact and heuristic ones) in tree-based GP applied for symbolic regression, and we show that building blocks play an important role. More precisely, our contributions are:
• We present a new technique to conduct heuristic simplification for GP. We combine the heuristic simplification with the exact one, allowing us to reduce the tree sizes significantly. • We discuss a new concept in GP that we denote as winning trees. While there are similarities between winning trees and building blocks, the main differences stem from the fact that the winning trees have constraints on fitness and tree depth. We introduce the notion of winning trees to help us understand better how to guide the evolutionary process to highly-fit solutions. • We provide extensive experimental analysis to showcase that the evolutionary process when using winning trees can result in 1) more fit solutions, 2) faster convergence, and 3) a more robust evolutionary process. Additionally, we discuss the depth constraints for winning trees and show they work well only if of sufficient size, coupled with the appropriate solution depth.

heading: 2 RELATED WORK
text: Several studies have already dealt with the problem of simplifying the expression trees evolved by GP. These methods can roughly be divided into two groups, methods that simplify the expression without changing the behavior of the original expression and those which, by simplifying the expression, change its behavior compared to the original one. The former group consists mostly of methods that perform algebraic simplification. These methods apply predefined algebraic rules to replace a part of an expression with a simpler but equivalent one. In the literature, such methods are usually denoted as algebraic simplification or editing. Such a method was applied by (Wong & Zhang, 2006), and (Zhang et al., 2006) online during the evolution; the authors defined 30 algebraic rules which were applied to the evolved trees in the population. The algebraic simplification method was combined with hashing, which helped to determine equivalent expressions (Wong & Zhang, 2006; 2007). These methods hash sub-expressions and determine whether certain expressions are equivalent or not based on the hash value. This helps the algebraic procedure to detect situations that would otherwise go undetected.
The second group of simplification methods introduces modifications that can change the expression’s behavior. The idea is to detect parts of the expression that are not meaningful and remove them, although this might affect the numerical outcome. The main question is how to determine which parts of the expression should be eliminated. (Kinzett et al., 2008; 2010) proposed the application of a numerical simplification based on node contribution to reduce the complexity of the evolved trees. (Song et al., 2009) pruned trees by removing a child of an operator with two arguments if, when removed, the removal does not change the output of the node beyond a given threshold. (Garcia-Almanza & Tsang, 2006) proposed a method for tree pruning applied to decision trees used to generate classification rules for financial stock markets. The method consists of extracting rules from a decision tree, evaluating them, and then pruning the rules that did not achieve the expected pruning threshold in the evaluation phase. A constant sub-tree pruning method was proposed by (Rockett, 2020). This pruning scheme replaces a subtree with a constant value. The constant is calculated as the expectation of the subtree, which is replaced on the entire dataset.
Building blocks were first discussed in the context of genetic algorithms as short, low-order, and highly fit schemata that are sampled, recombined, and resampled to provide solutions of higher fitness (Goldberg, 1989). Intuitively, building blocks are small parts of a solution that can be formed into larger, more fit components through genetic operators. Defining a building block for GP is more difficult, where some common (traditional) interpretations are a subtree to a solution tree (Altenberg, 1994), a rooted subtree (Rosca, 1997), and a block of code (Angeline & Kinnear, 1996). In this work, we will follow the work from Langdon and Poli that define building blocks as parts of the solution
that can be combined to form more fit solutions but without any constraints on fitness, length, or order of building blocks (Langdon & Poli, 2002). We note a recent work by O’Neill et al. where the authors discuss transfer learning for GP and how to create valuable material as building blocks dynamically (O’Neill et al., 2017). Still, we consider this work orthogonal to ours as we do not aim at transferability while imposing other constraints.
Since its definition, several studies which focus on the lottery ticket hypothesis have been made. For instance, (Chen et al., 2020) used observations from the work on the lottery ticket hypothesis (Frankle & Carbin, 2019) to find trainable and transferable subnetworks in pre-trained BERT models, which are commonly used in natural language processing. (Frankle et al., 2020) used iterative magnitude pruning (IMP) to determine “whether a neural network optimizes to the same, linearly connected minimum under different samples of SGD noise”.

heading: 3 METHODOLOGY
text: To evaluate the winning trees hypothesis for GP, we need to consider the expressions that GP obtains. There is no guarantee that the expressions obtained by GP are exact (i.e., they represent the exact solution), and at the same time, they can contain many unnecessary subexpressions. This is often true when GP is executed for longer periods, and bloat starts occurring (Luke & Panait, 2006). To mitigate this problem, we introduce two methods for reducing the complexity of the expression trees. We denote these methods as simplification, for the exact procedure and pruning, for the heuristic procedure.

heading: 3.1 SIMPLIFICATION
text: The goal of the simplification approach is to simplify the expression without changing its behavior. Therefore, this approach replaces expressions with equivalent but simpler ones. One such example would be to replace the expression x+ 0 with x since the first one includes two redundant symbols. The rules for simplification in our experiments are based on common algebraic axioms and aim to reduce the size of the expression, such as the example above, and the complete list is given in Appendix A, Table 7. The applied rules are not exhaustive, and more rules can be defined and used. However, the given set of rules has shown to be enough to simplify the obtained expressions.
The simplification is performed using the Compare-Match algorithm proposed in (Steyaert & Flajolet, 1983). The algorithm includes two recursive functions, Match and Compare. The Match function iterates through the expression tree from the root node through all of its subtrees and determines whether it can find a pattern P in the given expression T . If a match is found, then P is replaced by a simpler expression defined for that pattern. Finding patterns is performed by the Compare function, which traverses through the expression tree and returns true if it could locate pattern P in the expression tree, otherwise it returns false. The Compare function applies an additional Map function to retrieve the information about the located pattern. The outline of the method is given in Appendix A, Algorithm 1.

heading: 3.2 PRUNING
text: Unlike simplification, which is exact and does not change the behavior of the expression, the pruning method allows the expression to be simplified by removing parts of it, which will directly influence its output. This means that the expression does not necessarily need to have the same output value for a given input before and after pruning. This technique is performed so that certain elements in the expression are simply replaced by a neutral element for a given operator. For example, in the expression +XY , where X and Y represent arbitrary subexpressions, the expression can be pruned by removing either operand and replacing it with a neutral element for summation, which is 0. Thus, it is possible to obtain either +X0 or +0Y . In that way, one part of the expression can be removed while keeping the rest of the expression fixed. Each binary operator has its neutral element, which for the summation and subtraction are 0, whereas, for multiplication and division, they are equal to 1. Unary operators do not have a neutral element as they represent a single expression. Thus, they are not considered in the pruning process.
The removal of certain subexpressions can change the behavior of the entire expression. To observe how the modifications influence the expression’s behavior (the semantics), we monitor the change in fitness between the original expression and the pruned one. If the fitness improves or stays the same, the change is accepted. Our approach also allows pruning to be performed even if it reduces the fitness compared to the original expression; however, a limit is imposed on how much the simplified expression can be worse than the original one.
The procedure that performs the pruning starts from the root node of the expression tree and traverses the tree. At each node, it replaces the current node with a corresponding neutral element. Then, the new expression is evaluated, and its fitness is compared to the fitness of the original expression. The new expression is accepted if it does not degrade the performance of the original expression beyond a certain degree. In our experiments, we set that the solution should not be degraded beyond 15% of its original quality. Naturally, this parameter can be arbitrarily chosen to balance the complexity and quality of the expressions. If the change is not accepted, then the procedure continues the traversal through the expression tree. Otherwise, if the change was accepted, the procedure is restarted at the root node and traverses the tree again to check whether it is possible to perform additional simplifications. The procedure stops when both the entire expression tree is traversed, and no modification is performed. To the best of our knowledge, this kind of pruning approach for GP has not been applied before.

heading: 3.3 SEARCH FOR WINNING TREES
text: We define winning trees for GP as parts (subtrees) of a solution (tree) that can be formed into larger, more fit components through the use of genetic operators. Differing from building blocks, winning trees have:
• constraints on the fitness value - as they are formed as subtrees of highly fit solutions (trees), and • constraints on the size – as they cannot be arbitrarily small or large.
Note that winning trees are actually subtrees, but we denote them as trees for simplicity.
The candidates for the winning trees will be obtained by first identifying highly fit simplified expressions in the following procedure. A full GP evolution will be executed n times, and the best individual from each run on the training set will be stored. When n individuals are obtained, each of them is simplified by the previously outlined methods in the following way. First, the exact simplification is performed, followed by the heuristic pruning, and then again the exact simplification. The goal of the first exact simplification is to reduce the complexity of the original expression if possible. Since the heuristic pruning needs to evaluate the expression after each change, it is beneficial to start with an already simplified expression to reduce the number of possible evaluations (especially in cases where the fitness function is more complex). After pruning, the exact simplification is again invoked to remove possible redundant elements introduced by the heuristic simplification (for example, when introducing neutral elements in the expression).
After the process mentioned above, the n obtained expressions are considered simplified. Therefore, in our approach, the simplification is performed offline after the GP run has finished. The simplified expressions can then be used as the basis to create subtrees that will be used for the initialization of the initial population of a new GP run. However, using only the complete expressions would not make sense as it would mean that GP would be starting from the best solutions and trying to improve them further (emulating a setting with a longer evolution process). Therefore, smaller subexpressions (winning trees) that are part of the original ones are inserted into the initial population. This is performed by selecting random subtrees (with a defined depth) from the n available expressions. These selected subtrees are then used as individuals in the starting population of a new GP run.
A depth limit for the selected expressions is additionally imposed. If the GP is allowed to evolve expression trees of depth d, then the maximum depth of the randomly selected subtrees is equal to d 2 . In that way, we wish to include smaller subtrees (relative to the maximal depth of the tree) but also ensure that not only small subtrees are included in the new population. Note that we limit the minimal tree depth to 2 for all settings. What is more, the limit on d2 represents an upper bound, which means we also use smaller winning trees. The value d2 was selected arbitrarily, and we leave further investigation on various depths for winning trees for future work.

heading: 4 EXPERIMENTAL SETUP

heading: 4.1 DATASETS
text: To test our hypothesis, we use two symbolic regression benchmark sets. One set is based on existing synthetic benchmark functions whose exact target expressions are known and, as such, can be fitted without error. The second benchmark set consists of several real-world regression datasets for which the exact solution is not known.
Table 8 in Appendix A shows a selected set of ten synthetic symbolic regression problems (Oliveira et al., 2018). This set was selected to include functions of different forms and complexities. All selected functions are either one or two-dimensional. A training set consisting of 10 000 instances and a test set of 1 000 instances were generated for all functions. Both sets contain instances sampled uniformly from the interval [−5, 5]. Table 9 in Appendix A denotes the properties of the datasets for the five real-world regression problems (Dua & Graff, 2017). These sets were divided into the training set containing 70% of instances and the test set containing 30% of instances. Compared to the synthetic benchmark problems, these problems have fewer instances that can be used for training and contain more input variables.

heading: 4.2 GENETIC PROGRAMMING
text: The applied GP uses the steady-state tournament selection with a tournament consisting of three individuals. The population size of the algorithm was set to 500 individuals and the mutation probability to 0.3. The tree depths of 6, 8, and 10 will be used in experiments to test the hypothesis with different expression sizes. The crossover operators included the subtree, context preserving, one point, size fair, and uniform operators, whereas the set of mutation operators contains the subtree, shrink, permutation, node replacement, node complement, hoist, and Gauss mutation operators (Poli et al., 2008). Each time individuals are crossed over or mutated, the operators that will be applied are randomly selected from the set of crossover and mutation operators. The function set contains the addition, subtraction, multiplication, and division operator, as well as the sine, cosine, and square root. In addition to the input variables, the set of terminal nodes also includes numerical constants generated from the interval [−1, 1]. Two stopping criteria were used, the maximum number of evaluations and the maximum number of evaluations without improvement in the best individual. The maximum number of evaluations was set to 500 000, whereas the number of evaluations without improvement was set to 25 000. The fitness function being minimized is the mean squared error between the expected outputs and the output values obtained by the evolved expression for all input values. Each experiment was executed 50 times to obtain statistically significant results.

heading: 5 EXPERIMENTAL RESULTS

heading: 5.1 RESULTS FOR SYNTHETIC BENCHMARKS
text: In the first set of experiments, GP is tasked with finding the expression for ten synthetic benchmark functions, using the three specified maximum tree depths (6, 8, and 10). In every experiment, the fitness of original expressions is denoted as original, whereas the fitness of simplified expressions is denoted as final. Three scenarios were conducted in the experiments. The first scenario, where GP was executed with a random initial population to find the symbolic expression for the given data, is denoted as Random. The expressions obtained from this run are then used as the seeds for the initial population of a second GP execution denoted as SubtreeInit. Since the comparison between those two approaches could be considered unfair, we include an additional experiment in which GP was given twice the number of evaluations than the Random variant to compensate for the additional time that is used when rerunning the GP with a new initial population. This scenario is denoted as Random2x.
Table 1 gives the results for the test set. The experiments demonstrate that the obtained results depend quite heavily on the maximum tree depth. Indeed, for expressions of depth 6, the results demonstrate that the initialization with the winning trees did not improve the results in most cases. However, as the depth of the expressions increases, the results of the SubtreeInit approach improve. This is most evident when using a tree depth of size 10. For the tree depth of 10, the results obtained
by SubtreeInit are equally good or better than the results obtained by both Random or Random2x for all the tested functions. Another interesting result is that the method initialized with winning trees outperformed GP with the random initialization, which was given twice the number of evaluations. This shows that the improvement in the results is not a consequence of the extra time that GP was given. Rather, the good solutions obtained seem to be a direct consequence of the winning trees inserted in the starting population.
Such a behavior can be explained so that the winning trees obtained for tree depth six will be quite small and thus very general. Therefore, GP will still struggle to combine such subtrees in a meaningful way. However, for the larger tree depths, a larger portion of the solution will be transferred. Naturally, this subtree does not have a good fitness by itself since it represents only a part of the expression. However, it is more “specialized” for the considered problem.
UNIVERSALITY OF WINNING TREES
After the initial results, we can investigate whether the winning trees for one problem are universal, i.e., can they also be used to initialize the population when applying GP for a different problem. To test this hypothesis, we selected five function pairs and used the obtained individuals for one function to initialize the population of GP when optimizing the second function. The functions were selected so that in certain cases, similar functions are paired together (Nguyen 12 and Keijzer 16) while, in other cases, functions with completely different behavior are paired together (Nguyen 4 and Keijzer 4). Table 2 shows the results for this experiment. The first function represents the optimized function, while the second represents the one from which the subtrees were used for initialization (e.g., Keijzerf12 subtree Kornsf12 denotes that we optimize function Keijzer 12, and we use subtrees from Korns 12).
The results generally suggest that the winning trees are not universal, since in most cases, the results obtained by the unmatched initialization procedure were worse than those obtained by either the ran-
dom or subtree initialization procedures. Therefore, winning trees seem exclusive to the considered problem and cannot be reused across different problems. As such, this is an indication that winning trees represent a specialization of building blocks in GP.

heading: 5.2 RESULTS FOR THE REAL-WORLD DATASETS
text: Table 3 gives the results obtained by GP when using random initialization, whereas Table 4 presents the results obtained when the population is initialized by winning trees obtained from the initial run. For the first two test problems, namely AFN and CCP, it is evident that initializing the population with winning trees improves the overall results. For the other three, the results are more evenly matched. This is especially true for the WIR and WIW problems, where both methods achieved an almost equal performance.

heading: 5.3 EXPRESSION COMPLEXITY ANALYSIS
text: Besides the test performance, another perspective worth considering is their complexity, i.e., the sizes of the obtained expressions. Table 5 shows the median of expression sizes for all synthetic test functions. First, it can be noticed that the applied simplification and pruning methods were effective in reducing the complexity of the expressions. On average, a reduction of 40% was achieved across all the experiments after both simplification methods were applied. Although for some functions, like Korns 12, the method simplifies the expression to only a single node, this result is not indicative of simplification only. The reason is that GP was, in this case, actually unable to fit this function well, and the expression it obtained does not perform better than only a single constant node that is obtained after simplification.
The second important observation is that the expressions that are evolved when initializing the population with winning trees are, in most cases, significantly smaller than when using random initialization. On average, when considering all the experiments, initialization with winning trees reduces the size of the evolved expressions by around 50%. This demonstrates that a good initialization leads to a smaller occurrence of bloat. Still, it should be noted that it does not eliminate bloat completely since the obtained solutions could be simplified further.
Table 6 shows the summary of the obtained expression sizes for real-world problems after the execution of the simplification and pruning methods. The expressions obtained using the winning trees for initialization did not always lead to smaller expressions for these problems. This happens for the WIW and WIR datasets, in which the expressions obtained with the initialization by winning trees were larger than those obtained with random initialization. A probable cause for this is that the algorithm quickly converged to a good region of solutions and simply started to bloat and overfit on the training set. On the WIW dataset, we observe some spikes on the test set for two experiments (random initialization with the tree depth of 6 and subtree initialization with the three depth of 8). At this point, it seems that the method started to overfit, but nevertheless, in the next iterations, solutions that performed well on the test set were evolved. For CST, the expressions are of similar size, whereas initialization with winning trees resulted in smaller expressions being evolved for the other two problems. In those cases, the algorithm converged more slowly, and as such, it seems that they did not have the chance to overfit the training set.

heading: 6 CONCLUSIONS AND FUTURE WORK
text: This paper analyses the influence of simplification in GP for regression problems. First, we investigate how various simplification procedures can result in smaller, yet fit solutions. Afterward, we use the parts of the obtained solutions (denoted as winning trees) to seed the population for new runs. Our results indicate that winning trees can help reach better solutions in a smaller number of evaluations. This approach works especially well for cases where solutions have larger depth as then, winning trees have sufficient “space” to be properly adapted, and where the tree depth size makes it more challenging for the GP process to evolve highly fit solutions.
As this paper proposes a new concept – winning trees, there are multiple possible future research directions. It is possible to look at winning trees as a building block specialization with constraints on size and fitness. Still, one could question our design choices in several places. For instance, why considering the problems we consider, why not tune more or the GP’s parameters, why go for subtrees (winning trees) of depth half the maximum tree depth. Furthermore, the insertion and application of subtrees in the new population can also be performed to provide more influence to the evolutionary process. We consider the investigation of those alternatives a natural next step.

heading: A ADDITIONAL RESULTS
text: The mapping rules for simplification in our experiments are given in Table 7, defined using the prefix notation. The left side of each line denotes the original pattern that the Compare-Match algorithm searches for in the expression. On the other hand, the right side represents the expression by which the pattern in the original expression will be replaced.
Algorithm 1 Compare-Match procedure Input: P – pattern (left side of the rule), T – expression Output: Boolean: true if the rule has changed, false otherwise.
Function Compare if root(P) = null —— root(T) = null then
return true end if if !(Map(P, T)) then
return false end if for (i := 0; i < degree(P ); i+ +) do
if !Compare(P-¿child[i], T-¿child[i]) then return false
end if end for return true
Function Match if Compare(P, T) then
Replace pattern P in T with the simplified expression return true
end if Boolean matched := false if T != null then
for (i := 0; i < degree(T ); i+ +) do matched := Match(P, T-¿child[i]) —— matched
end for end if return matched
CONVERGENCE
Figure 1 shows the GP convergence results for real-world problems. The plots represent the median of the best individuals from the 50 performed runs. The convergence is shown both on the training
set and on the test set, where in each iteration, the best individual from the training set was selected and evaluated on the test set.
The problems can be roughly grouped into two categories by their behavior. For the first three problems, we observed that some of the methods still did not converge in the given time and were improving the solutions. For the final two problems, namely WIR and WIW, the algorithms converged quite quickly, and for most of the run, the solutions did not improve significantly. The best convergence was achieved on the training set by GP initialized with winning trees and with the maximum tree depth of 10. The convergence also improves when using winning trees for the other tree depths, although not as consistently. On the test set, it is evident that these methods reach good solutions faster than random initialization. This means that inserting existing genetic material into the initial population did not lead to overfitting but rather helped speed up the convergence.
STABILITY AND DIVERSITY OF THE SYNTHETIC SOLUTIONS
Figure 2 shows the boxplot results for the synthetic benchmark datasets. This figure aims to determine the stability and dissipation of the results between the tested methods. For the smallest depth of 6, the initialization with winning trees did not improve the stability of the results. In general, the results obtained by this method were, in several cases, even more dispersed than with random initialization (for example, in cases of the Korns 4 and Keijzer 16 functions). In cases where the results had a small dissipation, they were generally worse than the results obtained by random initialization. For tree depth of 8, the results tend to improve in some cases, but still, the initialization with winging trees does not demonstrate a clear dominance over the GP results obtained by random initialization. However, the situation largely improves with the tree depth of 10. In this case, the initialization with winning trees leads to significantly less dispersed results than all the other experiments. This is especially evident in the Nguyen type functions, in which the dispersion is almost negligible compared to the other experiments. This suggests that for the depths of 6 and 8, the extracted winning trees were too small to provide useful information that could more efficiently guide GP towards better solutions.
To evaluate the diversity of solutions, we can compare the obtained solutions semantically (i.e., if the resulting trees “look” the same) and functionally (if the trees give the same fitness value as output). For ten synthetic benchmarks, for 21 out of 30 cases, initialization with winning tress gives less semantically diverse solutions. Additionally, for 21 out of 30 cases, initialization with winning trees gives less functionally diverse solutions.
STABILITY AND DIVERSITY OF THE REAL-WORLD SOLUTIONS
Figure 3 shows the boxplot results for the real-world problems. These plots suggest that for these problems, the initialization with winning trees again provides several benefits. However, this again becomes evident only for the two larger tree sizes, as for the tree depth of 6 initialization with winning trees did not always perform better. The initialization with winning trees resulted in less dispersed and more stable results for the other two tree depths, confirming the results obtained for the synthetic benchmarks.
Finally, for 4 out of 15 cases, initialization with winning tress gives less semantically diverse solutions. For 6 out of 15 cases, initialization with winning trees gives less functionally diverse solutions.

Review summaries:
Inspired by (Frankle & Carbin, 2019), the paper proposes to find winning trees from a set of GP solutions as initialisation for another GP procedure. Winning tress are random sub-trees from GP solutions after simplification and a novel pruning strategy. Results show that such procedure can lead to better regression performance when the expression depth is larger or equal to 8. However, results also suggest that the discovered winning trees are specialised to specific tasks (i.e. fail to transfer) and cannot in general produce smaller trees.

On a technical level, the paper proposes two methods for Genetic Programming (GP) tree pruning, as well as a method for a population _restart_ that relies on both pruning methods. The aim of such approach is that in the second, or subsequent, GP runs, the GP algorithm starts from with an already-somewhat-good initial population of individuals that would allow GP to reach better solutions. On a scientific level, authors try to draw analogies between their approach, and recent advances in the deep learning (DL) community, regarding the Lottery Ticket Hypothesis (LTH). The authors complement their draft with a set of experimental evaluations on different standard datasets.

This paper discusses the influence of simplification and pruning in GP for regression problems. A novel pruning method is presented, and a new concept termed as winning trees is proposed. Experiments are conducted based on ten one or two-dimensional synthetic symbolic regression problems and five real-world regression problems. Comparative results show that winning trees can help GP find better solutions in a smaller number of evaluations.