論文の概要: Calculating lexicase selection probabilities is NP-Hard
- arxiv url: http://arxiv.org/abs/2301.06724v1
- Date: Tue, 17 Jan 2023 06:51:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 14:47:02.291058
- Title: Calculating lexicase selection probabilities is NP-Hard
- Title(参考訳): 計算レキシケース選択確率はNP-Hardである
- Authors: Emily Dolson
- Abstract要約: lex-prob というこの問題が NP-Hard であることを示す。
この証明は、よく知られたNP-Complete問題であるSATを、時間内にlex-probに還元することで達成する。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): レキシケース選択下で選択される個々の解の確率を計算することは、進化的計算における最先端の親選択アルゴリズムであるレキシケース選択のより深い理論的理解を開発する上で重要な問題である。
この問題に対する高速な解決策を見つけることは、レキシケース選択の実際的な改善を開発するための努力にも意味がある。
ここでは、lex-probと呼ばれるこの問題がNP-Hardであることを証明する。
この証明は、よく知られたNP-Complete問題であるSATを多項式時間でlex-probに還元することで達成する。
この還元には、一般的なレキシケース選択であるepsilon-lexicase選択を標準レキシケース選択に還元する中間段階が含まれる。
この証明は、レキシケース選択の下で選択される個々の解の確率を計算する高速な計算方法を必要とする人に重要な実践的意味を持つ。
多項式時間で行うことは、完全に不可能ではないとしても、信じられないほど難しい。
したがって、ブルート・フォース・ソリューションを高速化するための近似アルゴリズムや実用的な最適化を見つけることは、おそらく価値がある。
この結果は、epsilon-lexicase selectionとlexicase selectionの関係と、lex-probと他のNP-Hard問題との関係について深い理論的意味を持つ。
関連論文リスト
- On the Robustness of Lexicase Selection to Contradictory Objectives [0.9208007322096533]
矛盾する目的について,レキシケースとエプシロン-レキシケース選択の性能について検討した。
辞書とepsilon-lexicase選択は、それぞれパラメータ空間の領域を持ち、矛盾する目的を最適化することができない。
パラメータ選択のための理論的支援されたガイドラインを提案する。
論文 参考訳(メタデータ) (2024-03-11T15:23:35Z) - DALex: Lexicase-like Selection via Diverse Aggregation [6.394522608656896]
DALex(Diversely Aggregated Lexicase)は,レキシケース選択とその緩和された変種に対して,大幅な高速化を実現することを示す。
プログラム合成, 深層学習, 記号回帰, 学習システムの結果から, DALexは語彙選択とその緩和された変種に対して, 大幅な高速化を実現することが示された。
論文 参考訳(メタデータ) (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]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳(メタデータ) (2023-12-18T18:29:01Z) - Probabilistic Lexicase Selection [6.177959045971966]
本稿では,レキシケード選択の確率分布を効率的に近似する新しい親選択アルゴリズムである確率論的レキシケード選択(プレキシケード選択)を導入する。
提案手法は,セマンティック・アウェア選択法として優れた問題解決能力を示すだけでなく,選択プロセスの確率的表現の利点も示している。
論文 参考訳(メタデータ) (2023-05-19T13:57:04Z) - Estimating the hardness of SAT encodings for Logical Equivalence
Checking of Boolean circuits [58.83758257568434]
LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。
そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
論文 参考訳(メタデータ) (2022-10-04T09:19:13Z) - Leximax Approximations and Representative Cohort Selection [10.55182802721649]
幅広い候補から代表コホートを見つけることは、多くの文脈で発生する目標である。
レキシマックス解を見つけることは、ある群の効用の小さなバリエーションに大きく依存することができる。
線形ユーティリティを用いたレキシマックスコホート選択の整数解を見つけることはNP-Hardであることを示す。
論文 参考訳(メタデータ) (2022-05-02T18:43:25Z) - Efficient Locally Optimal Number Set Partitioning for Scheduling,
Allocation and Fair Selection [0.0]
提案アルゴリズムは, ほぼ線形時間で局所最適解を求めることができることを示す。
我々のアルゴリズムは入力集合に正の要素も整数の要素も必要としないので、より広く適用できる。
論文 参考訳(メタデータ) (2021-09-10T11:53:34Z) - An Exploration of Exploration: Measuring the ability of lexicase
selection to find obscure pathways to optimality [62.997667081978825]
本稿では,探索空間探索のための選択スキームの容量を診断する探索診断手法を提案する。
我々はレキシケースの選択がトーナメントの選択を外見することを確認した。
我々は,レキシケースのエリート性をエプシロンレキシケースで緩和することで,探索をさらに改善できることを見出した。
論文 参考訳(メタデータ) (2021-07-20T20:43:06Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳(メタデータ) (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。