Calculating lexicase selection probabilities is NP-Hard
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Probabilistic Lexicase Selection
Lexicase selection is a widely used parent selection algorithm in genetic programming, known for its success in various task domains such as program synthesis, symbolic regression, and machine learning. Due to its non-pa…
Program SynthesisregressionSymbolic RegressionA probabilistic and multi-objective analysis of lexicase selection and epsilon-lexicase selection
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 selec…
Program SynthesisregressionSymbolic RegressionAn Exploration of Exploration: Measuring the ability of lexicase selection to find obscure pathways to optimality
Parent selection algorithms (selection schemes) steer populations through a problem's search space, often trading off between exploitation and exploration. Understanding how selection schemes affect exploitation and expl…
BenchmarkingDiagnosticDown-Sampled Epsilon-Lexicase Selection for Real-World Symbolic Regression Problems
Epsilon-lexicase selection is a parent selection method in genetic programming that has been successfully applied to symbolic regression problems. Recently, the combination of random subsampling with lexicase selection s…
Program SynthesisregressionSymbolic RegressionComparing and Combining Lexicase Selection and Novelty Search
Lexicase selection and novelty search, two parent selection methods used in evolutionary computation, emphasize exploring widely in the search space more than traditional methods such as tournament selection. However, le…
DiversityProgram Synthesis