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

research-article

Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report

Author:

Lee SpectorAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

Pages 401 - 408

https://doi.org/10.1145/2330784.2330846

Published: 07 July 2012 Publication History

GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report

Pages 401 - 408

Abstract
References

Abstract

Many potential target problems for genetic programming are modal in the sense that qualitatively different modes of response are required for inputs from different regions of the problem's domain. This paper presents a new approach to solving modal problems with genetic programming, using a simple and novel parent selection method called lexicase selection. It then shows how the differential performance of genetic programming with and without lexicase selection can be used to provide a measure of problem modality, and it argues that defining such a measure in this way is not as methodologically problematic as it may initially appear. The modality measure is illustrated through the analysis of genetic programming runs on a simple modal symbolic regression problem. This is a preliminary report that is intended in part to stimulate discussion on the significance of modal problems, methods for solving them, and methods for measuring the modality of problems. Although the core concepts in this paper are presented in the context of genetic programming, they are also relevant to applications of other forms of evolutionary computation to modal problems.

References

[1]

K. A. Benson. Evolving automatic target detection algorithms that logically combine decision spaces. In Proceedings of the 11th British Machine Vision Conference, pages 685--694, Bristol, UK, 2000.

[2]

K. Imamura, T. Soule, R. B. Heckendorn, and J. A. Foster. Behavioral diversity and a probabilistically optimal GP ensemble. Genetic Programming and Evolvable Machines, 4(3):235--253, Sept. 2003.

Digital Library

[3]

J. Klein and L. Spector. Genetic programming with historically assessed hardness. In R. L. Riolo, T. Soule, and B. Worzel, editors, Genetic Programming Theory and Practice VI, pages 61--75. Springer, 2008.

[4]

M. Kotanchek, G. Smits, and E. Vladislavleva. Pursuing the pareto paradigm tournaments, algorithm variations & ordinal optimization. In R. L. Riolo, T. Soule, and B. Worzel, editors, Genetic Programming Theory and Practice IV, pages 167--186. Springer, 2006.

[5]

J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.

Digital Library

[6]

W. B. Langdon. Genetic Programming and Data Structures: Genetic Programming & Data Structures = Automatic Programming!, volume 1 of Genetic Programming. Kluwer, Boston, 1998.

[7]

W. B. Langdon and B. F. Buxton. Genetic programming for combining classifiers. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 66--73. Morgan Kaufmann, 2001.

[8]

S. Luke and L. Panait. Lexicographic parsimony pressure. In GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pages 829--836. Morgan Kaufmann Publishers, 9--13 July 2002.

Digital Library

[9]

L. Panait and S. Luke. Alternative bloat control methods. In Genetic and Evolutionary Computation -- GECCO-2004, Part II, volume 3103, pages 630--641. Springer-Verlag, 2004.

[10]

R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published viatexttthttp://lulu.com and freely available attexttthttp://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).

Digital Library

[11]

L. Rokach. Taxonomy for characterizing ensemble methods in classification tasks: A review and annotated bibliography. Computational Statistics & Data Analysis, 53(12):4046--4072, 2009.

Digital Library

[12]

F. Schmiedle, N. Drechsler, D. Grosse, and R. Drechsler. Priorities in multi-objective optimization for genetic programming. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 129--136. Morgan Kaufmann, 2001.

[13]

T. Soule, R. B. Heckendorn, B. Dyre, and R. Lew. Ensemble classifiers: Adaboost and orthogonal evolution of teams. In R. Riolo, T. McConaghy, and E. Vladislavleva, editors, Genetic Programming Theory and Practice VIII, pages 55--69. Springer, 2010.

[14]

L. Spector and J. Klein. Trivial geography in genetic programming. In T. Yu, R. L. Riolo, and B. Worzel, editors, Genetic Programming Theory and Practice III, pages 109--123. Springer, Ann Arbor, 2005.

Digital Library

[15]

L. Vanneschi, M. Tomassini, M. Clergue, and P. Collard. Difficulty of unimodal and multimodal landscapes in genetic programming. In Genetic and Evolutionary Computation -- GECCO-2003, pages 1788--1799. Springer-Verlag, 2003.

Digital Library

Cited By

Powers SPinciroli C(2025)Automatic extraction of symbolic models of collective behaviors with graph neural networks and macro-micro evolutionSwarm Intelligence10.1007/s11721-025-00247-0Online publication date: 7-Feb-2025
https://doi.org/10.1007/s11721-025-00247-0
Ingelse LHidalgo JColmenar JLourenço NFonseca A(2025)A comparison of representations in grammar-guided genetic programming in the context of glucose prediction in people with diabetesGenetic Programming and Evolvable Machines10.1007/s10710-024-09502-526:1Online publication date: 1-Jun-2025
https://dl.acm.org/doi/10.1007/s10710-024-09502-5
Suzue KOfria CLalejini A(2025)Using Lineage Age to Augment Search Space Exploration in Lexicase SelectionGenetic Programming Theory and Practice XXI10.1007/978-981-96-0077-9_20(395-411)Online publication date: 28-Feb-2025
https://doi.org/10.1007/978-981-96-0077-9_20
Show More Cited By

Index Terms

Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report
1. Theory of computation
  1. Design and analysis of 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 ...
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. ...
The Impact of Hyperselection on Lexicase Selection
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

July 2012

1586 pages

ISBN:9781450311786

DOI:10.1145/2330784

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Copyright © 2012 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 ACM 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: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '12

Sponsor:

SIGEVO

GECCO '12: Genetic and Evolutionary Computation Conference

July 7 - 11, 2012

Pennsylvania, Philadelphia, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

120
Total Citations
View Citations
221
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)7

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Powers SPinciroli C(2025)Automatic extraction of symbolic models of collective behaviors with graph neural networks and macro-micro evolutionSwarm Intelligence10.1007/s11721-025-00247-0Online publication date: 7-Feb-2025
https://doi.org/10.1007/s11721-025-00247-0
Ingelse LHidalgo JColmenar JLourenço NFonseca A(2025)A comparison of representations in grammar-guided genetic programming in the context of glucose prediction in people with diabetesGenetic Programming and Evolvable Machines10.1007/s10710-024-09502-526:1Online publication date: 1-Jun-2025
https://dl.acm.org/doi/10.1007/s10710-024-09502-5
Suzue KOfria CLalejini A(2025)Using Lineage Age to Augment Search Space Exploration in Lexicase SelectionGenetic Programming Theory and Practice XXI10.1007/978-981-96-0077-9_20(395-411)Online publication date: 28-Feb-2025
https://doi.org/10.1007/978-981-96-0077-9_20
Fredericks EBobeldyk DMoore J(2025)Crafting Generative Art Through Genetic Improvement: Managing Creative Outputs in Diverse Fitness LandscapesGenetic Programming Theory and Practice XXI10.1007/978-981-96-0077-9_16(321-335)Online publication date: 28-Feb-2025
https://doi.org/10.1007/978-981-96-0077-9_16
Garbus JWillkens TLalejini APollack JLi XHandl J(2024)Accelerating Co-Evolutionary Learning Through Phylogeny-Informed Interaction EstimationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654250(427-430)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654250
Lalejini ASanson MGarbus JMoreno MDolson ELi XHandl J(2024)Runtime phylogenetic analysis enables extreme subsampling for test-based problemsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654208(511-514)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654208
Boldi RBao ABriesch MHelmuth TSobania DSpector LLalejini ALi XHandl J(2024)A Comprehensive Analysis of Down-sampling for Genetic Programming-based Program SynthesisProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654134(487-490)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654134
Boldi RDing LSpector LLi XHandl J(2024)Solving Deceptive Problems Without Explicit Diversity MaintenanceProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654099(171-174)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654099
Reyes Fernández De Bulnes DDe Lima AMurphy AMota Dias DRyan CLi XHandl J(2024)Feature Encapsulation by Stages Using Grammatical EvolutionProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654097(531-534)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654097
Shahbandegan SDolson ELi XHandl J(2024)On the robustness of lexicase selection to contradictory objectivesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654215(594-602)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654215
Show More Cited By

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.

Figures

Tables

Media

View Table of Conten