論文の概要: Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction

• arxiv url: http://arxiv.org/abs/2502.15794v1
• Date: Tue, 18 Feb 2025 16:51:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:59:24.108441
• Title: Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
• Title（参考訳）: 制約充足のための反復解法改善剤としての自己監督型変圧器
• Authors: Yudong W. Xu, Wenhao Li, Scott Sanner, Elias B. Khalil,
• Abstract要約: 制約満足度問題(CSP)のためのトランスフォーマーベースのフレームワークを提案する。 CSPは多くのアプリケーションで利用されており、機械学習によるソリューションの高速化は幅広い関心を集めている。 本稿では,Transformerをソリューションリファインダとして活用する自己教師型フレームワークであるConsFormerを提案する。
• 参考スコア（独自算出の注目度）: 44.67050228129961
• License:
• Abstract: We present a Transformer-based framework for Constraint Satisfaction Problems (CSPs). CSPs find use in many applications and thus accelerating their solution with machine learning is of wide interest. Most existing approaches rely on supervised learning from feasible solutions or reinforcement learning, paradigms that require either feasible solutions to these NP-Complete CSPs or large training budgets and a complex expert-designed reward signal. To address these challenges, we propose ConsFormer, a self-supervised framework that leverages a Transformer as a solution refiner. ConsFormer constructs a solution to a CSP iteratively in a process that mimics local search. Instead of using feasible solutions as labeled data, we devise differentiable approximations to the discrete constraints of a CSP to guide model training. Our model is trained to improve random assignments for a single step but is deployed iteratively at test time, circumventing the bottlenecks of supervised and reinforcement learning. Our method can tackle out-of-distribution CSPs simply through additional iterations.
• Abstract（参考訳）: 本稿では,制約満足度問題(CSP)のためのトランスフォーマーベースのフレームワークを提案する。 CSPは多くのアプリケーションで利用されており、機械学習によるソリューションの高速化は幅広い関心を集めている。 既存のアプローチの多くは、実現可能なソリューションや強化学習からの教師あり学習、NP-Complete CSPへの実現可能なソリューション、あるいは大規模なトレーニング予算、複雑な専門家が設計した報酬信号のいずれかを必要とするパラダイムに依存している。 これらの課題に対処するために,Transformerをソリューションリファインダとして活用する自己教師型フレームワークであるConsFormerを提案する。 ConsFormerは、ローカル検索を模倣するプロセスにおいて、CSPに対するソリューションを反復的に構築する。 ラベル付きデータとして実現可能なソリューションを使用する代わりに、モデルトレーニングをガイドするために、CSPの離散制約に対する微分可能な近似を考案する。 本モデルは1ステップのランダムな割り当てを改善するために訓練されているが、テスト時に反復的にデプロイされ、教師付きおよび強化学習のボトルネックを回避する。 提案手法は, 追加イテレーションにより, 分配不能なCSPに対処できる。

関連論文リスト

• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization [15.842155380912002]
  本研究は,ニューラル最適化の大規模一般化のための新しいインスタンス・コンディション適応モデル(ICAM)を提案する。 特に,NCOモデルのための強力なインスタンス条件付きルーティング適応モジュールを設計する。 我々は,ラベル付き最適解を使わずに,モデルがクロススケールな特徴を学習することのできる,効率的な3段階強化学習ベーストレーニング手法を開発した。
  論文  参考訳（メタデータ） (2024-05-03T08:00:19Z)
• Self-Labeling the Job Shop Scheduling Problem [15.723699332053558]
  生成モデルは複数の解をサンプリングし、問題の目的に応じて最良の解を擬似ラベルとして使用することにより訓練可能であることを示す。 旅行セールスマン問題に適用することで,様々なパラメータに対するSLIMのロバスト性とその一般性を証明する。
  論文  参考訳（メタデータ） (2024-01-22T11:08:36Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。 最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
  論文  参考訳（メタデータ） (2021-02-14T18:05:42Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  トラベリングセールスマン問題(TSP)は古典的な最適化問題である。 ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。 本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2020-10-23T07:37:16Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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