# Runtime phylogenetic analysis enables extreme subsampling for test-based
problems

Alexander Lalejini  Grand Valley State University<EMAIL_ADDRESS>,  Marcos
Sanson  Grand Valley State University<EMAIL_ADDRESS>,  Jack Garbus
Brandeis University<EMAIL_ADDRESS>,  Matthew Andres Moreno  University
of Michigan<EMAIL_ADDRESS>and  Emily Dolson  Michigan State University
<EMAIL_ADDRESS>
###### Abstract.

A phylogeny describes the evolutionary history of an evolving population.
Evolutionary search algorithms can perfectly track the ancestry of candidate
solutions, illuminating a population’s trajectory through the search space.
However, phylogenetic analyses are typically limited to post-hoc studies of
search performance. We introduce phylogeny-informed subsampling, a new class
of subsampling methods that exploit runtime phylogenetic analyses for solving
test-based problems. Specifically, we assess two phylogeny-informed
subsampling methods—individualized random subsampling and ancestor-based
subsampling—on three diagnostic problems and ten genetic programming (GP)
problems from program synthesis benchmark suites. Overall, we found that
phylogeny-informed subsampling methods enable problem-solving success at
extreme subsampling levels where other subsampling methods fail. For example,
phylogeny-informed subsampling methods more reliably solved program synthesis
problems when evaluating just one training case per-individual, per-
generation. However, at moderate subsampling levels, phylogeny-informed
subsampling generally performed no better than random subsampling on GP
problems. Our diagnostic experiments show that phylogeny-informed subsampling
improves diversity maintenance relative to random subsampling, but its effects
on a selection scheme’s capacity to rapidly exploit fitness gradients varied
by selection scheme. Continued refinements of phylogeny-informed subsampling
techniques offer a promising new direction for scaling up evolutionary systems
to handle problems with many expensive-to-evaluate fitness criteria.

genetic programming, subsampling, selection schemes, lexicase selection,
phylogenetic analysis, test-based problems

††ccs: Software and its engineering Search-based software engineering††ccs:
Computing methodologies Randomized search

##  1\. Introduction

A phylogeny (ancestry tree) describes the evolutionary history of an evolving
population by representing the evolutionary relationships among taxa (e.g.,
individuals, genotypes, genes, species, etc.). Evolutionary biologists
typically estimate phylogenies from the fossil record, phenotypic traits, and
extant genetic information. Phylogenetic analyses using such imperfect
phylogenies have profoundly advanced our understanding of life on Earth (Raup,
1992; Wiley and Lieberman, 2011; Rothan and Byrareddy, 2020; Tucker et al.,
2017). Evolutionary search algorithms, in contrast, can track the ancestry of
candidate solutions with perfect (or user adjustable) accuracy (Ofria et al.,
2020; Moreno et al., 2022; De Rainville et al., 2012; Bohm et al., 2017;
Godin-Dubois et al., 2019; Dolson et al., 2023). Indeed, post-hoc phylogenetic
analyses have yielded valuable insights for evolutionary computing research
(McPhee et al., 2016; Hernandez et al., 2022a; Shahbandegan et al., 2022;
Dolson et al., 2020; McPhee and Hopper, 1999; Donatucci et al., 2014; Burlacu
et al., 2023; McPhee et al., 2017), but phylogenetic analyses remain largely
unexplored for assisting evolutionary search at runtime. In this work, we
introduce phylogeny-informed subsampling methods that exploit phylogenetic
analyses for solving test-based problems.

In evolutionary computing, many problems require evaluating candidate
solutions on many fitness criteria to accurately assess solution quality. This
scenario is especially common in genetic programming (GP) where, each
generation, a population of evolving programs is typically evaluated on a
corpus of input-output examples (i.e., training cases) that specify expected
program behavior. Using the results of these training case evaluations, a
selection algorithm chooses promising programs to “reproduce” into the next
generation. Ideally, we would thoroughly evaluate each candidate solution’s
quality with a large number of training cases. However, thoroughly assessing
candidate solution quality can be an inefficient use of computational
resources, especially if training cases (or fitness criteria) are
computationally expensive to evaluate or assess redundant behavior (Boldi et
al., 2023a). Finite computing resources force GP systems to balance evaluation
thoroughness with other aspects of evolutionary search, such as population
size or generation count, which are also important for problem-solving success
(Hernandez et al., 2019; Ferguson et al., 2020; Helmuth and Spector, 2022;
Helmuth and Abdelhady, 2020; Briesch et al., 2023).

Evaluation thoroughness is often traded for computational savings on test-
based problems by assessing each candidate solution on a small subsample of
training cases each generation (Jin, 2005, 2011; Curry and Heywood, 2004;
Gathercole and Ross, 1994). Indeed, random subsampling has been shown to
dramatically improve problem-solving success in GP by reallocating
computational savings to run search for more generations or to increase
population size (Ferguson et al., 2020; Helmuth and Spector, 2022; Geiger et
al., 2023). Current subsampling methods, however, sometimes omit important
evaluation criteria, potentially causing the loss of genetic diversity and
negatively affecting problem-solving success (Hernandez et al., 2022b; Boldi
et al., 2023b; Ferguson et al., 2020). Moderating subsample rates or using
many redundant training cases can mitigate this drawback. Unfortunately, even
the occasional loss of critical diversity from a population can slow or
prevent problem-solving success on certain problems. This risk is particularly
pronounced on problems that require substantial search space exploration or
those where an expected behavior is represented by only a small proportion of
training cases (making them more likely to be left out in a random subsample)
(Lozano et al., 2008). Some subsampling techniques (e.g., informed down-
sampling (Boldi et al., 2023a)) mitigate these issues by using population
statistics at runtime to try to build subsamples that better represent the
full training set.

As phylogenies are a rich source of information about the process of
evolution, we hypothesize that we can build on the success of techniques like
informed down-sampling (Boldi et al., 2023a) by using phylogenetic
information. We propose a new category of phylogeny-informed subsampling
procedures for test-based problems. These methods operate on the assumption
that the population’s ancestry information is tracked during evolution. In
addition to tracking ancestral relationships, the phylogeny is annotated with
any training case results evaluated during a run. Ancestral performance data
can then be used to (1) estimate a candidate solution’s performance on
unevaluated training cases and (2) choose which training cases should be
included in a subsample. Previous work demonstrated that phylogeny-based
estimations used in combination with random down-sampling can improve
diversity maintenance and overall problem-solving success at extreme
subsampling rates (Lalejini et al., ress). Here, we extend the use of
phylogenetic analysis to choose individualized subsamples when evaluating
candidate solutions.

We introduce two phylogeny-informed subsampling routines in the context of
lexicase parent selection: individualized random subsampling (IRS) and
ancestor-based subsampling (ABS). Each generation, IRS constructs a random
subsample of training cases for each candidate solution to be evaluated on and
uses phylogenetic information to estimate the solution’s performance on all
other cases. Like IRS, ABS constructs a subsample of training cases for each
candidate solution. However, instead of selecting cases randomly, ABS chooses
the training cases on which the candidate solution’s ancestors were least
recently evaluated, minimizing the phylogenetic distance from which
estimations are drawn. We compared IRS, ABS, down-sampling with phylogeny-
based fitness estimation (Lalejini et al., ress), and down-sampling with no
estimation on thirteen problems across two problem domains: three selection
scheme diagnostic problems (Hernandez et al., 2022c) and ten program synthesis
benchmark problems (Helmuth and Spector, 2015; Helmuth and Kelly, 2021).

##  2\. Assisting evolutionary search with phylogenetic analysis

Many parent selection algorithms require that each candidate solution be
evaluated on a comparable set of training cases each generation in order to
assess their relative performance. Conventional subsampling methods
accommodate this constraint by constructing a single sample to evaluate all
individuals against. For example, random down-sampling chooses a subsample of
training cases at random each generation. Phylogeny-informed subsampling
methods allow for individualized subsampling; that is, each candidate solution
can be evaluated on a unique sample of training cases while remaining
comparable to other members of the population. Phylogeny-informed subsampling
maintains comparability among candidate solutions by estimating candidate
solution performance on any unevaluated training cases via phylogeny-based
fitness estimation (Lalejini et al., ress). Thus, any parent selection
algorithm can be applied as if all candidates were evaluated against all
training cases.

###  2.1. Phylogeny-informed fitness estimation

Lalejini et al. (ress) recently proposed two phylogeny-informed fitness
estimation methods: ancestor-based estimation and relative-based estimation.
In our experiments, we use ancestor-based estimation, as it is computationally
cheaper and neither estimation method was found to be consistently better than
the other. To estimate an individual’s performance on a training case,
ancestor-based estimation iterates over the individual’s direct ancestors
until finding the nearest ancestor that was evaluated against the focal
training case. This ancestor’s score then serves as the estimate for the focal
individual’s performance on that training case.

Phylogeny-informed fitness estimation requires the overhead of ancestry
tracking. In our experiments, we use the same tracking approach as in
(Lalejini et al., ress), which discusses the computational costs in detail.
Phylogenies can be tracked at any taxonomic level of organization (e.g.,
individuals, genotypes, etc.), and a node in a phylogenetic tree is
generically referred to as a “taxon” (pluralized as “taxa”). In our work, taxa
represented genotypes. We limited the computational cost of estimation by
constraining search distance in the phylogeny to eight steps, and we assumed
maximally poor performance for any failed estimates (as in (Lalejini et al.,
ress)).

Ancestor-based estimation can be optimized to forgo full phylogeny tracking by
passing evaluation information from parent to offspring. This optimization is
similar to many fitness inheritance methods where a proportion of offspring
inherit the mean fitness of their parents (Bui et al., 2005; Chen et al.,
2002; Fonseca et al., 2012; Ducheyne et al., 2008; Wang and Ting, 2018; Shi
and Rasheed, 2008). Pilato et al. (2007, 2010)’s ancestor-based fitness
inheritance method works similarly to our estimation approach, but uses
multiple genetically similar ancestors to compute an estimate. Phylogeny-
informed fitness estimation extends existing fitness inheritance methods by
conducting independent estimates for each training case, supporting the use of
collateral relatives for estimates, and by allowing additional phylogenetic
information to be incorporated into the estimate if so desired. Like fitness
inheritance methods, phylogeny-informed estimation assumes that offspring
behavior will (on average) be strongly correlated with their parents.

Lalejini et al. (ress) applied phylogeny-informed estimation in combination
with random down-sampling and cohort partitioning (each using lexicase
selection). Lalejini et al. (ress) found that estimation could improve
diversity maintenance and search space exploration but did not observe
consistent benefits for problem-solving success across four GP problems.
Phylogeny-informed subsampling builds on these fitness estimation methods by
customizing subsample construction for each member of the population.

###  2.2. Phylogeny-informed subsampling

In this work, we introduce two simple phylogeny-informed subsampling methods:
individualized random subsampling and ancestor-based subsampling.

####  2.2.1. Individualized random sampling (IRS)

IRS constructs a random subsample of training cases for each member of the
population. Candidate solutions are then assessed on their assigned random
sample. IRS is a straightforward extension of random down-sampling, but has
the benefit of using a greater diversity of training cases when assessing a
population each generation. While phylogenetic analysis is not used to
construct subsamples, phylogenetic information enables IRS by ensuring that
all members of the population are comparable by the selection algorithm.

####  2.2.2. Ancestor-based subsampling (ABS)

Ancestor-based subsampling (ABS) constructs a subsample based on which
training cases a candidate solution’s recent ancestors were evaluated against.
When building a subsample of size $S$, all training cases are initially
eligible for inclusion. We then iterate over the candidate solution’s taxon
and its direct ancestors in sequence. At each step, we mark all training cases
that the current taxon has already been evaluated against as ineligible. This
process continues until the number of eligible training cases is less than or
equal to $S$. At that point, all remaining eligible training cases are added
to the subsample. To fill out the subsample, random training cases from the
set most recently marked ineligible are added until it contains $S$ training
cases. In this way, ABS prioritizes evaluating candidate solutions on training
cases least recently evaluated in that candidate’s ancestry.

##  3\. Methods

We assessed phylogeny-informed subsampling methods in the context of the
lexicase parent selection algorithm on thirteen problems across two problem
domains: three selection scheme diagnostic problems (Hernandez et al., 2022c)
and ten GP problems selected from the first and second program synthesis
benchmark suites (Helmuth and Spector, 2015; Helmuth and Kelly, 2021). We
repeated all experiments at two subsampling rates: 1% and 10%.

###  3.1. Lexicase Selection

Lexicase selection is designed for use on test-based problems where candidate
solutions are evaluated on a set of training cases that specify correct
behavior (Spector, 2012). Lexicase selection has been successful across many
domains (Aenugu and Spector, 2019; Moore and Stanton, 2017; Lalejini et al.,
2022; Ding and Spector, 2022; Matsumoto et al., 2023; Boldi et al., 2023c; La
Cava et al., 2016; Metevier et al., 2019; Stanton and Moore, 2022), including
(and especially) genetic programming (Helmuth and Abdelhady, 2020; Orzechowski
et al., 2018). To select a parent, lexicase selection first shuffles all
training cases and adds all members of the population to a pool of candidates
eligible for selection. Each training cases is then used in sequence (in
shuffled order) to remove all but the elite candidates (on the current
training case) from the pool of selectable candidates. This process continues
until all training cases have been used. If more than one candidate remains in
the pool, one is selected at random.

####  3.1.1. Down-sampled lexicase selection

Each generation, down-sampled lexicase randomly subsamples the training set
used to evaluate and select parents (Hernandez et al., 2019). When augmented
with phylogeny-informed estimation, the full training set can be used for
parent selection, and the population’s phylogeny is used to estimate any
performances on training cases a candidate solution was not evaluated against.

####  3.1.2. Applying phylogeny-informed subsampling to lexicase selection

Individualized random subsampling and ancestor-based subsampling choose the
training cases used to evaluate candidate solutions on an individual basis.
Once all members of the population are evaluated on their subsample of
training cases, the complete training set is used for lexicase selection, and
the population’s phylogeny is used to estimate performances on any training
cases a candidate solution was not evaluated against.

###  3.2. Diagnostic experiments

We used the exploitation rate, contradictory objectives, and multi-path
exploration diagnostics from the DOSSIER suite to compare four subsampling
regimes: individualized random sampling, ancestor-based sampling, random down-
sampling with fitness estimation, and random down-sampling without fitness
estimation. The DOSSIER suite is a set of diagnostic benchmarks that measure
important problem-solving characteristics for evolutionary search (Hernandez
et al., 2022c). These diagnostics have been used to study the problem-solving
and phylogenetic characteristics of lexicase selection (among many other
selection methods) (Hernandez et al., 2022b, a; Shahbandegan et al., 2022),
making them an ideal domain to assess the impacts of phylogeny-informed
subsampling. We parameterize our experiments similarly to those from
(Hernandez et al., 2022c).

Each diagnostic represents genomes as a vector of 100 “genes”. Genes are
floating point values, each between 0.0 and 100.0. Each diagnostic specifies a
particular genotype-to-phenotype translation that interprets a genome as an
equal-length phenotype vector of numeric “traits”. Lexicase selection uses
each trait as a training case, so each of our diagnostic experiments use
training sets of size 100. For all diagnostics used in this work, higher trait
scores are better. We apply subsampling to diagnostic problems in the same way
as in (Hernandez et al., 2022b).

For each diagnostic experiment, we ran 20 replicates of each condition. We
evolved populations of size 500 for 50,000 generations. Each generation, we
evaluated members of the population according to the condition-specific
subsampling regime, and we selected parents to reproduce asexually. We mutated
offspring at a per-gene rate of 0.7%, drawing mutations from a Gaussian
distribution with a mean of 0.0 and standard deviation of 1.0 (Hernandez et
al., 2022c).

Note that generations are held constant across diagnostic experiments
regardless of subsampling level, as we limit comparisons to subsampling
methods (and not across sampling levels). We provide a description of relevant
diagnostics below but direct readers to (Hernandez et al., 2022c) for more
detailed descriptions.

####  3.2.1. Exploitation rate diagnostic

The exploitation rate diagnostic measures a selection scheme’s ability to
exploit a search space with single, smooth fitness gradient (i.e., hill
climbing) (Hernandez et al., 2022c). This diagnostic directly translates a
genome into the phenotype, interpreting each gene value as the corresponding
trait value. All traits are maximized at the upper bound of 100. This creates
a search space with a single global optimum comprising a genome where all
gene-values are maximized. For this diagnostic, we report the best aggregate
trait score in the population, as greater aggregate trait scores indicate more
successful search space exploitation.

####  3.2.2. Contradictory objectives diagnostic

The contradictory objectives diagnostic measures a selection scheme’s ability
to find and maintain many independent global optima in a population (Hernandez
et al., 2022c). To translate a genome into a phenotype, this diagnostic marks
the maximum gene as active and all others as inactive. The active gene value
is copied into the corresponding phenotypic trait, and all traits associated
with inactive genes are set to zero. Thus, a candidate solution’s fitness is
limited to a single trait value, creating 100 independent global optima in
this search space (each associated with a different trait). All traits are
maximized at the upper bound of 100, and for our analyses, we consider any
trait with a value above 98 as “satisfied”. On this diagnostic, we report
“satisfactory trait coverage”, which counts the number of distinct traits
satisfied across the entire population. Satisfactory trait coverage quantifies
the number of unique global optima maintained in a population.

####  3.2.3. Multi-path exploration diagnostic

The multi-path exploration diagnostic measures a selection scheme’s capacity
to continuously explore different fitness gradients in a search space
(Hernandez et al., 2022c). To translate a genome, this diagnostic first marks
the maximum gene in the genome as the activation gene. Each consecutive gene
after the activation gene that is less than or equal to the previous gene is
marked as active, creating an active gene region. All genes in the active gene
region are copied into their corresponding phenotypic traits, and all traits
associated with genes outside of the active region are set to zero. Traits are
maximized at the upper bound of 100, and the phenotype with all maximized
traits is the global optimum.

The multi-path exploration diagnostic defines a search space with many
pathways that each begin at a different activation gene. Each pathway in the
search space has a different path length and peak fitness, but all paths have
identical slopes. The pathway beginning at the first gene position leads to
the global optimum, and all others lead to local optima. To be consistently
successful on this diagnostic, a selection scheme must be capable of
continuously exploring different pathways to reach the global optima. For this
diagnostic, we report the best aggregate trait score in the population because
greater scores indicate that a population was able to find and optimize better
pathways in the search space.

###  3.3. Genetic programming experiments

We compared the problem-solving success of individualized random sampling,
ancestor-based sampling, and random down-sampling with and without estimation
on ten problems from the first and second general program synthesis benchmark
suites (Helmuth and Kelly, 2021; Helmuth and Spector, 2015): Bouncing Balls,
Dice Game, Fizz Buzz, For Loop Index, GCD, Grade, Median, Small or Large,
Smallest, and Snow Day.

####  3.3.1. GP system

For all GP experiments, we ran 50 replicates of each condition. In each
replicate, we evolved a population of 1,000 linear genetic programs using the
SignalGP representation (Lalejini and Ofria, 2018). We configured these
experiments similarly to those in (Lalejini et al., ress). Our supplemental
material (see (Lalejini et al., 2024)) contains the full instruction sets used
and configuration details used for each problem (including source code). We
reproduced programs asexually, applying mutations to offspring. We applied
single-instruction insertions, deletions, and substitutions, each at a per-
instruction rate of 0.1%. We applied single-argument substitutions at a per-
argument rate of 0.1%, and we applied slip mutations (Lalejini et al., 2017),
which can duplicate or delete whole sequences of instructions, at a per-
program rate of 5%. For all problems, we limited program length to a maximum
of 128 instructions, and programs were given 128 time steps (i.e.,
instruction-execution steps) to return their output.

####  3.3.2. Program synthesis problems

The program synthesis benchmark suites include a large number of introductory
to programming problems that are well studied (Helmuth and Spector, 2015;
Helmuth and Kelly, 2021). The problems used in this work range in difficulty
from easy (e.g., Smallest) to challenging (e.g., Bouncing Balls) (Helmuth and
Kelly, 2022). Brief descriptions of each problem are given below:

  * •

Bouncing Balls (Helmuth and Kelly, 2021): Programs are given three inputs: a
starting height (float in [1.0, 100.0]), a height after the first bounce of a
dropped ball (float in [1.0 and 100.0]), and a number of bounces (integer in
[1 and 20]). A program must compute the bounciness index using the first two
inputs, and then output the total distance that the dropped ball travels
across all of its bounces.

  * •

Dice Game (Helmuth and Kelly, 2021): Programs receive two integers, $n$ and
$m$, in range [1, 1000]. Each integer corresponds to the number of sides on a
die, and programs must output the probability that an $n$-sided die rolls
strictly higher than an $m$-sided die.

  * •

Fizz Buzz (Helmuth and Kelly, 2021): Given an integer $x$, a program must
output “Fizz” if $x$ is divisible by 3, “Buzz” if $x$ is divisible by 5,
“FizzBuzz” if $x$ is divisible by both 3 and 5, and $x$ if none of those
conditions are true.

  * •

For Loop Index (Helmuth and Spector, 2015): Programs receive three integer
inputs: start (in range [-500, 500]), end (in range [-500, 500]), and step (in
range [1, 10]). Beginning with start, programs output each subsequent value
step away from the previous value until end.

  * •

GCD (Helmuth and Kelly, 2021): Programs are given two integers (in range [1,
1000000]) and must output the largest integer that evenly divides into each.

  * •

Grade (Helmuth and Spector, 2015): Programs receive five integer inputs in
range [0, 100]: $A$, $B$, $C$, $D$, and score. $A$, $B$, $C$, and $D$ are
monotonically decreasing and unique “grade” thresholds that describe the
minimum score to receive that grade. A program must return the appropriate
letter grade for the given score or return $F$ if $\text{{score}}<D$.

  * •

Median (Helmuth and Spector, 2015): Programs receive three integer inputs in
range [-100, 100] and must output the median value.

  * •

Small or Large (Helmuth and Spector, 2015): Given an integer $n$, programs
must output “small” if $n<1000$, “large” if $n\geq 2000$, and “neither” if
$1000\geq n<2000$.

  * •

Smallest (Helmuth and Spector, 2015): Programs receive four integer inputs in
range [-100, 100] and must output the smallest value.

  * •

Snow Day (Helmuth and Kelly, 2021): Programs receive four inputs: a number of
hours (integer in [0, 20]), how much snow is on the ground (float in [0.0,
20.0]), the rate of snow fall (float in [0.0, 10.0]), and the proportion of
snow melting per hour (float in [0.0, 1.0]). Programs must output the amount
of snow on the ground after the given number of hours.

For each problem, we used a set of 100 training cases for program evaluation
and a set of 1,000 testing cases for determination of problem-solving success.
All training and testing sets were generated from data provided by the
benchmark suite authors (Helmuth and Spector, 2015; Helmuth and Kelly, 2021).
We provide the training and testing sets used for each problem in our
supplemental material (Lalejini et al., 2024). We categorized a replicate as
successful if it produced a program that solved all testing cases. For all
problems, we ensured that input-output edge cases were included in the
training and testing sets to ensure that testing sets adequately assessed
generalization on their own. We terminated runs after 50,000,000 training case
evaluations, which corresponds to 500 generations of evolution under standard
lexicase selection, 5,000 generations under 10% subsampling, and 50,000
generations under 1% subsampling.

###  3.4. Statistical analyses

For all experiments, we only made comparisons among different subsampling
methods. We did not compare measurements taken from treatments across
different problems or subsampling levels (1% and 10%). When comparing
distributions of measurements taken from different treatments, we performed
Kruskal-Wallis tests to screen for statistical differences among independent
conditions. For comparisons in which the Kruskal-Wallis test was significant
(significance level of 0.05), we performed post-hoc Wilcoxon rank-sum tests to
identify pairwise differences. When comparing problem-solving success rates,
we used pairwise Fisher’s exact tests (significance level of 0.05). We used
the Holm-Bonferroni method to correct for multiple comparisons as appropriate.
Complete results of statistical analyses are available in our supplemental
material (Lalejini et al., 2024).

###  3.5. Software and data availability

Experiment software and data analyses can be found in our supplemental
material, which is hosted on GitHub and archived on Zenodo: (Lalejini et al.,
2024). Our experiment data are archived on the Open Science Framework at
(Lalejini, 2024).

##  4\. Results and discussion

###  4.1. Random down-sampling without fitness estimation most improves
gradient exploitation with lexicase selection

Figure 1.  Aggregate trait score on the exploitation-rate diagnostic for
subsampling regimes with lexicase selection. Panels (a) and (c) show mean
aggregate trait score over time for 1% and 10% subsampling levels,
respectively. Shading around the mean indicates a bootstraped 95% confidence
interval. Panels (b) and (d) show best aggregate trait score after 50,000
generations of evolution for 1% and 10% subsampling levels, respectively.
Dotted black lines in each plot indicate the median aggregate trait score
achieved by standard lexicase selection (no subsampling) after an equivalent
number of trait evaluations. Kruskal-Wallis tests for both subsampling levels
were statistically significant ($p<0.001$).

The exploitation rate diagnostic measures a selection scheme’s ability to
rapidly guide a population up a smooth, unimodal fitness gradient. Figure 1
shows aggregate scores over time and after 50,000 generations of evolution
under both 1% and 10% subsampling rates. The dotted black line on each graph
indicates the median aggregate score achieved by 20 replicates of standard
lexicase selection (with no subsampling) after an equivalent number of trait
evaluations (e.g., 50,000 generations at 1% subsampling is equivalent to 500
generations of standard lexicase). Standard lexicase’s median performance is
provided for reference, but we did not make direct comparisons to it.

At both 1% and 10% subsampling levels, random down-sampling with no estimation
(DS) substantially outperforms all other subsampling regimes (corrected
Wilcoxon rank-sum tests, $p<0.001$). Both phylogeny-informed subsampling
regimes, individualized random sampling (IRS) and ancestor-based subsampling
(ABS), outperformed random down-sampling with fitness estimation (DS+EST) for
both 1% and 10% subsampling levels ($p<0.001$). All subsampling regimes
achieved greater aggregate scores than standard lexicase run for an equivalent
number of trait evaluations.

Previous work benchmarked standard lexicase selection on the exploitation rate
diagnostic (Hernandez et al., 2022c), establishing that lexicase optimizes
populations more slowly than elitist aggregative selection methods that do not
actively maintain diverse specialists. For example, tournament selection and
truncation selection performed substantially better than lexicase selection on
this diagnostic (Hernandez et al., 2022c). Lexicase selection, however,
exploited faster than other selection methods with mechanisms for diversity
maintenance (e.g., fitness sharing and non-dominated sorting) because lexicase
is elitist for individual traits appearing early in the ‘shuffled’ order of
training cases used for selecting a parent.

To our knowledge, this is the first assessment of down-sampled lexicase on the
exploitation rate diagnostic. Our results show that random down-sampling (with
no estimation) can substantially improve lexicase selection’s ability to
exploit smooth gradients. We attribute this improvement to down-sampled
lexicase’s use of fewer training cases (traits) when selecting a parent, which
concentrates selection on candidate solutions that are elite on those cases.
In search spaces where substantial exploration is required, selecting a large
number of different parents can be beneficial. However, the exploitation-rate
diagnostic requires no off-gradient exploration. Concentrating selection to
fewer individuals results in more focused mutations, increasing the
probability of any single parent producing an offspring with beneficial
mutations. Indeed, we found that standard lexicase selected, on average, close
to 50% of the population as parents (approximately 216, (Lalejini et al.,
2024)). Down-sampled lexicase (with no estimation) selected many fewer parents
on average: approximately 120 and 28 for 1% and 10% subsampling levels,
respectively. All treatments with phylogeny-informed fitness estimation
selected approximately the same number of distinct parents as standard
lexicase selection, providing some explanation for their under-performance on
this diagnostic. That is, the diversity maintenance recovered by phylogeny-
informed subsampling impeded exploitation rate.

Preliminary evidence also suggests that lexicase selection is not robust to
misleading performance information (Dolson et al., 2018). As such, we also
expect that inaccurate phylogeny-based fitness estimates could be contributing
to slower exploitation rates.

####  4.1.1. Phylogeny-informed subsampling improves tournament selection’s
gradient exploitation rate

Figure 2.  Aggregate trait score on the exploitation-rate diagnostic for
subsampling regimes with tournament selection. Panels (a) and (c) show mean
aggregate trait score over time for 1% and 10% subsampling levels,
respectively. Shading around the mean indicates a 95% confidence interval.
Panels (b) and (d) show best aggregate trait score after 50,000 generations of
evolution for 1% and 10% subsampling levels, respectively. Dotted black lines
in each plot indicate the median aggregate trait score achieved by standard
tournament selection (no subsampling) after an equivalent number of trait
evaluations. Kruskal-Wallis tests for both subsampling levels were
statistically significant ($p<0.001$).

Previous work has shown that tournament selection with a sufficiently large
tournament size is one of the best selection methods when pure exploitation is
most important (Hernandez et al., 2022c). We wanted to assess the effect of
phylogeny-informed subsampling in the context of a more exploitative selection
scheme than lexicase, so we repeated our exploitation rate experiment using
tournament selection (with a tournament size of 8). Figure 2 shows aggregate
scores over time and after 50,000 generations of evolution under both 1% and
10% subsampling rates.

In contrast to our lexicase selection experiments, phylogeny-informed
subsampling methods (IRS and ABS) outperformed all other subsampling regimes
when combined with tournament selection (corrected Wilcoxon rank-sum tests,
$p<0.001$). At 1% subsampling, all subsampling regimes except DS+EST achieved
near-optimal scores for this diagnostic (Fig. 2b). The DS+EST regime performed
approximately the same as tournament selection without subsampling (for an
equivalent number of evaluations). At 10% subsampling, all subsampling regimes
achieved near-optimal scores that were above the median score achieved in our
standard tournament selection reference (Fig. 2d). However, at both
subsampling levels, Figures 2a and 2b reveal that IRS and ABS optimized
populations at much faster rates than all other subsampling regimes.

Taken together with our lexicase selection results, our data show that choice
of selection method determines which subsampling regimes perform best. For
both selection methods, DS+EST performed worst. DS and DS+EST regimes evaluate
all individuals in the population on the same training cases each generation.
When evaluating a population, IRS and ABS construct samples per-individual,
likely resulting in the use of many more distinct training cases in a single
generation than DS or DS+EST, which construct a single sample to use for the
entire population. As such, we hypothesize that fitness estimations may be
less useful (or less accurate) under DS+EST versus the IRS or ABS subsampling
regimes.

###  4.2. Phylogeny-informed subsampling improves diversity maintenance and
search space exploration

Figure 3.  Satisfactory trait coverage on the contradictory objectives
diagnostic. Dotted black lines in both plots indicate the median aggregate
trait score achieved by standard lexicase selection (no subsampling) after an
equivalent number of trait evaluations. Kruskal-Wallis tests for both
subsampling levels were statistically significant ($p<0.001$).

The contradictory objectives and multi-path exploration diagnostics both
measure a selection method’s ability to maintain diversity in a population.
The contradictory objectives diagnostic isolates a selection scheme’s ability
to maintain many global optima in a population. Consistent success on the
multi-path exploration diagnostic requires that a selection scheme be capable
of exploring many fitness gradients in the search space.

On the contradictory objectives diagnostic (Figure 3), no subsampling regime
(at any subsampling level) matched or exceeded the trait coverage maintained
by our standard lexicase reference. Random down-sampling with no fitness
estimation achieved the worst satisfactory trait coverage (corrected Wilcoxon
rank-sum test, $p<0.001$), maintaining just one optimal trait in all
replicates for both 1% and 10% subsampling levels. Phylogeny-informed
subsampling regimes, IRS and ABS, achieved the greatest satisfactory trait
coverage at all subsampling levels relative to other subsampling regimes
($p<0.001$). DS+EST averaged between 3 and 4 satisfactory traits at 1%
subsampling and between 18 and 19 at 10% subsampling. Both IRS and ABS
averaged between 8 and 9 and between 24 and 25 satisfactory traits at 1% and
10% subsampling, respectively.

Figure 4.  Aggregate trait score on the multi-path exploration diagnostic.
Dotted black lines in both plots indicate the median aggregate trait score
achieved by standard lexicase selection (no subsampling) after an equivalent
number of trait evaluations. Kruskal-Wallis tests for both subsampling levels
were statistically significant ($p<0.001$).

On the multi-path exploration diagnostic at 1% subsampling (Figure 4a),
phylogeny-informed subsampling regimes (IRS and ABS) achieved the greatest
aggregate trait scores (corrected Wilcoxon rank-sum test, $p<0.001$), and we
were unable to detect a significant difference between the IRS and ABS
regimes. The DS+EST regime achieved the worst aggregate score at 1%
subsampling ($p<0.003$). All 1% subsampling regimes achieved greater scores
than standard lexicase run for an equivalent number of evaluations.

At 10% subsampling (Figure 4b), random down-sampling without estimation (DS)
achieved the worst performance of all subsampling regimes on the multi-path
exploration diagnostic ($p<0.001$). The DS+EST, IRS, ABS regimes each scored
higher than our standard lexicase reference at an equivalent number of trait
evaluations. We were unable to detect a significant difference among the
DS+EST, IRS, and ABS regimes at 10% subsampling.

Our data from the contradictory objectives diagnostic are consistent with
findings in a previous study, showing that phylogeny-based fitness estimation
can improve diversity maintenance over random down-sampling with no estimation
(Lalejini et al., ress). Indeed, naive random down-sampling can prevent
lexicase selection from maintaining diverse populations (Hernandez et al.,
2022b; Geiger et al., 2023). No subsampling regime fully recovered lexicase’s
capacity for diversity maintenance when using all training cases (traits) for
parent selection. However, our phylogeny-informed subsampling regimes did
improve contradictory objective maintenance over down-sampling with fitness
estimation.

Our data from the exploration diagnostic are consistent with previous work
showing that phylogeny-based fitness estimation can improve diagnostic
performance at sufficiently high subsampling levels but decrease performance
at 1% subsampling (Lalejini et al., ress). Data from the exploitation rate
diagnostic offer an explanation for these results. At 1% subsampling levels,
DS+EST lexicase regimes fail to rapidly exploit fitness gradients (Figure 1a).
In order to explore many pathways in the multi-path exploration diagnostic,
the population must be able to efficiently exploit each pathways fitness
gradient. Overall, phylogeny-informed subsampling regimes more consistently
improved search space exploration as compared to using random down-sampling
(with or without estimation).

###  4.3. Phylogeny-informed subsampling enables extreme subsampling on test-
based problems

Table 1.  Problem-solving success on 10 program synthesis problems at 1% and
10% subsampling levels. The greatest success rate for each problem at each
subsampling level is bolded. Success rates that were significantly greater
than the success rates of all other regimes at that subsampling level are
underlined (Holm-Bonferroni-corrected pairwise Fisher’s exact tests,
$p<0.05$).

Table 1 shows problem-solving success on ten program synthesis problems from
the general program synthesis benchmark suites (Helmuth and Spector, 2015;
Helmuth and Kelly, 2021). We consider a run to be successful if it produces a
program capable of passing all test cases in the testing set. For each
problem, we compared the problem-solving success of each subsampling regime
within a particular subsampling level. We do not include a standard lexicase
reference, but several studies have down that down-sampled lexicase typically
outperforms standard lexicase for these problems (Helmuth and Abdelhady, 2020;
Helmuth and Spector, 2022).

At 1% subsampling, phylogeny-informed subsampling regimes (IRS or ABS)
achieved the greatest success rates on 7 of 10 problems, 5 of which were
significantly better than down-sampling without estimation (corrected pairwise
Fisher’s exact tests, $p<0.05$). We did not detect a significant difference
between IRS and ABS on any problems. IRS and ABS significantly outperformed
DS+EST on one problem (Fizz Buzz), and we were unable to detect differences
between IRS, ABS, and DS+EST for all other problems at 1% subsampling. Down-
sampling with no estimation failed to produce solutions on three problems
(Dice Game, GCD, and Snow Day) at 1% subsampling. In all three of these cases,
all three other subsampling regimes produced at least one solution.

At 10% subsampling, phylogeny-informed subsampling regimes (IRS or ABS)
produced the greatest success rates on 4 of 10 problems; none of these
instances were significantly better than the success rates of all other
regimes (DS and DS+EST). DS produced the greatest success rates on 3 of 10
problems, and DS+EST produced the greatest success rates on 4 of 10 problems.
On the Fizz Buzz problem, DS and DS+EST success rates were significantly
better than both IRS and ABS ($p<0.02$). Only DS and DS+EST failed to produce
solutions on any problems; IRS and ABS runs produced solutions in at least one
replicate for all problems.

No single subsampling regime produced the greatest success rates across all
problems and subsampling levels, which is consistent with other studies
comparing selection methods on large problem sets (Helmuth and Abdelhady,
2020; Orzechowski et al., 2018; Jiang and Yang, 2017). The particulars of the
search space and genetic representation interact with the chosen evaluation
and selection procedures when steering the population through a search space.
At 1% subsampling, however, our data suggest that regimes with some form of
phylogeny-based fitness estimation performed best, and phylogeny-informed
subsampling regimes are generally an improvement over down-sampling with
estimation (Figure 1).

Successes at 1% subsampling levels are impressive considering that each
program in the population is evaluated on a single training case per
generation. At 1% subsampling, random down-sampling with no estimation is
reduced to elitist selection on a random training case. This removes
lexicase’s ability to maintain multiple specialists on different subsets of
the training cases (Ferguson et al., 2020), which is known to be an important
characteristic for lexicase’s success (Helmuth et al., 2019). Indeed, previous
studies have shown that using too few training cases with standard or down-
sampled lexicase reduces problem-solving success (Schweim et al., 2022;
Ferguson et al., 2020). We attribute much of the success of the DS+EST, IRS,
and ABS regimes to their ability to use the full training set for selection,
estimating a program’s performance on any unevaluated training cases using
that program’s ancestry. As such, these regimes can still maintain specialists
by selecting a more diverse set of parents, and indeed, we found that DS+EST,
IRS, and ABS regimes selected a greater diversity of parents than the DS
regime (Lalejini et al., 2024). In supplemental analyses, we also found that
phylogeny-informed subsampling methods generally had greater estimation
accuracy than when estimating under random down-sampling, and estimation
accuracy varied by problem. For example, estimation accuracy was lowest for
the Bouncing Balls and GCD problems, suggesting that mutations are potentially
more likely to have phenotypic effects (making offspring more likely to be
different from their parent) on these problems than on other problems. Our
results also suggest that the search spaces instantiated by the Median and
Smallest problems are trivial to navigate with simple hill climbing, and
indeed, estimation accuracy was generally highest for these two problems.

Our results at 10% subsampling were far more mixed than at 1% subsampling. The
best choice of subsampling regime depended on the particular problem. At 10%
subsampling, each program is evaluated against 10 training cases per
generation. Training sets in program synthesis typically highly redundant;
that is, there are many training cases that assess the same mode of behavior.
If sampling just one training case (1% subsampling), it is impossible to
sample a representative set of training cases for most problems (e.g., those
that require programs to produce qualitatively different outputs for different
inputs). However, with 10 training cases (10% subsampling), it is much more
likely to capture a representative sample of training cases without omitting
cases that assess a particular mode of behavior (Spector, 2012).

While some problems clearly benefited from the use of phylogenetic analysis to
aid evaluation and selection at 10% subsampling (e.g., Bouncing Balls, Snow
Day, and GCD), most other problems did not. This suggests that the forms of
phylogeny-based estimation and phylogeny-informed subsampling are most
appropriate for enabling extreme subsampling, which is often necessary for
domains where evaluation is particularly expensive (e.g., any that require
expensive simulations to evaluate candidate solutions (Moore and Stanton,
2019)).

##  5\. Conclusion

In this work, we demonstrated two simple phylogeny-informed subsampling
methods: individualized random subsampling (IRS) and ancestor-based
subsampling (ABS). Relative to random down-sampling, we found evidence that
phylogeny-based subsampling methods can reduce lexicase selection’s ability to
exploit a smooth fitness gradient (Fig. 1), but improve tournament selection’s
ability to exploit gradients (Fig. 2). We also found that phylogeny-informed
subsampling methods can improve diversity maintenance and overall search space
exploration (Fig. 3 and 4). Across ten program synthesis benchmark problems,
we found that subsampling methods that take advantage of phylogenetic analysis
allow for problem-solving success at extreme subsampling levels where random
down-sampling often fails (Fig. 1). However, at more moderate subsampling
levels, phylogeny-informed subsampling generally performed no better than
random subsampling on program synthesis problems.

Future studies are necessary to further characterize these failure cases for
phylogeny-informed subsampling, which will inform further refinements to these
techniques. For example, inaccurate fitness estimates likely reduce problem-
solving success. One potential source of inaccuracies are scenarios where
offspring have large mutations. Phylogenies could be additionally annotated
with mutation information, and we could take mutational differences into
account when estimating fitnesses and constructing subsamples (e.g., as in
(Pilato et al., 2007)).

Overall, phylogeny-informed methods show promise for helping to scale up
evolutionary computing systems to tackle problems with many fitness criteria
that are each expensive to evaluate. In particular, we recommend phylogeny-
informed methods on problems where evaluating a large population on many
fitness criteria is not computationally feasible, necessitating extreme
subsampling.

###### Acknowledgements.

We thank our respective universities for supporting this work. This research
was supported by Grand Valley State University through a Kindschi Fellowship
to MS. Additionally, this work was supported in part through computational
resources and services provided by the Institute for Cyber-Enabled Research at
Michigan State University.

## References

  * (1)
  * Aenugu and Spector (2019) Sneha Aenugu and Lee Spector. 2019.  Lexicase selection in learning classifier systems. In _Proceedings of the Genetic and Evolutionary Computation Conference on - GECCO ’19_. ACM Press, Prague, Czech Republic, 356–364.  https://doi.org/10.1145/3321707.3321828
  * Bohm et al. (2017) Clifford Bohm, Nitash C. G., and Arend Hintze. 2017.  MABE (Modular Agent Based Evolver): A framework for digital evolution research. In _Proceedings of the 14th European Conference on Artificial Life ECAL 2017_. MIT Press, Lyon, France, 76–83.  https://doi.org/10.7551/ecal_a_016
  * Boldi et al. (2023a) Ryan Boldi, Martin Briesch, Dominik Sobania, Alexander Lalejini, Thomas Helmuth, Franz Rothlauf, Charles Ofria, and Lee Spector. 2023a.  Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving.  http://arxiv.org/abs/2301.01488 arXiv:2301.01488 [cs].
  * Boldi et al. (2023b) Ryan Boldi, Alexander Lalejini, Thomas Helmuth, and Lee Spector. 2023b.  A Static Analysis of Informed Down-Samples. In _Proceedings of the Companion Conference on Genetic and Evolutionary Computation_. ACM, Lisbon Portugal, 531–534.  https://doi.org/10.1145/3583133.3590751
  * Boldi et al. (2023c) Ryan Boldi, Aadam Lokhandwala, Edward Annatone, Yuval Schechter, Alexander Lavrenenko, and Cooper Sigrist. 2023c.  Improving Recommendation System Serendipity Through Lexicase Selection.  http://arxiv.org/abs/2305.11044 arXiv:2305.11044 [cs].
  * Briesch et al. (2023) Martin Briesch, Dominik Sobania, and Franz Rothlauf. 2023.  On the Trade-Off between Population Size and Number of Generations in GP for Program Synthesis. In _Proceedings of the Companion Conference on Genetic and Evolutionary Computation_. ACM, Lisbon Portugal, 535–538.  https://doi.org/10.1145/3583133.3590681
  * Bui et al. (2005) Lam T. Bui, Hussein A. Abbass, and Daryl Essam. 2005.  Fitness inheritance for noisy evolutionary multi-objective optimization. In _Proceedings of the 7th annual conference on Genetic and evolutionary computation_. ACM, Washington DC USA, 779–785.  https://doi.org/10.1145/1068009.1068141
  * Burlacu et al. (2023) Bogdan Burlacu, Kaifeng Yang, and Michael Affenzeller. 2023.  Population diversity and inheritance in genetic programming for symbolic regression.  _Natural Computing_ (Jan. 2023).  https://doi.org/10.1007/s11047-022-09934-x
  * Chen et al. (2002) Jian-Hung Chen, David E. Goldberg, Shinn-Ying Ho, and Kumara Sastry. 2002.  Fitness Inheritance in Multi-Objective Optimization. In _Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation_ _(GECCO’02)_. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 319–326.  event-place: New York City, New York.
  * Curry and Heywood (2004) Robert Curry and Malcolm Heywood. 2004.  Towards Efficient Training on Large Datasets for Genetic Programming.  In _Advances in Artificial Intelligence_ , Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Dough Tygar, Moshe Y. Vardi, Gerhard Weikum, Ahmed Y. Tawfik, and Scott D. Goodwin (Eds.). Vol. 3060. Springer Berlin Heidelberg, Berlin, Heidelberg, 161–174.  https://doi.org/10.1007/978-3-540-24840-8_12
  * De Rainville et al. (2012) François-Michel De Rainville, Félix-Antoine Fortin, Marc-André Gardner, Marc Parizeau, and Christian Gagné. 2012.  DEAP: a python framework for evolutionary algorithms. In _Proceedings of the 14th annual conference companion on Genetic and evolutionary computation_. ACM, Philadelphia Pennsylvania USA, 85–92.  https://doi.org/10.1145/2330784.2330799
  * Ding and Spector (2022) Li Ding and Lee Spector. 2022.  Optimizing Neural Networks with Gradient Lexicase Selection. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=J_2xNmVcY4
  * Dolson et al. (2018) Emily Dolson, Wolfgang Banzhaf, and Charles Ofria. 2018.  Applying Ecological Principles to Genetic Programming.  In _Genetic Programming Theory and Practice XV_ , Wolfgang Banzhaf, Randal S. Olson, William Tozier, and Rick Riolo (Eds.). Springer International Publishing, 73–88.
  * Dolson et al. (2020) Emily Dolson, Alexander Lalejini, Steven Jorgensen, and Charles Ofria. 2020.  Interpreting the Tape of Life: Ancestry-Based Analyses Provide Insights and Intuition about Evolutionary Dynamics.  _Artificial Life_ 26, 1 (April 2020), 58–79.  https://doi.org/10.1162/artl_a_00313
  * Dolson et al. (2023) Emily Dolson, Matthew Andres Moreno, and Santiago Rodriguez Papa. 2023.  Phylotrackpy: a python phylogeny tracker (software).  https://doi.org/10.5281/ZENODO.7922091
  * Donatucci et al. (2014) David Donatucci, M. Kirbie Dramdahl, Nicholas Freitag McPhee, and Morris Morris. 2014.  Analysis of Genetic Programming Ancestry Using a Graph Database.
  * Ducheyne et al. (2008) E.I. Ducheyne, B. De Baets, and R.R. De Wulf. 2008.  Fitness inheritance in multiple objective evolutionary algorithms: A test bench and real-world evaluation.  _Applied Soft Computing_ 8, 1 (Jan. 2008), 337–349.  https://doi.org/10.1016/j.asoc.2007.02.003
  * Ferguson et al. (2020) Austin J. Ferguson, Jose Guadalupe Hernandez, Daniel Junghans, Alexander Lalejini, Emily Dolson, and Charles Ofria. 2020.  Characterizing the Effects of Random Subsampling on Lexicase Selection.  In _Genetic Programming Theory and Practice XVII_ , Wolfgang Banzhaf, Erik Goodman, Leigh Sheneman, Leonardo Trujillo, and Bill Worzel (Eds.). Springer International Publishing, 1–23.  https://doi.org/10.1007/978-3-030-39958-0_1
  * Fonseca et al. (2012) Leonardo G. Fonseca, Afonso C.C. Lemonge, and Helio J.C. Barbosa. 2012.  A study on fitness inheritance for enhanced efficiency in real-coded genetic algorithms. In _2012 IEEE Congress on Evolutionary Computation_. IEEE, Brisbane, Australia, 1–8.  https://doi.org/10.1109/CEC.2012.6256154
  * Gathercole and Ross (1994) Chris Gathercole and Peter Ross. 1994.  Dynamic training subset selection for supervised learning in Genetic Programming.  In _Parallel Problem Solving from Nature — PPSN III_ , Gerhard Goos, Juris Hartmanis, Jan Leeuwen, Yuval Davidor, Hans-Paul Schwefel, and Reinhard Männer (Eds.). Vol. 866. Springer Berlin Heidelberg, Berlin, Heidelberg, 312–321.  https://doi.org/10.1007/3-540-58484-6_275
  * Geiger et al. (2023) Alina Geiger, Dominik Sobania, and Franz Rothlauf. 2023.  Down-Sampled Epsilon-Lexicase Selection for Real-World Symbolic Regression Problems.  http://arxiv.org/abs/2302.04301 arXiv:2302.04301 [cs].
  * Godin-Dubois et al. (2019) Kevin Godin-Dubois, Sylvain Cussat-Blanc, and Yves Duthen. 2019.  APOGeT: Automated Phylogeny Over Geological Timescales.  (2019).  https://doi.org/10.13140/RG.2.2.33781.93921 Publisher: Unpublished.
  * Helmuth and Abdelhady (2020) Thomas Helmuth and Amr Abdelhady. 2020.  Benchmarking parent selection for program synthesis by genetic programming. In _Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion_. ACM, Cancún Mexico, 237–238.  https://doi.org/10.1145/3377929.3389987
  * Helmuth and Kelly (2021) Thomas Helmuth and Peter Kelly. 2021.  PSB2: the second program synthesis benchmark suite. In _Proceedings of the Genetic and Evolutionary Computation Conference_. ACM, Lille France, 785–794.  https://doi.org/10.1145/3449639.3459285
  * Helmuth and Kelly (2022) Thomas Helmuth and Peter Kelly. 2022.  Applying genetic programming to PSB2: the next generation program synthesis benchmark suite.  _Genetic Programming and Evolvable Machines_ (June 2022).  https://doi.org/10.1007/s10710-022-09434-y
  * Helmuth et al. (2019) Thomas Helmuth, Edward Pantridge, and Lee Spector. 2019.  Lexicase selection of specialists. In _Proceedings of the Genetic and Evolutionary Computation Conference on - GECCO ’19_. ACM Press, Prague, Czech Republic, 1030–1038.  https://doi.org/10.1145/3321707.3321875
  * Helmuth and Spector (2015) Thomas Helmuth and Lee Spector. 2015.  General Program Synthesis Benchmark Suite. In _Proceedings of the 2015 on Genetic and Evolutionary Computation Conference - GECCO ’15_. ACM Press, Madrid, Spain, 1039–1046.  https://doi.org/10.1145/2739480.2754769
  * Helmuth and Spector (2022) Thomas Helmuth and Lee Spector. 2022.  Problem-Solving Benefits of Down-Sampled Lexicase Selection.  _Artificial Life_ 27, 3 (2022), 183–203.  https://doi.org/10.1162/artl_a_00341
  * Hernandez et al. (2022a) Jose Guadalupe Hernandez, Alexander Lalejini, and Emily Dolson. 2022a.  What Can Phylogenetic Metrics Tell us About Useful Diversity in Evolutionary Algorithms?  In _Genetic Programming Theory and Practice XVIII_ , Wolfgang Banzhaf, Leonardo Trujillo, Stephan Winkler, and Bill Worzel (Eds.). Springer Nature, 63–82.  https://doi.org/10.1007/978-981-16-8113-4_4
  * Hernandez et al. (2019) Jose Guadalupe Hernandez, Alexander Lalejini, Emily Dolson, and Charles Ofria. 2019.  Random subsampling improves performance in lexicase selection. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ (New York, NY, USA, 2019-07-13) _(GECCO ’19)_. Association for Computing Machinery, 2028–2031.  https://doi.org/10.1145/3319619.3326900
  * Hernandez et al. (2022b) Jose Guadalupe Hernandez, Alexander Lalejini, and Charles Ofria. 2022b.  An Exploration of Exploration: Measuring the Ability of Lexicase Selection to Find Obscure Pathways to Optimality.  In _Genetic Programming Theory and Practice XVIII_ , Wolfgang Banzhaf, Leonardo Trujillo, Stephan Winkler, and Bill Worzel (Eds.). Springer Nature Singapore, Singapore, 83–107.  https://doi.org/10.1007/978-981-16-8113-4_5 Series Title: Genetic and Evolutionary Computation.
  * Hernandez et al. (2022c) Jose Guadalupe Hernandez, Alexander Lalejini, and Charles Ofria. 2022c.  A suite of diagnostic metrics for characterizing selection schemes.  (2022).  https://doi.org/10.48550/ARXIV.2204.13839 Publisher: arXiv Version Number: 2.
  * Jiang and Yang (2017) Shouyong Jiang and Shengxiang Yang. 2017.  Evolutionary Dynamic Multiobjective Optimization: Benchmarks and Algorithm Comparisons.  _IEEE Transactions on Cybernetics_ 47, 1 (Jan. 2017), 198–211.  https://doi.org/10.1109/TCYB.2015.2510698
  * Jin (2005) Y. Jin. 2005.  A comprehensive survey of fitness approximation in evolutionary computation.  _Soft Computing_ 9, 1 (Jan. 2005), 3–12.  https://doi.org/10.1007/s00500-003-0328-5
  * Jin (2011) Yaochu Jin. 2011.  Surrogate-assisted evolutionary computation: Recent advances and future challenges.  _Swarm and Evolutionary Computation_ 1, 2 (June 2011), 61–70.  https://doi.org/10.1016/j.swevo.2011.05.001
  * La Cava et al. (2016) William La Cava, Lee Spector, and Kourosh Danai. 2016.  Epsilon-Lexicase Selection for Regression. In _Proceedings of the Genetic and Evolutionary Computation Conference 2016_. ACM, Denver Colorado USA, 741–748.  https://doi.org/10.1145/2908812.2908898
  * Lalejini et al. (2024) Alex Lalejini, Emily Dolson, and Matthew Andres Moreno. 2024.  _Supplemental material (GitHub repository)_.  https://doi.org/10.5281/zenodo.10576330 https://lalejini.com/GECCO-2024-phylogeny-informed-subsampling/bookdown/book/.
  * Lalejini et al. (2022) Alexander Lalejini, Emily Dolson, Anya E Vostinar, and Luis Zaman. 2022.  Artificial selection methods from evolutionary computing show promise for directed evolution of microbes.  _eLife_ 11 (Aug. 2022), e79665.  https://doi.org/10.7554/eLife.79665
  * Lalejini et al. (ress) Alexander Lalejini, Matthew Andres Moreno, Jose Guadalupe Hernandez, and Emily Dolson. in press.  Phylogeny-informed fitness estimation for test-based parent selection.  In _Genetic Programming Theory and Practice XX_ , Stephan Winkler, Leonardo Trujillo, Charles Ofria, and Ting Hu (Eds.). Springer International Publishing.  arXiv:2306.03970
  * Lalejini and Ofria (2018) Alexander Lalejini and Charles Ofria. 2018.  Evolving event-driven programs with SignalGP. In _Proceedings of the Genetic and Evolutionary Computation Conference on - GECCO ’18_. ACM Press, Kyoto, Japan, 1135–1142.  https://doi.org/10.1145/3205455.3205523
  * Lalejini et al. (2017) Alexander Lalejini, Michael J. Wiser, and Charles Ofria. 2017.  Gene duplications drive the evolution of complex traits and regulation. In _Proceedings of the 14th European Conference on Artificial Life ECAL 2017_. MIT Press, Lyon, France, 257–264.  https://doi.org/10.7551/ecal_a_045
  * Lalejini (2024) Alexander M Lalejini. 2024.  (Dataset) Archived experiment data.  https://doi.org/10.17605/OSF.IO/H3F52
  * Lozano et al. (2008) Manuel Lozano, Francisco Herrera, and José Ramón Cano. 2008.  Replacement strategies to preserve useful diversity in steady-state genetic algorithms.  _Information Sciences_ 178, 23 (2008), 4421–4433.  https://doi.org/10.1016/j.ins.2008.07.031 Including Special Section: Genetic and Evolutionary Computing.
  * Matsumoto et al. (2023) Nicholas Matsumoto, Anil Kumar Saini, Pedro Ribeiro, Hyunjun Choi, Alena Orlenko, Leo-Pekka Lyytikäinen, Jari O. Laurikka, Terho Lehtimäki, Sandra Batista, and Jason H. Moore. 2023.  Faster Convergence with Lexicase Selection in Tree-Based Automated Machine Learning.  In _Genetic Programming_ , Gisele Pappa, Mario Giacobini, and Zdenek Vasicek (Eds.). Vol. 13986. Springer Nature Switzerland, Cham, 165–181.  https://doi.org/10.1007/978-3-031-29573-7_11 Series Title: Lecture Notes in Computer Science.
  * McPhee et al. (2017) Nicholas Freitag McPhee, Maggie M. Casale, Mitchell Finzel, Thomas Helmuth, and Lee Spector. 2017.  Visualizing genetic programming ancestries using graph databases. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_. ACM, Berlin Germany, 245–246.  https://doi.org/10.1145/3067695.3075617
  * McPhee et al. (2016) Nicholas Freitag McPhee, David Donatucci, and Thomas Helmuth. 2016.  Using Graph Databases to Explore the Dynamics of Genetic Programming Runs.  In _Genetic Programming Theory and Practice XIII_ , Rick Riolo, W.P. Worzel, Mark Kotanchek, and Arthur Kordon (Eds.). Springer International Publishing, 185–201.  https://doi.org/10.1007/978-3-319-34223-8_11
  * McPhee and Hopper (1999) Nicholas Freitag McPhee and Nicholas J. Hopper. 1999.  Analysis of Genetic Diversity through Population History. In _Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 2_ _(GECCO’99)_. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1112–1120.  event-place: Orlando, Florida.
  * Metevier et al. (2019) Blossom Metevier, Anil Kumar Saini, and Lee Spector. 2019.  Lexicase Selection Beyond Genetic Programming.  In _Genetic Programming Theory and Practice XVI_ , Wolfgang Banzhaf, Lee Spector, and Leigh Sheneman (Eds.). Springer International Publishing, Cham, 123–136.  https://doi.org/10.1007/978-3-030-04735-1_7 Series Title: Genetic and Evolutionary Computation.
  * Moore and Stanton (2017) Jared M. Moore and Adam Stanton. 2017.  Lexicase selection outperforms previous strategies for incremental evolution of virtual creature controllers. In _Proceedings of the 14th European Conference on Artificial Life ECAL 2017_. MIT Press, Lyon, France, 290–297.  https://doi.org/10.7551/ecal_a_050
  * Moore and Stanton (2019) Jared M. Moore and Adam Stanton. 2019.  The Limits of Lexicase Selection in an Evolutionary Robotics Task. In _The 2019 Conference on Artificial Life_. MIT Press, Newcastle, United Kingdom, 551–558.  https://doi.org/10.1162/isal_a_00220
  * Moreno et al. (2022) Matthew Andres Moreno, Emily Dolson, and Charles Ofria. 2022.  hstrat: a Python Package for phylogenetic inference ondistributed digital evolution populations.  _Journal of Open Source Software_ 7, 80 (Dec. 2022), 4866.  https://doi.org/10.21105/joss.04866
  * Ofria et al. (2020) Charles Ofria, Matthew Andres Moreno, Emily Dolson, Alexander Lalejini, Santiago Rodriguez Papa, Jake Fenton, Katherine Perry, Steven Jorgensen, Hoffmanriley, Grenewode, Oliver Baldwin Edwards, Jason Stredwick, Cgnitash, theycallmeheem, Anya Vostinar, Ryan Moreno, Jory Schossau, Luis Zaman, and djrain. 2020.  Empirical: C++ library for efficient, reliable, and accessible scientific software.  https://doi.org/10.5281/ZENODO.4141943 [Computer Software].
  * Orzechowski et al. (2018) Patryk Orzechowski, William La Cava, and Jason H. Moore. 2018.  Where are we now? a large benchmark study of recent symbolic regression methods. In _Proceedings of the Genetic and Evolutionary Computation Conference_. ACM, Kyoto Japan, 1183–1190.  https://doi.org/10.1145/3205455.3205539
  * Pilato et al. (2010) Christian Pilato, Daniele Loiacono, Antonino Tumeo, Fabrizio Ferrandi, Pier Luca Lanzi, and Donatella Sciuto. 2010.  Speeding-Up Expensive Evaluations in High-Level Synthesis Using Solution Modeling and Fitness Inheritance.  In _Computational Intelligence in Expensive Optimization Problems_ , Lim Meng Hiot, Yew Soon Ong, Yoel Tenne, and Chi-Keong Goh (Eds.). Vol. 2. Springer Berlin Heidelberg, Berlin, Heidelberg, 701–723.  https://doi.org/10.1007/978-3-642-10701-6_26 Series Title: Evolutionary Learning and Optimization.
  * Pilato et al. (2007) Christian Pilato, Gianluca Palermo, Antonino Tumeo, Fabrizio Ferrandi, Donatella Sciuto, and Pier Luca Lanzi. 2007.  Fitness inheritance in evolutionary and multi-objective high-level synthesis. In _2007 IEEE Congress on Evolutionary Computation_. IEEE, Singapore, 3459–3466.  https://doi.org/10.1109/CEC.2007.4424920
  * Raup (1992) David M. Raup. 1992.  _Extinction: Bad Genes or Bad Luck?_ (1 ed.).  W. W. Norton and Company.
  * Rothan and Byrareddy (2020) Hussin A. Rothan and Siddappa N. Byrareddy. 2020.  The epidemiology and pathogenesis of coronavirus disease (COVID-19) outbreak.  _Journal of Autoimmunity_ 109 (May 2020), 102433.  https://doi.org/10.1016/j.jaut.2020.102433
  * Schweim et al. (2022) Dirk Schweim, Dominik Sobania, and Franz Rothlauf. 2022.  Effects of the Training Set Size: A Comparison of Standard and Down-Sampled Lexicase Selection in Program Synthesis. In _2022 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, Padua, Italy, 1–8.  https://doi.org/10.1109/CEC55065.2022.9870337
  * Shahbandegan et al. (2022) Shakiba Shahbandegan, Jose Guadalupe Hernandez, Alexander Lalejini, and Emily Dolson. 2022.  Untangling phylogenetic diversity’s role in evolutionary computation using a suite of diagnostic fitness landscapes. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ (New York, NY, USA, 2022-07-19) _(GECCO ’22)_. Association for Computing Machinery, 2322–2325.  https://doi.org/10.1145/3520304.3534028
  * Shi and Rasheed (2008) Liang Shi and Khaled Rasheed. 2008.  ASAGA: an adaptive surrogate-assisted genetic algorithm. In _Proceedings of the 10th annual conference on Genetic and evolutionary computation_. ACM, Atlanta GA USA, 1049–1056.  https://doi.org/10.1145/1389095.1389289
  * Spector (2012) Lee Spector. 2012.  Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report. In _Proceedings of the 14th annual conference companion on Genetic and evolutionary computation_ (2012). ACM, 401–408.  http://dl.acm.org/citation.cfm?id=2330846
  * Stanton and Moore (2022) Adam Stanton and Jared M. Moore. 2022.  Lexicase Selection for Multi-Task Evolutionary Robotics.  _Artificial Life_ 28, 4, 479–498.  https://doi.org/10.1162/artl_a_00374
  * Tucker et al. (2017) Caroline M. Tucker, Marc W. Cadotte, Silvia B. Carvalho, T. Jonathan Davies, Simon Ferrier, Susanne A. Fritz, Rich Grenyer, Matthew R. Helmus, Lanna S. Jin, Arne O. Mooers, Sandrine Pavoine, Oliver Purschke, David W. Redding, Dan F. Rosauer, Marten Winter, and Florent Mazel. 2017.  A guide to phylogenetic metrics for conservation, community ecology and macroecology: A guide to phylogenetic metrics for ecology.  _Biological Reviews_ 92, 2 (May 2017), 698–715.  https://doi.org/10.1111/brv.12252
  * Wang and Ting (2018) Ting-Chen Wang and Chuan-Kang Ting. 2018.  Fitness Inheritance Assisted MOEA/D-CMAES for Complex Multi-Objective Optimization Problems. In _2018 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, Rio de Janeiro, 1–8.  https://doi.org/10.1109/CEC.2018.8477898
  * Wiley and Lieberman (2011) E. O. Wiley and Bruce S. Lieberman. 2011.  _Phylogenetics: Theory and Practice of Phylogenetic Systematics_.  John Wiley & Sons.