Was Tournament Selection All We Ever Needed? A Critical Reflection on Lexicase Selection

• URL: http://arxiv.org/abs/2502.18093v1
• Date: Tue, 25 Feb 2025 11:01:11 GMT
• Title: Was Tournament Selection All We Ever Needed? A Critical Reflection on Lexicase Selection
• Authors: Alina Geiger, Martin Briesch, Dominik Sobania, Franz Rothlauf,
• Abstract summary: We run experiments comparing epsilon-lexicase and tournament selection with different down-sampling techniques.<n>We find that down-sampling improves generalization and performance even when compared over the same number of generations.<n>We observe that population diversity increases for tournament selection when combined with down-sampling.
• Score: 0.7874708385247353
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The success of lexicase selection has led to various extensions, including its combination with down-sampling, which further increased performance. However, recent work found that down-sampling also leads to significant improvements in the performance of tournament selection. This raises the question of whether tournament selection combined with down-sampling is the better choice, given its faster running times. To address this question, we run a set of experiments comparing epsilon-lexicase and tournament selection with different down-sampling techniques on synthetic problems of varying noise levels and problem sizes as well as real-world symbolic regression problems. Overall, we find that down-sampling improves generalization and performance even when compared over the same number of generations. This means that down-sampling is beneficial even with way fewer fitness evaluations. Additionally, down-sampling successfully reduces code growth. We observe that population diversity increases for tournament selection when combined with down-sampling. Further, we find that tournament selection and epsilon-lexicase selection with down-sampling perform similar, while tournament selection is significantly faster. We conclude that tournament selection should be further analyzed and improved in future work instead of only focusing on the improvement of lexicase variants.

Related papers

• Lexicase-based Selection Methods with Down-sampling for Symbolic Regression Problems: Overview and Benchmark [0.8602553195689513]
  This paper evaluates random as well as informed down-sampling in combination with the relevant lexicase-based selection methods on a wide range of symbolic regression problems. We find that for a given evaluation budget, epsilon-lexicase selection in combination with random or informed down-sampling outperforms all other methods.
  arXiv  Detail & Related papers  (2024-07-31T14:26:22Z)
• Untangling the Effects of Down-Sampling and Selection in Genetic Programming [40.05141985769286]
  Genetic programming systems often use large training sets to evaluate the quality of candidate solutions for selection. Recent studies have shown that both random and informed down-sampling can substantially improve problem-solving success.
  arXiv  Detail & Related papers  (2023-04-14T12:21:19Z)
• A Static Analysis of Informed Down-Samples [62.997667081978825]
  We study recorded populations from the first generation of genetic programming runs, as well as entirely synthetic populations. We show that both forms of down-sampling cause greater test coverage loss than standard lexicase selection with no down-sampling.
  arXiv  Detail & Related papers  (2023-04-04T17:34:48Z)
• Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving [40.683810697551166]
  Genetic Programming (GP) often uses large training sets and requires all individuals to be evaluated on all training cases during selection. Random down-sampled lexicase selection evaluates individuals on only a random subset of the training cases allowing for more individuals to be explored with the same amount of program executions. In Informed Down-Sampled Lexicase Selection, we use population statistics to build down-samples that contain more distinct and therefore informative training cases.
  arXiv  Detail & Related papers  (2023-01-04T08:47:18Z)
• The Environmental Discontinuity Hypothesis for Down-Sampled Lexicase Selection [0.0]
  Down-sampling has proved effective in genetic programming (GP) runs that utilize the lexicase parent selection technique. We hypothesize that the random sampling that is performed every generation causes discontinuities that result in the population being unable to adapt to the shifting environment. We find that forcing incremental environmental change is not significantly better for evolving solutions to program synthesis problems than simple random down-sampling.
  arXiv  Detail & Related papers  (2022-05-31T16:21:14Z)
• UNICON: Combating Label Noise Through Uniform Selection and Contrastive Learning [89.56465237941013]
  We propose UNICON, a simple yet effective sample selection method which is robust to high label noise. We obtain an 11.4% improvement over the current state-of-the-art on CIFAR100 dataset with a 90% noise rate.
  arXiv  Detail & Related papers  (2022-03-28T07:36:36Z)
• Saliency Grafting: Innocuous Attribution-Guided Mixup with Calibrated Label Mixing [104.630875328668]
  Mixup scheme suggests mixing a pair of samples to create an augmented training sample. We present a novel, yet simple Mixup-variant that captures the best of both worlds.
  arXiv  Detail & Related papers  (2021-12-16T11:27:48Z)
• Rethinking Sampling Strategies for Unsupervised Person Re-identification [59.47536050785886]
  We analyze the reasons for the performance differences between various sampling strategies under the same framework and loss function. Group sampling is proposed, which gathers samples from the same class into groups. Experiments on Market-1501, DukeMTMC-reID and MSMT17 show that group sampling achieves performance comparable to state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-07-07T05:39:58Z)
• Problem-solving benefits of down-sampled lexicase selection [0.20305676256390928]
  We show 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. The reasons that down-sampling helps, however, are not yet fully understood.
  arXiv  Detail & Related papers  (2021-06-10T23:42:09Z)
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity [83.81297078039836]
  We consider incentivized exploration: a version of multi-armed bandits where the choice of arms is controlled by self-interested agents. We focus on the price of incentives: the loss in performance, broadly construed, incurred for the sake of incentive-compatibility.
  arXiv  Detail & Related papers  (2020-02-03T04:58:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.