論文の概要: Improving probability selecting based weights for Satisfiability Problem
- arxiv url: http://arxiv.org/abs/2007.15185v1
- Date: Thu, 30 Jul 2020 02:23:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-05 14:07:47.691148
- Title: Improving probability selecting based weights for Satisfiability Problem
- Title（参考訳）: 満足度問題に対する確率選択に基づく重み付けの改善
- Authors: Huimin Fu, Yang Xu, Jun Liu, Guanfeng Wu, Sutcliffe Geoff
- Abstract要約: ランダム k-SAT と HRS に対して,SelectNTS という新しい SLS アルゴリズムを提案する。
我々のアルゴリズムは最先端のランダムSATアルゴリズムより優れており、SelectNTSはランダムk-SATとHRSの両方を効果的に解くことができる。
- 参考スコア（独自算出の注目度）: 6.59413630027528
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Boolean Satisfiability problem (SAT) is important on artificial
intelligence community and the impact of its solving on complex problems.
Recently, great breakthroughs have been made respectively on stochastic local
search (SLS) algorithms for uniform random k-SAT resulting in several
state-of-the-art SLS algorithms Score2SAT, YalSAT, ProbSAT, CScoreSAT and on a
hybrid algorithm for hard random SAT (HRS) resulting in one state-of-the-art
hybrid algorithm SparrowToRiss. However, there is no an algorithm which can
effectively solve both uniform random k-SAT and HRS. In this paper, we present
a new SLS algorithm named SelectNTS for uniform random k-SAT and HRS. SelectNTS
is an improved probability selecting based local search algorithm for SAT
problem. The core of SelectNTS relies on new clause and variable selection
heuristics. The new clause selection heuristic uses a new clause weighting
scheme and a biased random walk. The new variable selection heuristic uses a
probability selecting strategy with the variation of CC strategy based on a new
variable weighting scheme. Extensive experimental results on the well-known
random benchmarks instances from the SAT Competitions in 2017 and 2018, and on
randomly generated problems, show that our algorithm outperforms
state-of-the-art random SAT algorithms, and our SelectNTS can effectively solve
both uniform random k-SAT and HRS.
- Abstract（参考訳）: ブール満足度問題(SAT)は、人工知能コミュニティと、その解決が複雑な問題に与える影響において重要である。
近年,一様ランダム k-SAT に対する確率的局所探索 (SLS) アルゴリズム,複数の最先端 SLS アルゴリズム, Score2SAT, YalSAT, ProbSAT, CScoreSAT および1つの最先端ハイブリッドアルゴリズム, SparrowToRiss に対して,それぞれ大きなブレークスルーがなされている。
しかし、一様ランダム k-SAT と HRS の両方を効果的に解くアルゴリズムは存在しない。
本稿では,一様ランダム k-SAT と HRS に対して,SelectNTS という新しいSLSアルゴリズムを提案する。
SelectNTSはSAT問題に対する確率選択に基づく局所探索アルゴリズムの改良である。
SelectNTSのコアは、新しい節と変数選択ヒューリスティックに依存している。
新しい節選択ヒューリスティックは、新しい節重み付けスキームとバイアス付きランダムウォークを使用する。
新しい変数選択ヒューリスティックは、新しい変数重み付けスキームに基づいたcc戦略の変動を伴う確率選択戦略を用いる。
2017年と2018年のSATコンペティションでよく知られたランダムベンチマークのインスタンスとランダムに発生する問題に対する大規模な実験結果から、我々のアルゴリズムは最先端のランダムSATアルゴリズムよりも優れており、SelectNTSはランダムk-SATとHRSの両方を効果的に解くことができることを示した。
関連論文リスト
- Resource-Constrained Heuristic for Max-SAT [0.848762374187855]
より大規模な問題をより小さなサブコンポーネントに繰り返し分解する,Max-SATのインスタンスに対するリソース制約を提案する。
本研究では,所定のSATインスタンスの構造を利用するグラフベースの新しい手法を含む,変数選択手法の集合を分析する。
我々は,Max-SAT評価ベンチマークを用いて,ランダムに生成されたMax-SATインスタンスと実世界の実例について実験を行った。
論文 参考訳（メタデータ） (2024-10-11T18:20:08Z) - General Method for Solving Four Types of SAT Problems [12.28597116379225]
既存の方法は、様々なタイプのブール適合性問題(SAT)に対して様々なアルゴリズムを提供する。
本研究では,整数計画法と強化学習法(RL)に基づく統合フレームワークDCSATを提案する。
論文 参考訳（メタデータ） (2023-12-27T06:09:48Z) - Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
分解硬度(d硬度)の概念を導入する。
d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
論文 参考訳（メタデータ） (2023-12-16T12:44:36Z) - HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。
HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
論文 参考訳（メタデータ） (2022-10-31T14:06:11Z) - 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) - DeepSAT: An EDA-Driven Learning Framework for SAT [9.111341161918375]
We present DeepSAT, a novel-to-end learning framework for the Boolean satisfiability (SAT) problem。
DeepSATは最先端の学習ベースSATソリューションに対して,大幅な精度向上を実現している。
論文 参考訳（メタデータ） (2022-05-27T03:20:42Z) - Transformer-based Machine Learning for Fast SAT Solvers and Logic
Synthesis [63.53283025435107]
CNFベースのSATとMaxSATは論理合成と検証システムの中心である。
そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
論文 参考訳（メタデータ） (2021-07-15T04:47:35Z) - diff-SAT -- A Software for Sampling and Probabilistic Reasoning for SAT
and Answer Set Programming [0.0]
diff-SATは正規解と確率的節、事実、ルールを使用する能力を組み合わせる。
サンプリングプロセスは、ユーザ定義の微分可能目的関数を最小化する。
論文 参考訳（メタデータ） (2021-01-03T09:04:31Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z) - NLocalSAT: Boosting Local Search with Solution Prediction [36.69915361918781]
SAT問題の解決に有効な方法は局所探索 (SLS) である。
この方法はランダムな方法で割り振られ、SLSソルバの有効性に影響を与える。
NLocalSATは、SLSとソリューション予測モデルを組み合わせることで、ニューラルネットワークによる初期化割り当てを変更することで、SLSを向上する。
NLocalSATのソルバは元のSLSソルバよりも27% 62%改善した。
論文 参考訳（メタデータ） (2020-01-26T04:22:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。