論文の概要: Farsighted Probabilistic Sampling based Local Search for (Weighted) Partial MaxSAT

• arxiv url: http://arxiv.org/abs/2108.09988v1
• Date: Mon, 23 Aug 2021 07:41:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-24 20:58:34.128714
• Title: Farsighted Probabilistic Sampling based Local Search for (Weighted) Partial MaxSAT
• Title（参考訳）: farsighted probabilistic sampling based local search for (weighted) partial maxsat (英語)
• Authors: Jiongzhi Zheng and Jianrong Zhou and Kun He
• Abstract要約: 部分マックスSAT (PMS) と重み付き部分マックスSAT (WPMS) は、マックスSATの典型的な問題に対する実用的な一般化である。 本稿では,この2つの問題を解くために,FPSと呼ばれる効率的な遠視的確率的サンプリングに基づく局所探索アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 5.529868797285073
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Partial MaxSAT (PMS) and Weighted Partial MaxSAT (WPMS) are both practical generalizations to the typical combinatorial problem of MaxSAT. In this work, we propose an effective farsighted probabilistic sampling based local search algorithm called FPS for solving these two problems, denoted as (W)PMS. The FPS algorithm replaces the mechanism of flipping a single variable per iteration step, that is widely used in existing (W)PMS local search algorithms, with the proposed farsighted local search strategy, and provides higher-quality local optimal solutions. The farsighted strategy employs the probabilistic sampling technique that allows the algorithm to look-ahead widely and efficiently. In this way, FPS can provide more and better search directions and improve the performance without reducing the efficiency. Extensive experiments on all the benchmarks of (W)PMS problems from the incomplete track of recent four years of MaxSAT Evaluations demonstrate that our method significantly outperforms SATLike3.0, the state-of-the-art local search algorithm, for solving both the PMS and WPMS problems. We furthermore do comparison with the extended solver of SATLike, SATLike-c, which is the champion of three categories among the total four (PMS and WPMS categories, each associated with two time limits) of the incomplete track in the recent MaxSAT Evaluation (MSE2021). We replace the local search component in SATLike-c with the proposed farsighted sampling local search approach, and the resulting solver FPS-c also outperforms SATLike-c for solving both the PMS and WPMS problems.
• Abstract（参考訳）: 部分MaxSAT (PMS) と重み付き部分MaxSAT (WPMS) はどちらも、MaxSATの典型的な組合せ問題に対する実用的な一般化である。 本研究では, (w)pms という2つの問題を解くために, fps と呼ばれる遠視的確率的サンプリングに基づく局所探索アルゴリズムを提案する。 fpsアルゴリズムは、既存の(w)pms局所探索アルゴリズムで広く使われている反復ステップ毎に単一の変数を反転するメカニズムを、提案された遠視局所探索戦略に置き換え、高品質な局所最適解を提供する。 遠視戦略は確率的サンプリング技術を用いており、アルゴリズムを広く効率的に見渡すことができる。 これにより、FPSはより優れた探索方向を提供し、効率を低下させることなく性能を向上させることができる。 近年のMaxSAT評価において, (W)PMS問題の全ベンチマークにおいて, PMSとWPMS問題の両方を解くために, 最先端の局所探索アルゴリズムSATLike3.0を著しく上回っていることを示す。 さらに、最近のMaxSAT Evaluation(MSE2021)において、全4つのカテゴリー(PMSとWPMS、それぞれ2つの時間制限を伴う)のうち3つのカテゴリのチャンピオンであるSATLike, SATLike-cの拡張解法との比較を行った。 SATLike-c の局所探索成分を遠距離サンプリングによる局所探索手法に置き換え,結果の FPS-c は PMS と WPMS の両問題を解くために SATLike-c よりも優れている。

関連論文リスト

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• Rethinking the Soft Conflict Pseudo Boolean Constraint on MaxSAT Local Search Solvers [20.866863965121013]
  MaxSATは、有名なNP完全満足度問題(SAT)の最適化版である。 そこで我々は,SPB-MaxSATと呼ばれる局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-19T09:59:02Z)
• Towards Tackling MaxSAT by Combining Nested Monte Carlo with Local Search [10.70006528984961]
  UCTMAXSAT上でのアルゴリズム的バリエーションを2つ紹介する。 まず、Nested Monte Carlo Searchアルゴリズムにインスパイアされた木探索のネストは、ベンチマークのほとんどのインスタンスタイプに有効である。 第二に、SLSの静的フリップ制限を用いることで、理想的な予算はインスタンスサイズに大きく依存し、動的に設定することを提案する。
  論文  参考訳（メタデータ） (2023-02-26T03:37:26Z)
• DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization [10.513103815142731]
  PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。 我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
  論文  参考訳（メタデータ） (2023-01-28T17:03:56Z)
• Incorporating Multi-armed Bandit with Local Search for MaxSAT [16.371916145216737]
  MaxSAT問題の2つの一般化: partial MaxSAT (PMS) と Weighted PMS (WPMS) そこで本稿では,BandHSと呼ばれる局所探索アルゴリズムを提案する。 これら2つの帯域は、実現不可能な解空間と実現不可能な解空間の両方において、アルゴリズムの探索能力を向上させることができる。
  論文  参考訳（メタデータ） (2022-11-29T08:19:26Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• 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)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。 その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
  論文  参考訳（メタデータ） (2021-04-09T14:50:59Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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