Calculating lexicase selection probabilities is NP-Hard

• URL: http://arxiv.org/abs/2301.06724v2
• Date: Sat, 22 Apr 2023 22:16:41 GMT
• Title: Calculating lexicase selection probabilities is NP-Hard
• Authors: Emily Dolson
• Abstract summary: I prove that this problem, which I name lex-prob, is NP-Hard. I achieve this proof by reducing SAT, a well-known NP-Complete problem, to lex-prob in time.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Calculating the probability of an individual solution being selected under lexicase selection is an important problem in attempts to develop a deeper theoretical understanding of lexicase selection, a state-of-the art parent selection algorithm in evolutionary computation. Discovering a fast solution to this problem would also have implications for efforts to develop practical improvements to lexicase selection. Here, I prove that this problem, which I name lex-prob, is NP-Hard. I achieve this proof by reducing SAT, a well-known NP-Complete problem, to lex-prob in polynomial time. This reduction involves an intermediate step in which a popular variant of lexicase selection, epsilon-lexicase selection, is reduced to standard lexicase selection. This proof has important practical implications for anyone needing a fast way of calculating the probabilities of individual solutions being selected under lexicase selection. Doing so in polynomial time would be incredibly challenging, if not all-together impossible. Thus, finding approximation algorithms or practical optimizations for speeding up the brute-force solution is likely more worthwhile. This result also has deeper theoretical implications about the relationship between epsilon-lexicase selection and lexicase selection and the relationship between lex-prob and other NP-Hard problems.

Related papers

• On the Robustness of Lexicase Selection to Contradictory Objectives [0.9208007322096533]
  We study lexicase and epsilon-lexicase selection's performance on contradictory objectives. We find that lexicase and epsilon-lexicase selection each have a region of parameter space where they are incapable of optimizing contradictory objectives. We propose theoretically-backed guidelines for parameter choice.
  arXiv  Detail & Related papers  (2024-03-11T15:23:35Z)
• DALex: Lexicase-like Selection via Diverse Aggregation [6.394522608656896]
  We show that DALex (for Diversely Aggregated Lexicase) achieves significant speedups over lexicase selection and its relaxed variants. Results on program synthesis, deep learning, symbolic regression, and learning systems demonstrate that DALex achieves significant speedups over lexicase selection and its relaxed variants.
  arXiv  Detail & Related papers  (2024-01-23T01:20:15Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• Probabilistic Lexicase Selection [6.177959045971966]
  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.
  arXiv  Detail & Related papers  (2023-05-19T13:57:04Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  We show that the hardness of SAT encodings for LEC instances can be estimated textitw.r.t some SAT partitioning. The paper proposes several methods for constructing partitionings, which, when used in practice, allow one to estimate the hardness of SAT encodings for LEC with good accuracy.
  arXiv  Detail & Related papers  (2022-10-04T09:19:13Z)
• Leximax Approximations and Representative Cohort Selection [10.55182802721649]
  Finding a representative cohort from a broad pool of candidates is a goal that arises in many contexts. Finding a leximax solution can be highly dependent on small variations in the utility of certain groups. We show that finding an integer solution to leximax cohort selection with linear utilities is NP-Hard.
  arXiv  Detail & Related papers  (2022-05-02T18:43:25Z)
• Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection [0.0]
  We show that our proposed algorithms can find a locally optimal solution in near linear time. Our algorithms require neither positive nor integer elements in the input set, hence, they are more widely applicable.
  arXiv  Detail & Related papers  (2021-09-10T11:53:34Z)
• An Exploration of Exploration: Measuring the ability of lexicase selection to find obscure pathways to optimality [62.997667081978825]
  We introduce an "exploration diagnostic" that diagnoses a selection scheme's capacity for search space exploration. We verify that lexicase selection out-explores tournament selection. We find that relaxing lexicase's elitism with epsilon lexicase can further improve exploration.
  arXiv  Detail & Related papers  (2021-07-20T20:43:06Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

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.