論文の概要: Incorporating Multi-armed Bandit with Local Search for MaxSAT

• arxiv url: http://arxiv.org/abs/2211.16011v1
• Date: Tue, 29 Nov 2022 08:19:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-30 16:13:28.028487
• Title: Incorporating Multi-armed Bandit with Local Search for MaxSAT
• Title（参考訳）: MaxSATの局所探索によるマルチアームバンドの導入
• Authors: Jiongzhi Zheng and Kun He and Jianrong Zhou and Yan Jin and Chu-Min Li and Felip Many\`a
• Abstract要約: MaxSAT問題の2つの一般化: partial MaxSAT (PMS) と Weighted PMS (WPMS) そこで本稿では,BandHSと呼ばれる局所探索アルゴリズムを提案する。 これら2つの帯域は、実現不可能な解空間と実現不可能な解空間の両方において、アルゴリズムの探索能力を向上させることができる。
• 参考スコア（独自算出の注目度）: 16.371916145216737
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Partial MaxSAT (PMS) and Weighted PMS (WPMS) are two practical generalizations of the MaxSAT problem. In this paper, we propose a local search algorithm for these problems, called BandHS, which applies two multi-armed bandits to guide the search directions when escaping local optima. One bandit is combined with all the soft clauses to help the algorithm select to satisfy appropriate soft clauses, and the other bandit with all the literals in hard clauses to help the algorithm select appropriate literals to satisfy the hard clauses. These two bandits can improve the algorithm's search ability in both feasible and infeasible solution spaces. We further propose an initialization method for (W)PMS that prioritizes both unit and binary clauses when producing the initial solutions. Extensive experiments demonstrate the excellent performance and generalization capability of our proposed methods, that greatly boost the state-of-the-art local search algorithm, SATLike3.0, and the state-of-the-art SAT-based incomplete solver, NuWLS-c.
• Abstract（参考訳）: 部分マックスSAT (PMS) と重み付きPSM (WPMS) は、マックスSAT問題の実用的な一般化である。 本稿では,この問題に対する局所探索アルゴリズムであるbandhsを提案する。これは2つの多腕バンディットを適用し,局所オプティマからの脱出時の探索方向を導くものである。 1つのbanditは、すべてのsoft節と組み合わせて、アルゴリズムが適切なsoft節を満たすように支援し、もう1つのbanditは、ハード節のすべてのリテラルを満たし、アルゴリズムがハード節を満たす適切なリテラルを選択するのに役立つ。 これら2つの帯域は、実現不可能かつ実現不可能な解空間において、アルゴリズムの探索能力を向上させることができる。 さらに,初期解を生成する際に,単位節とバイナリ節の両方を優先する(w)pmsの初期化手法を提案する。 提案手法は,最先端の局所探索アルゴリズムSATLike3.0と,最先端のSATベース不完全解法NuWLS-cを大幅に向上させるものである。

関連論文リスト

• Rethinking the Soft Conflict Pseudo Boolean Constraint on MaxSAT Local Search Solvers [20.866863965121013]
  MaxSATは、有名なNP完全満足度問題(SAT)の最適化版である。 そこで我々は,SPB-MaxSATと呼ばれる局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-19T09:59:02Z)
• General Method for Solving Four Types of SAT Problems [12.28597116379225]
  既存の方法は、様々なタイプのブール適合性問題(SAT)に対して様々なアルゴリズムを提供する。 本研究では,整数計画法と強化学習法(RL)に基づく統合フレームワークDCSATを提案する。
  論文  参考訳（メタデータ） (2023-12-27T06:09:48Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving [45.21499915442282]
  本稿では,ハイブリッド制約を用いた一般化MaxSAT問題の解法について,新しい動的プログラミング手法を提案する。 我々の汎用フレームワークは、MaxSAT、Min-MaxSAT、MinSATといったCNF-MaxSATの多くの一般化をハイブリッド制約で認めている。 実験の結果、DPMSは様々な手法に基づく他のアルゴリズムがすべて失敗し、特定の問題を迅速に解決できることがわかった。
  論文  参考訳（メタデータ） (2022-05-08T00:31:53Z)
• BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit [16.371916145216737]
  そこで我々はBandMaxSATという局所探索アルゴリズムを提案する。 広汎な実験により、BandMaxSATは最先端(W)PMS局所探索アルゴリズムSATLike3.0を大きく上回っていることが示された。 その結果、BandMaxSAT-cはSATLike-c、Loandra、TT-Open-WBO-Incなど、最先端の完全(W)PMSソルバよりも優れている。
  論文  参考訳（メタデータ） (2022-01-14T16:32:39Z)
• Farsighted Probabilistic Sampling based Local Search for (Weighted) Partial MaxSAT [5.529868797285073]
  部分マックスSAT (PMS) と重み付き部分マックスSAT (WPMS) は、マックスSATの典型的な問題に対する実用的な一般化である。 本稿では,この2つの問題を解くために,FPSと呼ばれる効率的な遠視的確率的サンプリングに基づく局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-08-23T07:41:56Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Incomplete MaxSAT Approaches for Combinatorial Testing [0.0]
  本稿では,最小長の制約付き混合被覆アレイを構築するためのSAT(Satifiability)に基づくアプローチを提案する。 この問題はシステム障害検出のためのコンビネータテストの中心である。
  論文  参考訳（メタデータ） (2021-05-26T14:00:56Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Double Explore-then-Commit: Asymptotic Optimality and Beyond [101.77632893858063]
  ガウス級報酬を用いたマルチアームバンディット問題について検討する。 本研究では,探索-then-commit (ETC) アルゴリズムの変種により,マルチアームバンディット問題に対する最適性が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-21T08:07:56Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。