論文の概要: Controlling Continuous Relaxation for Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2309.16965v1
- Date: Fri, 29 Sep 2023 04:23:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-02 15:39:33.581961
- Title: Controlling Continuous Relaxation for Combinatorial Optimization
- Title(参考訳): 組合せ最適化のための連続緩和制御
- Authors: Yuma Ichikawa
- Abstract要約: 本論文は,高密度グラフ上のCO問題の早期学習において,PI-GNNソルバがすべての変数がゼロとなる局所解に閉じ込められることを数値的に示す。
次に、局所解を避けながら、緩和変数の連続性と離散性を制御することで、これらの問題に対処する。
実証的には、PI-GNNソルバが妥当な解を見つけるのに苦労する高密度グラフ上のCO問題や、比較的スパースなグラフ上の問題に対してより良い結果が得られる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent advancements in combinatorial optimization (CO) problems emphasize the
potential of graph neural networks (GNNs). The physics-inspired GNN (PI-GNN)
solver, which finds approximate solutions through unsupervised learning, has
attracted significant attention for large-scale CO problems. Nevertheless,
there has been limited discussion on the performance of the PI-GNN solver for
CO problems on relatively dense graphs where the performance of greedy
algorithms worsens. In addition, since the PI-GNN solver employs a relaxation
strategy, an artificial transformation from the continuous space back to the
original discrete space is necessary after learning, potentially undermining
the robustness of the solutions. This paper numerically demonstrates that the
PI-GNN solver can be trapped in a local solution, where all variables are zero,
in the early stage of learning for CO problems on the dense graphs. Then, we
address these problems by controlling the continuity and discreteness of
relaxed variables while avoiding the local solution: (i) introducing a new
penalty term that controls the continuity and discreteness of the relaxed
variables and eliminates the local solution; (ii) proposing a new continuous
relaxation annealing (CRA) strategy. This new annealing first prioritizes
continuous solutions and intensifies exploration by leveraging the continuity
while avoiding the local solution and then schedules the penalty term for
prioritizing a discrete solution until the relaxed variables are almost
discrete values, which eliminates the need for an artificial transformation
from the continuous to the original discrete space. Empirically, better results
are obtained for CO problems on the dense graphs, where the PI-GNN solver
struggles to find reasonable solutions, and for those on relatively sparse
graphs. Furthermore, the computational time scaling is identical to that of the
PI-GNN solver.
- Abstract(参考訳): 組合せ最適化(CO)問題の最近の進歩は、グラフニューラルネットワーク(GNN)の可能性を強調している。
物理に着想を得た GNN (PI-GNN) ソルバは教師なし学習により近似解を求めるが, 大規模CO問題に注目が集まっている。
それにもかかわらず、比較的高密度なグラフ上でのCO問題に対するPI-GNNソルバの性能に関する限定的な議論がある。
さらに、PI-GNNソルバは緩和戦略を採用しているため、学習後に連続空間から元の離散空間への人工的な変換が必要であり、解の堅牢性を損なう可能性がある。
本論文は,高密度グラフ上のCO問題の早期学習において,PI-GNNソルバがすべての変数がゼロとなる局所解に閉じ込められることを数値的に示す。
次に, 局所解を回避しつつ, 緩和変数の連続性と離散性を制御することにより, これらの問題に対処する。
(i)緩和変数の連続性と離散性を制御し、局所解を排除する新たなペナルティ用語を導入すること。
(II)新しい連続緩和焼鈍(CRA)戦略を提案する。
この新たなアニールは、まず連続解を優先し、局所解を避けながら連続性を活用して探索を強化し、その後、緩和された変数がほぼ離散値になるまで離散解を優先順位付けするためのペナルティ項をスケジュールし、連続から元の離散空間への人工的な変換の必要性を排除した。
実証的には、PI-GNNソルバが妥当な解を見つけるのに苦労するグラフ上のCO問題や比較的スパースなグラフ上の問題に対してより良い結果が得られる。
さらに、計算時間のスケーリングはPI-GNNソルバと同じである。
関連論文リスト
- Growing Q-Networks: Solving Continuous Control Tasks with Adaptive Control Resolution [51.83951489847344]
ロボット工学の応用において、スムーズな制御信号はシステム摩耗とエネルギー効率を減らすために一般的に好まれる。
本研究では,離散的な動作空間を粗い状態から細かい制御分解能まで拡大することにより,この性能ギャップを埋めることを目的とする。
我々の研究は、値分解とアダプティブ・コントロール・リゾリューションが組み合わさることで、単純な批判のみのアルゴリズムが得られ、連続制御タスクにおいて驚くほど高い性能が得られることを示唆している。
論文 参考訳(メタデータ) (2024-04-05T17:58:37Z) - Continuous Tensor Relaxation for Finding Diverse Solutions in
Combinatorial Optimization Problems [0.8158530638728501]
本研究では,教師なし学習に基づくCOソルバのための連続緩和アニーリング(CTRA)を提案する。
CTRAは、離散決定変数を連続テンソルに変換する連続緩和アプローチを拡張して、様々な問題に同時に対処する。
数値実験により、CTRAにより、ULベースの解法は既存のULベースの解法よりもはるかに高速に不均一でペナルティに分散した解を見つけることができることが示された。
論文 参考訳(メタデータ) (2024-02-03T15:31:05Z) - Distributionally Robust Model-based Reinforcement Learning with Large
State Spaces [55.14361269378122]
強化学習における3つの大きな課題は、大きな状態空間を持つ複雑な力学系、コストのかかるデータ取得プロセス、トレーニング環境の展開から現実の力学を逸脱させることである。
広範に用いられているKullback-Leibler, chi-square, および全変分不確実性集合の下で, 連続状態空間を持つ分布ロバストなマルコフ決定過程について検討した。
本稿では,ガウス過程と最大分散削減アルゴリズムを用いて,多出力名目遷移力学を効率的に学習するモデルベースアプローチを提案する。
論文 参考訳(メタデータ) (2023-09-05T13:42:11Z) - A Single-Loop Deep Actor-Critic Algorithm for Constrained Reinforcement
Learning with Provable Convergence [8.191815417711194]
Deep Actorriticアルゴリズムは、ActorriticとDeep Neural Network(DNN)を組み合わせる
本稿では,一般対話のための単一ループアクタ・クライブアルゴリズムを提案する。
SL-Criticアルゴリズムは、優れた学習近似と優れた性能に収束することを示す。
論文 参考訳(メタデータ) (2023-06-10T10:04:54Z) - Evolving Constrained Reinforcement Learning Policy [5.4444944707433525]
本稿では,報酬と制約違反とを適応的にバランスする,進化的制約付き強化学習アルゴリズムを提案する。
ロボット制御ベンチマーク実験により、ECRLは最先端のアルゴリズムと比較して優れた性能を発揮することが示された。
論文 参考訳(メタデータ) (2023-04-19T03:54:31Z) - 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 with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳(メタデータ) (2022-11-14T21:54:31Z) - Instance-Dependent Confidence and Early Stopping for Reinforcement
Learning [99.57168572237421]
強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。
この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。
次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
論文 参考訳(メタデータ) (2022-01-21T04:25:35Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。
我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。
その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
論文 参考訳(メタデータ) (2020-06-22T03:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。