publications

2024

1. 

   Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving

   Ryan Boldi*, Martin Briesch*, Dominik Sobania, and 5 more authors

   Evolutionary Computation 2024

   arXiv Bib Supp Code

   @article{boldi2024informed,
     title = {Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving},
     author = {Boldi*, Ryan and Briesch*, Martin and Sobania, Dominik and Lalejini, Alexander and Helmuth, Thomas and Rothlauf, Franz and Ofria, Charles and Spector, Lee},
     journal = {Evolutionary Computation},
     pages = {1--32},
     year = {2024},
     code = {https://github.com/ryanboldi/Informed-Down-Sampled-Lexicase/tree/main/propeller},
     supp = {https://ryanboldi.github.io/Informed-Down-Sampled-Lexicase/},
     arxiv = {2301.01488},
     preview = {IDS.png},
     bibtex_show = {true},
     selected = {true},
     publisher = {MIT Press One Rogers Street, Cambridge, MA 02142-1209, USA journals-info~…}
   }

2023

1. 

   Objectives Are All You Need: Solving Deceptive Problems Without Explicit Diversity Maintenance

   Ryan Boldi, Li Ding, and Lee Spector

   In The Workshop on Agent Learning in Open-Endedness (ALOE) at the Conference on Neural Information Processing Systems (NeurIPS) 2023
2. 

   Particularity

   Lee Spector, Li Ding, and Ryan Boldi

   In Genetic Programming Theory and Practice XX 2023

   PDF
3. 

   A Static Analysis of Informed Down-Samples

   Ryan Boldi, Alexander Lalejini, Thomas Helmuth, and 1 more author

   In Genetic and Evolutionary Computation Conference Companion (GECCO ’23 Companion), July 15–19, 2023, Lisbon, Portugal 2023

   Abs Bib PDF

   We present an analysis of the loss of population-level test coverage induced by different down-sampling strategies when combined with lexicase selection. We study recorded populations from the first generation of genetic programming runs, as well as entirely synthetic populations. Our findings verify the hypothesis that informed down-sampling better maintains population-level test coverage when compared to random down-sampling. Additionally, we show that both forms of down-sampling cause greater test coverage loss than standard lexicase selection with no down-sampling. However, given more information about the population, we found that informed down-sampling can further reduce its test coverage loss. We also recommend wider adoption of the static population analyses we present in this work.

   @inproceedings{boldi2023static,
     abbr = {GECCO '23},
     author = {Boldi, Ryan and Lalejini, Alexander and Helmuth, Thomas and Spector, Lee},
     title = {A Static Analysis of Informed Down-Samples},
     bibtex_show = {false},
     preview = {static1.png},
     booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '23 Companion), July 15--19, 2023, Lisbon, Portugal},
     pdf = {https://arxiv.org/pdf/2304.01978.pdf},
     year = {2023}
   }

4. 

   The Problem Solving Benefits of Down-Sampling Vary by Selection Scheme

   Ryan Boldi, Ashley Bao, Martin Briesch, and 4 more authors

   In Genetic and Evolutionary Computation Conference Companion (GECCO ’23 Companion), July 15–19, 2023, Lisbon, Portugal 2023

   Bib

   @inproceedings{boldi2023TournDS,
     abbr = {GECCO '23},
     author = {Boldi, Ryan and Bao, Ashley and Briesch, Martin and Helmuth, Thomas and Sobania, Dominik and Spector, Lee and Lalejini, Alexander},
     title = {The Problem Solving Benefits of Down-Sampling Vary by Selection Scheme},
     booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '23 Companion), July 15--19, 2023, Lisbon, Portugal},
     year = {2023},
     preview = {interaction.png},
     bibtex_show = {false}
   }

5. 

   Can the Problem-Solving Benefits of Quality Diversity Be Obtained Without Explicit Diversity Maintenance?

   Ryan Boldi, and Lee Spector

   In Genetic and Evolutionary Computation Conference Companion (GECCO ’23 Companion), July 15–19, 2023, Lisbon, Portugal 2023

   Abs Bib PDF

   When using Quality Diversity (QD) optimization to solve hard exploration or deceptive search problems, we assume that diversity is extrinsically valuable. This means that diversity is important to help us reach an objective, but is not an objective in itself. Often, in these domains, practitioners benchmark their QD algorithms against single objective optimization frameworks. In this paper, we argue that the correct comparison should be made to \emphmulti-objective optimization frameworks. This is because single objective optimization frameworks rely on the aggregation of sub-objectives, which could result in decreased information that is crucial for maintaining diverse populations automatically. In order to facilitate a fair comparison between quality diversity and multi-objective optimization, we present a method that utilizes dimensionality reduction to automatically determine a set of behavioral descriptors for an individual, as well as a set of objectives for an individual to solve. Using the former, one can generate solutions using standard quality diversity optimization techniques, and using the latter, one can generate solutions using standard multi-objective optimization techniques. This allows for a level comparison between these two classes of algorithms, without requiring domain and algorithm specific modifications to facilitate a comparison.

   @inproceedings{boldi2023QDBench,
     abbr = {GECCO '23},
     title = {Can the Problem-Solving Benefits of
     Quality Diversity Be Obtained Without Explicit Diversity Maintenance?},
     year = {2023},
     author = {Boldi, Ryan and Spector, Lee},
     bibtex_show = {false},
     preview = {encoder.png},
     booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '23 Companion), July 15--19, 2023, Lisbon, Portugal},
     pdf = {https://arxiv.org/pdf/2305.07767.pdf}
   }

2022

1. 

   The Environmental Discontinuity Hypothesis for Down-Sampled Lexicase Selection

   Ryan Boldi, Thomas Helmuth, and Lee Spector

   In 2022 Conference on Artificial Life - Why it Didn’t Work-Shop 2022

   Abs Bib PDF

   Down-sampling training data has long been shown to improve the generalization performance of a wide range of machine learning systems. Recently, down-sampling has proved effective in genetic programming (GP) runs that utilize the lexicase parent selection technique. Although this down-sampling procedure has been shown to significantly improve performance across a variety of problems, it does not seem to do so due to encouraging adaptability through environmental change. We hypothesize that the random sampling that is performed every generation causes discontinuities that result in the population being unable to adapt to the shifting environment. We investigate modifications to down-sampled lexicase selection in hopes of promoting incremental environmental change to scaffold evolution by reducing the amount of jarring discontinuities between the environments of successive generations. In our empirical studies, we find that forcing incremental environmental change is not significantly better for evolving solutions to program synthesis problems than simple random down-sampling. In response to this, we attempt to exacerbate the hypothesized prevalence of discontinuities by using only disjoint down-samples to see if it hinders performance. We find that this also does not significantly differ from the performance of regular random down-sampling. These negative results raise new questions about the ways in which the composition of sub-samples, which may include synonymous cases, may be expected to influence the performance of machine learning systems that use down-sampling.

   @inproceedings{boldi2022environmental,
     abbr = {ALIFE '22},
     title = {The Environmental Discontinuity Hypothesis for Down-Sampled Lexicase Selection},
     year = {2022},
     author = {Boldi, Ryan and Helmuth, Thomas and Spector, Lee},
     archiveprefix = {arXiv},
     eprint = {2205.15931},
     bibtex_show = {false},
     preview = {environment.png},
     booktitle = {2022 Conference on Artificial Life - Why it Didn't Work-Shop},
     pdf = {https://arxiv.org/pdf/2205.15931v1.pdf}
   }

2. 

   Lexicase Selection at Scale

   Li Ding, Ryan Boldi, Thomas Helmuth, and 1 more author

   In Genetic and Evolutionary Computation Conference Companion (GECCO ’22 Companion), July 9–13, 2022, Boston, MA, USA 2022

   Abs Bib HTML PDF

   Lexicase selection is a semantic-aware parent selection method, which assesses individual test cases in a randomly-shuffled data stream. It has demonstrated success in multiple research areas including genetic programming, genetic algorithms, and more recently symbolic regression and deep learning. One potential drawback of lexicase selection and its variants is that the selection procedure requires evaluating training cases in a single data stream, making it difficult to handle tasks where the evaluation is computationally heavy or the dataset is large-scale, e.g., deep learning. In this work, we investigate how the weighted shuffle methods can be employed to improve the efficiency of lexicase selection. We propose a novel method, fast lexicase selection, which incorporates lexicase selection and weighted shuffle with partial evaluation. Experiments on both classic genetic programming and deep learning tasks indicate that the proposed method can significantly reduce the number of evaluation steps needed for lexicase selection to select an individual, improving its efficiency while maintaining the performance.

   @inproceedings{ding2022scale,
     abbr = {GECCO '22},
     title = {Lexicase Selection at Scale},
     year = {2022},
     author = {Ding, Li and Boldi, Ryan and Helmuth, Thomas and Spector, Lee},
     booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '22 Companion), July 9--13, 2022, Boston, MA, USA},
     html = {https://dl.acm.org/doi/10.1145/3520304.3534026},
     preview = {scale.png},
     pdf = {https://arxiv.org/pdf/2208.10719.pdf},
     bibtex_show = {false}
   }

3. 

   Going Faster and Hence Further with Lexicase Selection

   Li Ding, Ryan Boldi, Thomas Helmuth, and 1 more author

   In Genetic and Evolutionary Computation Conference Companion (GECCO ’22 Companion), July 9–13, 2022, Boston, MA, USA 2022

   Bib HTML Poster

   @inproceedings{ding2022faster,
     abbr = {GECCO '22},
     title = {Going Faster and Hence Further with Lexicase Selection},
     year = {2022},
     author = {Ding, Li and Boldi, Ryan and Helmuth, Thomas and Spector, Lee},
     bibtex_show = {false},
     preview = {fast.png},
     poster = {gecco22poster.pdf},
     booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '22 Companion), July 9--13, 2022, Boston, MA, USA},
     html = {https://dl.acm.org/doi/10.1145/3520304.3529059}
   }

Under Review

2023

1. 

   Improving Recommendation System Serendipity Through Lexicase Selection

   Ryan Boldi*, Aadam Lokhandwala*, Edward Annatone, and 3 more authors

   arXiv preprint arXiv:2305.11044 2023

   arXiv Bib

   @article{boldi2023improving,
     title = {Improving Recommendation System Serendipity Through Lexicase Selection},
     author = {Boldi*, Ryan and Lokhandwala*, Aadam and Annatone, Edward and Schechter, Yuval and Lavrenenko, Alexander and Sigrist, Cooper},
     publisher = {arXiv},
     journal = {arXiv preprint arXiv:2305.11044},
     url = {https://arxiv.org/abs/2305.11044},
     arxiv = {2305.11044},
     preview = {recsys.png},
     year = {2023},
     bibtex_show = {true},
     copyright = {arXiv.org perpetual, non-exclusive license}
   }