論文の概要: Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2402.02190v1
• Date: Sat, 3 Feb 2024 15:31:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-06 21:24:58.359003
• Title: Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems
• Title（参考訳）: 組合せ最適化問題における多様な解を求める連続テンソル緩和
• Authors: Yuma Ichikawa, Hiroaki Iwashita
• Abstract要約: 本研究では,教師なし学習に基づくCOソルバのための連続緩和アニーリング(CTRA)を提案する。 CTRAは、離散決定変数を連続テンソルに変換する連続緩和アプローチを拡張して、様々な問題に同時に対処する。 数値実験により、CTRAにより、ULベースの解法は既存のULベースの解法よりもはるかに高速に不均一でペナルティに分散した解を見つけることができることが示された。
• 参考スコア（独自算出の注目度）: 0.8158530638728501
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the best solution is the most common objective in combinatorial optimization (CO) problems. However, a single solution may not be suitable in practical scenarios, as the objective functions and constraints are only approximations of original real-world situations. To tackle this, finding (i) "heterogeneous solutions", diverse solutions with distinct characteristics, and (ii) "penalty-diversified solutions", variations in constraint severity, are natural directions. This strategy provides the flexibility to select a suitable solution during post-processing. However, discovering these diverse solutions is more challenging than identifying a single solution. To overcome this challenge, this study introduces Continual Tensor Relaxation Annealing (CTRA) for unsupervised-learning-based CO solvers. CTRA addresses various problems simultaneously by extending the continual relaxation approach, which transforms discrete decision variables into continual tensors. This method finds heterogeneous and penalty-diversified solutions through mutual interactions, where the choice of one solution affects the other choices. Numerical experiments show that CTRA enables UL-based solvers to find heterogeneous and penalty-diversified solutions much faster than existing UL-based solvers. Moreover, these experiments reveal that CTRA enhances the exploration ability.
• Abstract（参考訳）: 最適解を見つけることは組合せ最適化(CO)問題の最も一般的な目的である。 しかし、目的関数と制約は本来の実世界の状況の近似に過ぎないため、現実的なシナリオでは単一の解は適さないかもしれない。 これに取り組むために (i)「異種解」、異なる特徴を有する多種多様な解、及び (ii)制約重大度の変化である「ペナルティ・ダイバーシファイズド・ソリューション」は自然方向である。 この戦略は、後処理中に適切なソリューションを選択する柔軟性を提供する。 しかし、これらの多様なソリューションを見つけることは、単一のソリューションを特定するよりも難しい。 この課題を克服するために、教師なし学習に基づくCOソルバのための連続テンソル緩和アニーリング(CTRA)を導入する。 CTRAは、離散決定変数を連続テンソルに変換する連続緩和アプローチを拡張して、様々な問題に同時に対処する。 この方法は相互相互作用を通じて不均一でペナルティに富んだ解を見つけ、一方の解の選択は他の解に影響を及ぼす。 数値実験により、CTRAにより、ULベースの解法は既存のULベースの解法よりもはるかに高速に不均一でペナルティに分散した解を見つけることができることが示された。 さらに、これらの実験により、CTRAは探査能力を高めることが明らかとなった。

関連論文リスト

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems [37.205311971072405]
  DISCOは、大規模な組合せ最適化問題に対する効率的な拡散解法である。 サンプリング空間は、解残基によって導かれるより有意義な領域に制約され、出力分布のマルチモーダルな性質は保たれる。 大規模なトラベリングセールスマン問題や最大独立セットのベンチマークに挑戦し、他の拡散手段よりも最大5.28倍の速度で推論を行う。
  論文  参考訳（メタデータ） (2024-06-28T07:36:31Z)
• Improved Training of Physics-Informed Neural Networks with Model Ensembles [81.38804205212425]
  我々は、PINNを正しい解に収束させるため、解区間を徐々に拡大することを提案する。 すべてのアンサンブルのメンバーは、観測されたデータの近くで同じ解に収束する。 提案手法は, 得られた解の精度を向上させることができることを示す。
  論文  参考訳（メタデータ） (2022-04-11T14:05:34Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• A Mutual Information Maximization Approach for the Spurious Solution Problem in Weakly Supervised Question Answering [60.768146126094955]
  弱々しい教師付き質問応答は通常、最終的な答えのみを監督信号として持つ。 偶然に正解を導出する刺激的な解が多数存在するかもしれないが、そのような解の訓練はモデルの性能を損なう可能性がある。 本稿では,質問応答対と予測解間の相互情報の最大化により,このような意味的相関を明示的に活用することを提案する。
  論文  参考訳（メタデータ） (2021-06-14T05:47:41Z)
• Discovering Diverse Solutions in Deep Reinforcement Learning [84.45686627019408]
  強化学習アルゴリズムは通常、特定のタスクの単一のソリューションを学ぶことに限定される。 連続的あるいは離散的な低次元潜在変数に条件付きポリシーを訓練することにより、無限に多くの解を学習できるRL法を提案する。
  論文  参考訳（メタデータ） (2021-03-12T04:54:31Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。 最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
  論文  参考訳（メタデータ） (2021-02-14T18:05:42Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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