Data

Tools

Indexes

Applications

Experiments

Open Source Science

lex-prob-is-np-hard

Code and materials for the paper "Calculating Lexicase Selection Probabilities is NP-Hard

https://github.com/emilydolson/lex-prob-is-np-hard

Science Score: 67.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ✓
    DOI references
    Found 1 DOI reference(s) in README
  • ✓
    Academic publication links
    Links to: arxiv.org, acm.org, zenodo.org
  • ○
    Committers with academic emails
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (8.3%) to scientific vocabulary
Last synced: 6 months ago · JSON representation ·

Repository

Code and materials for the paper "Calculating Lexicase Selection Probabilities is NP-Hard

Basic Info
  • Host: GitHub
  • Owner: emilydolson
  • Language: TeX
  • Default Branch: main
  • Size: 4.53 MB
Statistics
  • Stars: 1
  • Watchers: 2
  • Forks: 0
  • Open Issues: 0
  • Releases: 2
Created almost 3 years ago · Last pushed over 2 years ago
Metadata Files
Readme Citation

README.md

Calculating Lexicase Selection Probabilities is NP-Hard

preprint paper Code Code DOI

This repository contains scripts that implement the reductions (from Satisfiability to epsilon-lexicase and from epsilon-lexicase to lexicase) used in the paper "Calculating Lexicase Selection Probabilities is NP-Hard" to prove that these problems are all NP-Hard. Brute-force code to calculate lexicase and epsilon lexicase selection probabilities is in the EC Ecology Toolbox.

Example reduction from Satisfiability to Epsilon Lexicase Selection

Abstract

Lexicase selection is a state-of-the-art parent selection algorithm in evolutionary computation. Recently, there have been efforts to develop stronger theoretical analyses of lexicase selection. Many of these analyses hinge on calculating the probability of an individual solution being selected under lexicase selection. Discovering a fast way to perform this calculation would be very helpful to the development of theory regarding lexicase selection, and would also have implications for efforts to develop practical improvements to lexicase selection. Here, I prove that this problem of calculating selection probabilities under lexicase selection, 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 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. Finally, I present a highly-optimized brute-force algorithm (and accompanying open-source implementation) for performing these calculations. While the worst-case time complexity of this solution is, of course, exponential it is capable of solving realistically-sized instances of the problem in approximately one second.

Repository Contents

  • paper: contains all latex code for the paper
  • scripts: contains relevant python scripts
    • benchmark.py: For benchmarking optimized brute force algorithm
    • reducesatto_eps.py: Implements reduction from SAT to epsilon lexicase selection
    • reduceepsto_lex.py: Implements reduction fo epsilon lexicase selection to lexicase selection.

Author

Owner

  • Name: Emily Dolson
  • Login: emilydolson
  • Kind: user
  • Company: @DolsonLab, Michigan State University

Assistant professor studying evolution in cancer and digital organisms and building tools to do so. Views my own.

Citation (CITATION.cff) 

cff-version: 1.1.0
authors:
  - family-names: Dolson
    given-names: Emily
    orcid: https://orcid.org/0000-0001-8616-4898
title: Code and supporting information for "Calculating Lexicase Selection Probabilities is NP-Hard"
version: submitted
date-released: 2023-04-20
message: "If you use this software, please cite both the article from preferred-citation and the software itself."
preferred-citation:
  authors:
    - family-names: Dolson
      given-names: Emily
  title: "Calculating Lexicase Selection Probabilities is NP-Hard"
  type: article
  doi: 10.1145/3583131.3590356
  conference: Genetic and Evolutionary Computation Conference (GECCO ’23)
  year: 2023
  publisher: ACM

GitHub Events

Total
Last Year

Committers

Last synced: 7 months ago

All Time
  • Total Commits: 33
  • Total Committers: 1
  • Avg Commits per committer: 33.0
  • Development Distribution Score (DDS): 0.0
Past Year
  • Commits: 0
  • Committers: 0
  • Avg Commits per committer: 0.0
  • Development Distribution Score (DDS): 0.0
Top Committers
Name Email Commits
Emily Dolson e****n@g****m 33

Issues and Pull Requests

Last synced: 7 months ago

All Time
  • Total issues: 0
  • Total pull requests: 0
  • Average time to close issues: N/A
  • Average time to close pull requests: N/A
  • Total issue authors: 0
  • Total pull request authors: 0
  • Average comments per issue: 0
  • Average comments per pull request: 0
  • Merged pull requests: 0
  • Bot issues: 0
  • Bot pull requests: 0
Past Year
  • Issues: 0
  • Pull requests: 0
  • Average time to close issues: N/A
  • Average time to close pull requests: N/A
  • Issue authors: 0
  • Pull request authors: 0
  • Average comments per issue: 0
  • Average comments per pull request: 0
  • Merged pull requests: 0
  • Bot issues: 0
  • Bot pull requests: 0
View more stats
Top Authors
Issue Authors
Pull Request Authors
Top Labels
Issue Labels
Pull Request Labels

Dependencies

.github/workflows/python-app.yml actions
  • actions/checkout v3 composite
  • actions/setup-python v3 composite
requirements.txt pypi
  • ec-ecology-toolbox *
  • python-sat *