{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T10:10:52Z","timestamp":1783764652960,"version":"3.55.0"},"reference-count":50,"publisher":"MIT Press - Journals","issue":"3\u20134","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,3,16]]},"abstract":"<jats:p>In genetic programming, an evolutionary method for producing computer programs that solve specified computational problems, parent selection is ordinarily based on aggregate measures of performance across an entire training set. Lexicase selection, by contrast, selects on the basis of performance on random sequences of training cases; this has been shown to enhance problem-solving power in many circumstances. Lexicase selection can also be seen as better reflecting biological evolution, by modeling sequences of challenges that organisms face over their lifetimes. Recent work has demonstrated that the advantages of lexicase selection can be amplified by down-sampling, meaning that only a random subsample of the training cases is used each generation. This can be seen as modeling the fact that individual organisms encounter only subsets of the possible environments and that environments change over time. Here we provide the most extensive benchmarking of down-sampled lexicase selection to date, showing that its benefits hold up to increased scrutiny. The reasons that down-sampling helps, however, are not yet fully understood. Hypotheses include that down-sampling allows for more generations to be processed with the same budget of program evaluations; that the variation of training data across generations acts as a changing environment, encouraging adaptation; or that it reduces overfitting, leading to more general solutions. We systematically evaluate these hypotheses, finding evidence against all three, and instead draw the conclusion that down-sampled lexicase selection's main benefit stems from the fact that it allows the evolutionary process to examine more individuals within the same computational budget, even though each individual is examined less completely.<\/jats:p>","DOI":"10.1162\/artl_a_00341","type":"journal-article","created":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T17:40:26Z","timestamp":1630604426000},"page":"183-203","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":24,"title":["Problem-Solving Benefits of Down-Sampled Lexicase Selection"],"prefix":"10.1162","volume":"27","author":[{"given":"Thomas","family":"Helmuth","sequence":"first","affiliation":[{"name":"Hamilton College. thelmuth@hamilton.edu"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lee","family":"Spector","sequence":"additional","affiliation":[{"name":"Amherst College"},{"name":"Hampshire College"},{"name":"University of Massachusetts Amherst. lspector@amherst.edu"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","published-online":{"date-parts":[[2022,3,16]]},"reference":[{"key":"2022032316101262000_bib1","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1145\/3321707.3321828","article-title":"Lexicase selection in learning classifier systems","volume-title":"GECCO '19: Proceedings of the genetic and evolutionary computation conference","author":"Aenugu","year":"2019"},{"issue":"1","key":"2022032316101262000_bib2","doi-asserted-by":"publisher","first-page":"e1009314","DOI":"10.1371\/journal.pgen.1009314","article-title":"Adaptation is influenced by the complexity of environmental change during evolution in a dynamic environment","volume":"17","author":"Boyer","year":"2021","journal-title":"PLOS Genetics"},{"issue":"4","key":"2022032316101262000_bib3","doi-asserted-by":"publisher","first-page":"e1006445","DOI":"10.1371\/journal.pcbi.1006445","article-title":"Fluctuating environments select for short-term phenotypic variation leading to long-term exploration","volume":"15","author":"Canino-Koning","year":"2019","journal-title":"PLOS Computational Biology"},{"key":"2022032316101262000_bib4","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1145\/3321707.3321804","article-title":"Autonomous skill discovery with quality-diversity and unsupervised descriptors","volume-title":"GECCO '19: Proceedings of the genetic and evolutionary computation conference companion","author":"Cully","year":"2019"},{"issue":"2","key":"2022032316101262000_bib5","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1109\/TEVC.2017.2704781","article-title":"Quality and diversity optimization: A unifying modular framework","volume":"22","author":"Cully","year":"2018","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2022032316101262000_bib6","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-540-24840-8_12","article-title":"Towards efficient training on large datasets for genetic programming","volume-title":"Advances in artificial intelligence: Canadian AI 2004","author":"Curry","year":"2004"},{"issue":"2","key":"2022032316101262000_bib7","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/4235.996017","article-title":"A fast and elitist multiobjective genetic algorithm: NSGA-II","volume":"6","author":"Deb","year":"2002","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2022032316101262000_bib8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-39958-0_1","article-title":"Characterizing the effects of random subsampling and dilution on lexicase selection","volume-title":"Genetic programming theory and practice XVII","author":"Ferguson","year":"2019"},{"key":"2022032316101262000_bib9","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-319-55696-3_17","article-title":"A grammar design pattern for arbitrary program synthesis problems in genetic programming","volume-title":"Genetic programming: 20th European conference: EuroGP 2017","author":"Forstenlechner","year":"2017"},{"key":"2022032316101262000_bib10","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/3-540-58484-6_275","article-title":"Dynamic training subset selection for supervised learning in genetic programming","volume-title":"Parallel problem solving from nature\u2014PPSN III. PPSN 1994","author":"Gathercole","year":"1994"},{"key":"2022032316101262000_bib11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-37207-0_7","article-title":"Balancing learning and overfitting in genetic programming with interleaved sampling of training data","volume-title":"Genetic Programming: EuroGP 2013","author":"Goncalves","year":"2013"},{"key":"2022032316101262000_bib12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1145\/3377929.3389987","article-title":"Benchmarking parent selection for program synthesis by genetic programming","volume-title":"GECCO '20: Proceedings of the 2015 annual conference on genetic and evolutionary computation companion","author":"Helmuth","year":"2020"},{"key":"2022032316101262000_bib13","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1145\/3449639.3459285","article-title":"PSB2: The second program synthesis benchmark suite","volume-title":"GECCO '21: Proceedings of the genetic and evolutionary computation conference","author":"Helmuth","year":"2021"},{"key":"2022032316101262000_bib14","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1145\/3071178.3071330","article-title":"Improving generalization of evolved programs through automatic simplification","volume-title":"GECCO '17: Proceedings of the genetic and evolutionary computation conference","author":"Helmuth","year":"2017"},{"key":"2022032316101262000_bib15","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1145\/2908812.2908851","article-title":"The impact of hyperselection on lexicase selection","volume-title":"GECCO '16: Proceedings of the 2016 annual conference on genetic and evolutionary computation","author":"Helmuth","year":"2016"},{"key":"2022032316101262000_bib16","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1145\/3205455.3205603","article-title":"Program synthesis using uniform mutation by addition and deletion","volume-title":"GECCO '18: Proceedings of the genetic and evolutionary computation conference","author":"Helmuth","year":"2018"},{"key":"2022032316101262000_bib17","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1145\/2739480.2754769","article-title":"General program synthesis benchmark suite","volume-title":"GECCO '15: Proceedings of the 2015 annual conference on genetic and evolutionary computation","author":"Helmuth","year":"2015"},{"key":"2022032316101262000_bib18","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1162\/isal_a_00334","article-title":"Explaining and exploiting the advantages of down-sampled lexicase selection","volume-title":"Proceedings of the ALIFE 2020: The 2020 conference on artificial life","author":"Helmuth","year":"2020"},{"issue":"5","key":"2022032316101262000_bib19","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1109\/TEVC.2014.2362729","article-title":"Solving uncompromising problems with lexicase selection","volume":"19","author":"Helmuth","year":"2015","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2022032316101262000_bib20","doi-asserted-by":"publisher","first-page":"2028","DOI":"10.1145\/3319619.3326900","article-title":"Random subsampling improves performance in lexicase selection","volume-title":"GECCO '19: Proceedings of the genetic and evolutionary computation conference companion","author":"Hernandez","year":"2019"},{"key":"2022032316101262000_bib21","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-319-47898-2_6","article-title":"Sampling methods in genetic programming learners from large datasets: A comparative study","volume-title":"Advances in big data: Proceedings of the 2nd INNS conference on big data","author":"Hmida","year":"2016"},{"issue":"34","key":"2022032316101262000_bib22","doi-asserted-by":"publisher","first-page":"13711","DOI":"10.1073\/pnas.0611630104","article-title":"Varying environments can speed up evolution","volume":"104","author":"Kashtan","year":"2007","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2022032316101262000_bib23","first-page":"2698","article-title":"An alternative view: When does SGD escape local minima?","volume-title":"Proceedings of the 35th international conference on machine learning, PMLR 80","author":"Kleinberg","year":"2018"},{"key":"2022032316101262000_bib24","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-0-387-49650-4_11","article-title":"Pursuing the pareto paradigm tournaments, algorithm variations & ordinal optimization","volume-title":"Genetic programming theory and practice IV","author":"Kotanchek","year":"2006"},{"key":"2022032316101262000_bib25","first-page":"145","article-title":"Exploiting trustable models via pareto GP for targeted data collection","volume-title":"Genetic programming theory and practice VI","author":"Kotanchek","year":"2008"},{"key":"2022032316101262000_bib26","volume-title":"Genetic programming: On the programming of computers by means of natural selection","author":"Koza","year":"1992"},{"issue":"3","key":"2022032316101262000_bib27","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1162\/evco_a_00224","article-title":"A probabilistic and multi-objective analysis of lexicase selection and \u03b5-lexicase selection","volume":"27","author":"La Cava","year":"2019","journal-title":"Evolutionary Computation"},{"key":"2022032316101262000_bib28","doi-asserted-by":"publisher","DOI":"10.1515\/9780691209418","volume-title":"Evolution in changing environments: Some theoretical explorations","author":"Levins","year":"1968"},{"key":"2022032316101262000_bib29","doi-asserted-by":"publisher","first-page":"1301","DOI":"10.1145\/2739482.2768505","article-title":"Comparison of semantic-aware selection methods in genetic programming","volume-title":"GECCO '15: Semantic methods in genetic programming (SMGP'15) workshop","author":"Liskowski","year":"2015"},{"issue":"6","key":"2022032316101262000_bib30","doi-asserted-by":"publisher","first-page":"1203","DOI":"10.1080\/0952813X.2017.1328461","article-title":"A comparison of fitness-case sampling methods for genetic programming","volume":"29","author":"Martinez","year":"2017","journal-title":"Journal of Experimental & Theoretical Artificial Intelligence"},{"key":"2022032316101262000_bib31","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-030-04735-1_7","article-title":"Lexicase selection beyond genetic programming","volume-title":"Genetic programming theory and practice XVI","author":"Metevier","year":"2019"},{"key":"2022032316101262000_bib32","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1162\/isal_a_050","article-title":"Lexicase selection outperforms previous strategies for incremental evolution of virtual creature controllers","volume-title":"Proceedings of the ECAL 2017, the fourteenth European conference on artificial life","author":"Moore","year":"2017"},{"key":"2022032316101262000_bib33","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1162\/isal_a_00109","article-title":"Tiebreaks and diversity: Isolating effects in lexicase selection","volume-title":"Proceedings of the ALIFE 2018: The 2018 conference on artificial life","author":"Moore","year":"2018"},{"key":"2022032316101262000_bib34","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1162\/isal_a_00220","article-title":"The limits of lexicase selection in an evolutionary robotics task","volume-title":"Proceedings of the ALIFE 2019: The 2019 conference on artificial life","author":"Moore","year":"2019"},{"key":"2022032316101262000_bib35","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1162\/isal_a_00254","article-title":"When specialists transition to generalists: Evolutionary pressure in lexicase selection","volume-title":"Proceedings of the ALIFE 2020: The 2020 conference on artificial life","author":"Moore","year":"2020"},{"key":"2022032316101262000_bib36","article-title":"Illuminating search spaces by mapping elites","author":"Mouret","year":"2015"},{"key":"2022032316101262000_bib37","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1162\/isal_a_052","article-title":"Improved adaptation in exogenously and endogenously changing environments","volume-title":"Proceedings of the ECAL 2017, the fourteenth European conference on artificial life","author":"Nahum","year":"2017"},{"key":"2022032316101262000_bib38","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1109\/CEC.2017.7969310","article-title":"Lexicase selection promotes effective search and behavioural diversity of solutions in linear genetic programming","volume-title":"2017 IEEE congress on evolutionary computation (CEC)","author":"Oksanen","year":"2017"},{"key":"2022032316101262000_bib39","doi-asserted-by":"publisher","first-page":"1183","DOI":"10.1145\/3205455.3205539","article-title":"Where are we now? A large benchmark study of recent symbolic regression methods","volume-title":"GECCO '18: Proceedings of the genetic and evolutionary computation conference","author":"Orzechowski","year":"2018"},{"key":"2022032316101262000_bib40","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-0-387-49650-4_8","article-title":"Co-evolving fitness predictors for accelerating and reducing evaluations","volume-title":"Genetic programming theory and practice IV","author":"Schmidt","year":"2006"},{"issue":"6","key":"2022032316101262000_bib41","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1109\/TEVC.2008.919006","article-title":"Coevolution of fitness predictors","volume":"12","author":"Schmidt","year":"2008","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2022032316101262000_bib42","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-1-4419-7747-2_8","article-title":"Age-fitness pareto optimization","volume-title":"Genetic programming theory and practice VIII","author":"Schmidt","year":"2010"},{"key":"2022032316101262000_bib43","doi-asserted-by":"publisher","first-page":"949","DOI":"10.1145\/1830483.1830652","article-title":"Predicting solution rank to improve performance","volume-title":"GECCO '10: Proceedings of the 12th annual conference on genetic and evolutionary computation","author":"Schmidt","year":"2010"},{"key":"2022032316101262000_bib44","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/2330784.2330846","article-title":"Assessment of problem modality by differential performance of lexicase selection in genetic programming: A preliminary report","volume-title":"GECCO '12: Proceedings of the 14th annual conference companion on genetic and evolutionary computation, Session: Understanding problems (GECCO-UP)","author":"Spector","year":"2012"},{"key":"2022032316101262000_bib45","doi-asserted-by":"publisher","first-page":"1689","DOI":"10.1145\/1068009.1068292","article-title":"The Push3 execution stack and the evolution of control","volume-title":"GECCO 2005: Proceedings of the 2005 conference on genetic and evolutionary computation","author":"Spector","year":"2005"},{"key":"2022032316101262000_bib46","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-319-90512-9_7","article-title":"Relaxations of lexicase parent selection","volume-title":"Genetic programming theory and practice XV","author":"Spector","year":"2017"},{"key":"2022032316101262000_bib47","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1145\/2908961.2931727","article-title":"Evolution evolves with autoconstruction","volume-title":"GECCO '16: Proceedings of the 2016 annual conference on genetic and evolutionary computation","author":"Spector","year":"2016"},{"issue":"1","key":"2022032316101262000_bib48","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1023\/A:1014538503543","article-title":"Genetic programming and autoconstructive evolution with the Push programming language","volume":"3","author":"Spector","year":"2002","journal-title":"Genetic Programming and Evolvable Machines"},{"issue":"4","key":"2022032316101262000_bib49","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1109\/TEVC.2017.2735550","article-title":"Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm","volume":"22","author":"Vassiliades","year":"2018","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2022032316101262000_bib50","first-page":"1217","article-title":"Genetic programming with incremental data inheritance","volume-title":"GECCO-99: Proceedings of the genetic and evolutionary computation conference","author":"Zhang","year":"1999"}],"container-title":["Artificial Life"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/artl\/article-pdf\/27\/3%E2%80%934\/183\/2003245\/artl_a_00341.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/artl\/article-pdf\/27\/3%E2%80%934\/183\/2003245\/artl_a_00341.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T16:10:39Z","timestamp":1648051839000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/artl\/article\/27\/3%E2%80%934\/183\/106924\/Problem-Solving-Benefits-of-Down-Sampled-Lexicase"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":50,"journal-issue":{"issue":"3\u20134","published-online":{"date-parts":[[2022,3,16]]},"published-print":{"date-parts":[[2022,3,16]]}},"URL":"https:\/\/doi.org\/10.1162\/artl_a_00341","relation":{},"ISSN":["1064-5462","1530-9185"],"issn-type":[{"value":"1064-5462","type":"print"},{"value":"1530-9185","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021]]},"published":{"date-parts":[[2021]]}}}