More Web Proxy on the site http://driver.im/

research-article

Probabilistic Lexicase Selection

Authors:

Edward Pantridge,

Lee SpectorAuthors Info & Claims

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1073 - 1081

https://doi.org/10.1145/3583131.3590375

Published: 12 July 2023 Publication History

Abstract

Lexicase selection is a widely used parent selection algorithm in genetic programming, known for its success in various task domains such as program synthesis, symbolic regression, and machine learning. Due to its non-parametric and recursive nature, calculating the probability of each individual being selected by lexicase selection has been proven to be an NP-hard problem, which discourages deeper theoretical understanding and practical improvements to the algorithm. In this work, we introduce probabilistic lexicase selection (plexicase selection), a novel parent selection algorithm that efficiently approximates the probability distribution of lexicase selection. Our method not only demonstrates superior problem-solving capabilities as a semantic-aware selection method, but also benefits from having a probabilistic representation of the selection process for enhanced efficiency and flexibility. Experiments are conducted in two prevalent domains in genetic programming: program synthesis and symbolic regression, using standard benchmarks including PSB and SRBench. The empirical results show that plexicase selection achieves state-of-the-art problem-solving performance that is competitive to the lexicase selection, and significantly outperforms lexicase selection in computation efficiency.

Supplementary Material

PDF File (p1073-ding-suppl.pdf)

Supplemental material.

Download
434.43 KB

References

[1]

Sneha Aenugu and Lee Spector. 2019. Lexicase selection in learning classifier systems. In Proceedings of the Genetic and Evolutionary Computation Conference. 356--364.

Digital Library

[2]

James Edward Baker. 2014. Adaptive selection methods for genetic algorithms. In Proceedings of the first international conference on genetic algorithms and their applications. Psychology Press, 101--106.

[3]

James E Baker et al. 1987. Reducing bias and inefficiency in the selection algorithm. In Proceedings of the second international conference on genetic algorithms, Vol. 206. 14--21.

[4]

Ryan Boldi, Martin Briesch, Dominik Sobania, Alexander Lalejini, Thomas Helmuth, Franz Rothlauf, Charles Ofria, and Lee Spector. 2023. Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving. arXiv preprint arXiv:2301.01488 (2023).

[5]

Vinícius V De Melo, Danilo Vasconcellos Vargas, and Wolfgang Banzhaf. 2019. Batch tournament selection for genetic programming: the quality of lexicase, the speed of tournament. In Proceedings of the genetic and evolutionary computation conference. 994--1002.

Digital Library

[6]

Li Ding, Ryan Boldi, Thomas Helmuth, and Lee Spector. 2022. Going faster and hence further with lexicase selection. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. 538--541.

Digital Library

[7]

Li Ding, Ryan Boldi, Thomas Helmuth, and Lee Spector. 2022. Lexicase selection at scale. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2054--2062.

Digital Library

[8]

Li Ding and Lee Spector. 2021. Evolving neural selection with adaptive regularization. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. 1717--1725.

Digital Library

[9]

Li Ding and Lee Spector. 2022. Evolutionary quantum architecture search for parametrized quantum circuits. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2190--2195.

Digital Library

[10]

Li Ding and Lee Spector. 2022. Optimizing Neural Networks with Gradient Lexicase Selection. In International Conference on Learning Representations.

[11]

Li Ding and Lee Spector. 2023. Multi-Objective Evolutionary Architecture Search for Parameterized Quantum Circuits. Entropy 25, 1 (2023), 93.

[12]

Emily Dolson. 2023. Calculating lexicase selection probabilities is NP-Hard. arXiv preprint arXiv:2301.06724 (2023).

[13]

Austin J. Ferguson, Jose Guadalupe Hernandez, Daniel Junghans, Alexander Lalejini, Emily Dolson, and Charles Ofria. 2019. Characterizing the effects of random subsampling and dilution on Lexicase selection, In Genetic Programming Theory and Practice XVII, Wolfgang Banzhaf, Erik Goodman, Leigh Sheneman, Leonardo Trujillo, and Bill Worzel (Eds.). Genetic Programming Theory and Practice XVII.

[14]

Jonathan E Fieldsend and Alberto Moraglio. 2015. Strength through diversity: Disaggregation and multi-objectivisation approaches for genetic programming. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. 1031--1038.

Digital Library

[15]

Stefan Forstenlechner, David Fagan, Miguel Nicolau, and Michael O'Neill. 2018. Extending program synthesis grammars for grammar-guided genetic programming. In Parallel Problem Solving from Nature-PPSN XV: 15th International Conference, Coimbra, Portugal, September 8--12, 2018, Proceedings, Part I 15. Springer, 197--208.

[16]

Edgar Galvan-Lopez, Brendan Cody-Kenny, Leonardo Trujillo, and Ahmed Kattan. 2013. Using semantics in the selection mechanism in genetic programming: a simple method for promoting semantic diversity. In 2013 IEEE Congress on Evolutionary Computation. IEEE, 2972--2979.

[17]

David E Golberg. 1989. Genetic algorithms in search, optimization, and machine learning. Addion wesley 1989, 102 (1989), 36.

Digital Library

[18]

David E Goldberg and Kalyanmoy Deb. 1991. A comparative analysis of selection schemes used in genetic algorithms. In Foundations of genetic algorithms. Vol. 1. Elsevier, 69--93.

[19]

Thomas Helmuth, Johannes Lengler, and William La Cava. 2022. Population Diversity Leads to Short Running Times of Lexicase Selection. In Parallel Problem Solving from Nature-PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10--14, 2022, Proceedings, Part II. Springer, 485--498.

[20]

Thomas Helmuth, Nicholas Freitag McPhee, and Lee Spector. 2016. The impact of hyperselection on lexicase selection. In Proceedings of the Genetic and Evolutionary Computation Conference 2016. 717--724.

[21]

Thomas Helmuth, Nicholas Freitag McPhee, and Lee Spector. 2016. Lexicase selection for program synthesis: a diversity analysis. In Genetic Programming Theory and Practice XIII. Springer, 151--167.

[22]

Thomas Helmuth, Nicholas Freitag McPhee, and Lee Spector. 2018. Program synthesis using uniform mutation by addition and deletion. In Proceedings of the Genetic and Evolutionary Computation Conference. 1127--1134.

Digital Library

[23]

Thomas Helmuth, Edward Pantridge, and Lee Spector. 2019. Lexicase Selection of Specialists. In Proceedings of the Genetic and Evolutionary Computation Conference (Prague, Czech Republic) (GECCO '19). Association for Computing Machinery, New York, NY, USA, 1030--1038.

Digital Library

[24]

Thomas Helmuth, Edward Pantridge, and Lee Spector. 2020. On the Importance of Specialists for Lexicase Selection. Genetic Programming and Evolvable Machines 21, 3 (sep 2020), 349--373.

Digital Library

[25]

Thomas Helmuth and Lee Spector. 2015. General program synthesis benchmark suite. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. 1039--1046.

Digital Library

[26]

Thomas Helmuth and Lee Spector. 2020. Explaining and exploiting the advantages of down-sampled lexicase selection. In ALIFE 2020: The 2020 Conference on Artificial Life. MIT Press, 341--349.

[27]

Thomas Helmuth and Lee Spector. 2022. Problem-solving benefits of down-sampled lexicase selection. Artificial Life 27, 3--4 (2022), 183--203.

[28]

Thomas Helmuth, Lee Spector, and James Matheson. 2014. Solving uncompromising problems with lexicase selection. IEEE Transactions on Evolutionary Computation 19, 5 (2014), 630--643.

Digital Library

[29]

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. 2028--2031.

Digital Library

[30]

Joost Huizinga and Jeff Clune. 2018. Evolving multimodal robot behavior via many stepping stones with the combinatorial multi-objective evolutionary algorithm. arXiv preprint arXiv:1807.03392 (2018).

[31]

Krzysztof Krawiec and Paweł Liskowski. 2015. Automatic derivation of search objectives for test-based genetic programming. In European Conference on Genetic Programming. Springer, 53--65.

[32]

William La Cava, Thomas Helmuth, Lee Spector, and Jason H Moore. 2019. A probabilistic and multi-objective analysis of lexicase selection and ε-lexicase selection. Evolutionary Computation 27, 3 (2019), 377--402.

Digital Library

[33]

William La Cava and Jason Moore. 2018. Behavioral search drivers and the role of elitism in soft robotics. In ALIFE 2018: The 2018 Conference on Artificial Life. MIT Press, 206--213.

[34]

William La Cava and Jason H Moore. 2020. Genetic programming approaches to learning fair classifiers. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference. 967--975.

Digital Library

[35]

William La Cava and Jason H Moore. 2020. Learning feature spaces for regression with genetic programming. Genetic Programming and Evolvable Machines 21, 3 (2020), 433--467.

Digital Library

[36]

William La Cava, Patryk Orzechowski, Bogdan Burlacu, Fabrício Olivetti de França, Marco Virgolin, Ying Jin, Michael Kommenda, and Jason H Moore. 2021. Contemporary symbolic regression methods and their relative performance. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, Vol. 1.

[37]

William La Cava, Tilak Raj Singh, James Taggart, Srinivas Suri, and Jason H Moore. 2018. Learning concise representations for regression by evolving networks of trees. arXiv preprint arXiv:1807.00981 (2018).

[38]

William La Cava, Lee Spector, and Kourosh Danai. 2016. Epsilon-lexicase selection for regression. In Proceedings of the Genetic and Evolutionary Computation Conference 2016. 741--748.

Digital Library

[39]

Adam Lipowski and Dorota Lipowska. 2012. Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and its Applications 391, 6 (2012), 2193--2196.

[40]

Pawel Liskowski, Krzysztof Krawiec, Thomas Helmuth, and Lee Spector. 2015. Comparison of semantic-aware selection methods in genetic programming. In Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. 1301--1307.

Digital Library

[41]

Alexander McFarlane Mood. 1950. Introduction to the Theory of Statistics. (1950).

[42]

Jared M Moore and Adam Stanton. 2017. Lexicase selection outperforms previous strategies for incremental evolution of virtual creature controllers. In ECAL 2017, the Fourteenth European Conference on Artificial Life. MIT Press, 290--297.

[43]

Jared M Moore and Adam Stanton. 2018. Tiebreaks and Diversity: Isolating Effects in Lexicase Selection., 590--597 pages.

[44]

Edward Pantridge, Thomas Helmuth, and Lee Spector. 2022. Functional code building genetic programming. In Proceedings of the Genetic and Evolutionary Computation Conference. 1000--1008.

Digital Library

[45]

Edward Pantridge and Lee Spector. 2020. Code building genetic programming. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference. 994--1002.

Digital Library

[46]

Karl Pearson. 1900. X. On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 50, 302 (1900), 157--175.

[47]

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. 401--408.

Digital Library

[48]

Sarah Anne Troise and Thomas Helmuth. 2018. Lexicase selection with weighted shuffle. In Genetic Programming Theory and Practice XV. Springer, 89--104.

Cited By

Ding LZhang JClune JSpector LLehman JSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Quality diversity through human feedbackProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692511(11072-11090)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692511
Imai Aldeia GDe França FLa Cava WLi XHandl J(2024)Minimum variance threshold for epsilon-lexicase selectionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654149(905-913)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654149
Helmuth TFedoroff JPantridge ESpector LLi XHandl J(2024)Facilitating Function Application in Code Building Genetic ProgrammingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654068(887-895)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654068
Show More Cited By

Index Terms

Probabilistic Lexicase Selection
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by regression
2. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Non-parametric optimization
        Genetic programming
  2. Probability and statistics
    1. Probabilistic algorithms

Recommendations

Lexicase selection at scale
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference Companion

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 ...
Down-Sampled Epsilon-Lexicase Selection for Real-World Symbolic Regression Problems
GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

Epsilon-lexicase selection is a parent selection method in genetic programming that has been successfully applied to symbolic regression problems. Recently, the combination of random subsampling with lexicase selection significantly improved ...
Epsilon-Lexicase Selection for Regression
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Lexicase selection is a parent selection method that considers test cases separately, rather than in aggregate, when performing parent selection. It performs well in discrete error spaces but not on the continuous-valued problems that compose most ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

July 2023

1667 pages

ISBN:9798400701191

DOI:10.1145/3583131

Chair:
Sara Silva,
Program Chair:
Luís Paquete

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '23

Sponsor:

SIGEVO

GECCO '23: Genetic and Evolutionary Computation Conference

July 15 - 19, 2023

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
92
Total Downloads

Downloads (Last 12 months)45
Downloads (Last 6 weeks)6

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ding LZhang JClune JSpector LLehman JSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Quality diversity through human feedbackProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692511(11072-11090)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692511
Imai Aldeia GDe França FLa Cava WLi XHandl J(2024)Minimum variance threshold for epsilon-lexicase selectionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654149(905-913)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654149
Helmuth TFedoroff JPantridge ESpector LLi XHandl J(2024)Facilitating Function Application in Code Building Genetic ProgrammingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654068(887-895)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654068
Rosenfeld LVanneschi L(2024)A survey on batch training in genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-024-09501-626:1Online publication date: 29-Nov-2024
https://doi.org/10.1007/s10710-024-09501-6
Spector LDing LBoldi R(2024)ParticularityGenetic Programming Theory and Practice XX10.1007/978-981-99-8413-8_9(159-176)Online publication date: 18-Feb-2024
https://doi.org/10.1007/978-981-99-8413-8_9

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents