EUVIMEDEUVIMED entdecken
Open Access

A Probabilistic and Multi-Objective Analysis of Lexicase Selection and ε-Lexicase Selection

William La Cava, Thomas Helmuth, Lee Spector, Jason H Moore

Evolutionary Computation · 2019-09 · 27 (3) · 377-402

DOI: 10.1162/evco_a_00224 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, 2019-09. Verfasst von William La Cava und 3 weiteren Autor:innen. Beteiligte Einrichtung: Institute for Bioinformatics, University of Pennsylvania, Philadelphia, PA, 19104, USA lacava@upenn.edu. Hauptthemen laut MEDLINE: Models, Statistical. Die Arbeit wurde bisher 89-mal zitiert (Crossref) und nennt 50 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar. Gefördert von: NIEHS NIH HHS, NLM NIH HHS, NIAID NIH HHS.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Lexicase selection is a parent selection method that considers training cases individually, rather than in aggregate, when performing parent selection. Whereas previous work has demonstrated the ability of lexicase selection to solve difficult problems in program synthesis and symbolic regression, the central goal of this article is to develop the theoretical underpinnings that explain its performance. To this end, we derive an analytical formula that gives the expected probabilities of selection under lexicase selection, given a population and its behavior. In addition, we expand upon the relation of lexicase selection to many-objective optimization methods to describe the behavior of lexicase selection, which is to select individuals on the boundaries of Pareto fronts in high-dimensional space. We show analytically why lexicase selection performs more poorly for certain sizes of population and training cases, and show why it has been shown to perform more poorly in continuous error spaces. To address this last concern, we propose new variants of [Formula: see text]-lexicase selection, a method that modifies the pass condition in lexicase selection to allow near-elite individuals to pass cases, thereby improving selection performance with continuous errors. We show that [Formula: see text]-lexicase outperforms several diversity–maintenance strategies on a number of real-world and synthetic regression problems.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

Models, StatisticalAlgorithmsComputational BiologyHumansLinguisticsRegression AnalysisSearch EngineSemantics

Stichwörter der Autor:innen

Selectiongenetic programmingmulti-objective optimizationsymbolic regression.

Autor:innen und Institutionen

  • Institute for Bioinformatics, University of Pennsylvania, Philadelphia, PA, 19104, USA lacava@upenn.edu.
  • Department of Computer Science, Hamilton College, Clinton, NY, 13323, USA thelmuth@hamilton.edu.
  • School of Cognitive Science, Hampshire College, Amherst, MA, 01002, USA lspector@hampshire.edu.
  • Institute for Bioinformatics, University of Pennsylvania, Philadelphia, PA, 19104, USA jhmoore@upenn.edu.

Förderung

  • NIEHS NIH HHS
  • NLM NIH HHS
  • NIAID NIH HHS

Zitieren

APA

La Cava, W., Helmuth, T., Spector, L., & Moore, J. H. (2019). A Probabilistic and Multi-Objective Analysis of Lexicase Selection and ε-Lexicase Selection. Evolutionary Computation, 27(3), 377-402. https://doi.org/10.1162/evco_a_00224

Vancouver

La Cava W, Helmuth T, Spector L, Moore JH. A Probabilistic and Multi-Objective Analysis of Lexicase Selection and ε-Lexicase Selection. Evolutionary Computation. 2019;27(3):377-402. doi:10.1162/evco_a_00224

BibTeX
@article{LaCava2019,
  author = {La Cava, William and Helmuth, Thomas and Spector, Lee and Moore, Jason H},
  title = {A Probabilistic and Multi-Objective Analysis of Lexicase Selection and ε-Lexicase Selection},
  journal = {Evolutionary Computation},
  year = {2019},
  volume = {27},
  number = {3},
  pages = {377--402},
  doi = {10.1162/evco_a_00224}
}
Kostenlos starten →