research-article

Public Access

The Impact of Hyperselection on Lexicase Selection

Authors:

Thomas Helmuth,

Nicholas Freitag McPhee,

Lee SpectorAuthors Info & Claims

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Pages 717 - 724

https://doi.org/10.1145/2908812.2908851

Published: 20 July 2016 Publication History

Abstract

Lexicase selection is a parent selection method that has been shown to improve the problem solving power of genetic programming over a range of problems. Previous work has shown that it can also produce hyperselection events, in which a single individual is selected many more times than other individuals. Here we investigate the role that hyperselection plays in the problem-solving performance of lexicase selection. We run genetic programming on a set of program synthesis benchmark problems using lexicase and tournament selection, confirming that hyperselection occurs significantly more often and more drastically with lexicase selection, which also performs significantly better. We then show results from an experiment indicating that hyperselection is not integral to the problem-solving performance or diversity maintenance observed when using lexicase selection. We conclude that the power of lexicase selection stems from the collection of individuals that it selects, not from the unusual frequencies with which it sometimes selects them.

References

[1]

T. Back. Selective pressure in evolutionary algorithms: a characterization of selection mechanisms. In Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on, pages 57--62 vol.1, Jun 1994.

[2]

T. Blickle and L. Thiele. A mathematical analysis of tournament selection. In Proceedings of the 6th International Conference on Genetic Algorithms, pages 9--16, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.

Digital Library

[3]

J. E. Fieldsend and A. Moraglio. Strength through diversity: Disaggregation and multi-objectivisation approaches for genetic programming. In GECCO '15: Proceedings of the 2015 conference on Genetic and evolutionary computation. ACM, 2015.

Digital Library

[4]

E. Galván-López, B. Cody-Kenny, L. Trujillo, and A. Kattan. Using semantics in the selection mechanism in genetic programming: A simple method for promoting semantic diversity. In L. G. de la Fraga, editor, 2013 IEEE Conference on Evolutionary Computation, volume 1, pages 2972--2979, Cancun, Mexico, June 20--23 2013.

[5]

T. Helmuth. General Program Synthesis from Examples Using Genetic Programming with Parent Selection Based on Random Lexicographic Orderings of Test Cases. Ph.D. dissertation, 2015.

[6]

T. Helmuth, N. F. McPhee, and L. Spector. Lexicase selection for program synthesis: a diversity analysis. In Genetic Programming Theory and Practice XIII, Genetic and Evolutionary Computation. Springer.

[7]

T. Helmuth and L. Spector. General program synthesis benchmark suite. In GECCO '15: Proceedings of the 2015 Conference on Genetic and Evolutionary Computation, July 2015.

Digital Library

[8]

T. Helmuth, L. Spector, and J. Matheson. Solving uncompromising problems with lexicase selection. IEEE Transactions on Evolutionary Computation, 19(5):630--643, Oct. 2015.

Digital Library

[9]

K. Krawiec and P. Lichocki. Using co-solvability to model and exploit synergetic effects in evolution. In PPSN 2010 11th International Conference on Parallel Problem Solving From Nature, volume 6239 of Lecture Notes in Computer Science, pages 492--501, Krakow, Poland, 11--15 Sept. 2010. Springer.

Digital Library

[10]

K. Krawiec and P. Liskowski. Automatic derivation of search objectives for test-based genetic programming. In 18th European Conference on Genetic Programming, volume 9025 of LNCS, pages 53--65, Copenhagen, 8--10 Apr. 2015. Springer.

[11]

K. Krawiec, J. Swan, and U.-M. O'Reilly. Behavioral program synthesis: Insights and prospects. In Genetic Programming Theory and Practice XIII, Genetic and Evolutionary Computation. Springer, 2015.

[12]

P. Liskowski, K. Krawiec, T. Helmuth, and L. Spector. Comparison of semantic-aware selection methods in genetic programming. In GECCO 2015 workshop on Semantic Methods in Genetic Programming. ACM, 2015.

Digital Library

[13]

R. I. McKay. Fitness sharing in genetic programming. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pages 435--442, Las Vegas, Nevada, USA, 10--12 July 2000. Morgan Kaufmann.

Digital Library

[14]

N. F. McPhee, D. Donatucci, and T. Helmuth. Using graph databases to explore the dynamics of genetic programming runs. In Genetic Programming Theory and Practice XIII, Genetic and Evolutionary Computation. Springer.

[15]

L. Spector. Assessment of problem modality by differential performance of lexicase selection in genetic programming: A preliminary report. In 1st workshop on Understanding Problems (GECCO-UP), pages 401--408, Philadelphia, Pennsylvania, USA, 7--11 July 2012. ACM.

Digital Library

[16]

L. Spector and T. Helmuth. Uniform linear transformation with repair and alternation in genetic programming. In Genetic Programming Theory and Practice XI, Genetic and Evolutionary Computation, chapter 8, pages 137--153. Springer, Ann Arbor, USA, 9--11 May 2013.

[17]

L. Spector, J. Klein, and M. Keijzer. The Push3 execution stack and the evolution of control. In GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, pages 1689--1696, Washington DC, USA, 2005. ACM Press.

Digital Library

[18]

L. Spector and A. Robinson. Genetic programming and autoconstructive evolution with the push programming language. Genetic Programming and Evolvable Machines, 3(1):7--40, Mar. 2002.

Digital Library

Cited By

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
Xu MMei YZhang FZhang M(2024)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: Oct-2024
https://doi.org/10.1109/TEVC.2023.3244607
Helmuth TPantridge EFrazier JSpector L(2024)Generational Computation Reduction in Informal Counterexample-Driven Genetic ProgrammingGenetic Programming10.1007/978-3-031-56957-9_2(21-37)Online publication date: 3-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-56957-9_2
Show More Cited By

Index Terms

The Impact of Hyperselection on Lexicase Selection
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches
        Genetic programming

Recommendations

Lexicase selection in learning classifier systems
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

The lexicase parent selection method selects parents by considering performance on individual data points in random order instead of using a fitness function based on an aggregated data accuracy. While the method has demonstrated promise in genetic ...
Lexicase selection of specialists
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

Lexicase parent selection filters the population by considering one random training case at a time, eliminating any individuals with errors for the current case that are worse than the best error in the selection pool, until a single individual remains. ...
Effects of Lexicase and Tournament Selection on Diversity Recovery and Maintenance
GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion

In genetic programming systems, parent selection algorithms select the programs from which offspring will be produced by random variation and recombination. While most parent selection algorithms select programs on the basis of aggregate performance on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

July 2016

1196 pages

ISBN:9781450342063

DOI:10.1145/2908812

Editor:
Tobias Friedrich
Hasso Plattner Institute
,
General Chair:
Frank Neumann
University of Adelaide
,
Program Chair:
Andrew M. Sutton
Hasso Plattner Institute

Copyright © 2016 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: 20 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

GECCO '16

Sponsor:

SIGEVO

GECCO '16: Genetic and Evolutionary Computation Conference

July 20 - 24, 2016

Colorado, Denver, USA

Acceptance Rates

GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
434
Total Downloads

Downloads (Last 12 months)97
Downloads (Last 6 weeks)25

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Xu MMei YZhang FZhang M(2024)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: Oct-2024
https://doi.org/10.1109/TEVC.2023.3244607
Helmuth TPantridge EFrazier JSpector L(2024)Generational Computation Reduction in Informal Counterexample-Driven Genetic ProgrammingGenetic Programming10.1007/978-3-031-56957-9_2(21-37)Online publication date: 3-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-56957-9_2
Geiger ASobania DRothlauf FSilva SPaquete L(2023)Down-Sampled Epsilon-Lexicase Selection for Real-World Symbolic Regression ProblemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590400(1109-1117)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590400
Sobania DSchweim DRothlauf F(2023)A Comprehensive Survey on Program Synthesis With Evolutionary AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.316232427:1(82-97)Online publication date: Feb-2023
https://doi.org/10.1109/TEVC.2022.3162324
Zhang HChen QXue BBanzhaf WZhang M(2023)Automatically Choosing Selection Operator Based on Semantic Information in Evolutionary Feature ConstructionPRICAI 2023: Trends in Artificial Intelligence10.1007/978-981-99-7022-3_36(385-397)Online publication date: 10-Nov-2023
https://doi.org/10.1007/978-981-99-7022-3_36
Helmuth TSpector L(2022)Problem-Solving Benefits of Down-Sampled Lexicase SelectionArtificial Life10.1162/artl_a_0034127:3–4(183-203)Online publication date: 16-Mar-2022
https://doi.org/10.1162/artl_a_00341
Helmuth TLengler JLa Cava W(2022)Population Diversity Leads to Short Running Times of Lexicase SelectionParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_34(485-498)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_34
Sobania DRothlauf F(2022)Program Synthesis with Genetic Programming: The Influence of Batch SizesGenetic Programming10.1007/978-3-031-02056-8_8(118-129)Online publication date: 13-Apr-2022
https://doi.org/10.1007/978-3-031-02056-8_8
Helmuth TPantridge ESpector L(2020)On the importance of specialists for lexicase selectionGenetic Programming and Evolvable Machines10.1007/s10710-020-09377-2Online publication date: 30-Jan-2020
https://doi.org/10.1007/s10710-020-09377-2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents