論文の概要: 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は探査能力を高めることが明らかとなった。
関連論文リスト
- 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) - Controlling Continuous Relaxation for Combinatorial Optimization [0.0]
CO問題に対する教師なし学習(UL)に基づく解法が提案されている。
これらの解法は、CO目標を直接最適化することで解を出力するニューラルネットワークを訓練する。
論文 参考訳(メタデータ) (2023-09-29T04:23:58Z) - Nonuniqueness and Convergence to Equivalent Solutions in Observer-based
Inverse Reinforcement Learning [2.7178968279054927]
オンラインおよびリアルタイムに決定論的逆強化学習(IRL)問題を解決する上で重要な課題は、複数のソリューションの存在である。
非特異性は等価解の概念の研究を必要とする。
IRL問題のほぼ等価解に収束する正規化履歴スタックオブザーバを開発した。
論文 参考訳(メタデータ) (2022-10-28T17:52:18Z) - Revisiting GANs by Best-Response Constraint: Perspective, Methodology,
and Application [49.66088514485446]
ベストレスポンス制約(Best-Response Constraint、BRC)は、ジェネレータのディスクリミネータへの依存性を明示的に定式化する一般的な学習フレームワークである。
モチベーションや定式化の相違があっても, フレキシブルBRC法により, 様々なGANが一様に改善できることが示される。
論文 参考訳(メタデータ) (2022-05-20T12:42:41Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - A Multi-objective Evolutionary Algorithm for EEG Inverse Problem [0.0]
本稿では,脳波逆問題に対する多目的アプローチを提案する。
この問題の特徴から、この代替案にはそれを解決するための進化戦略が含まれていた。
その結果、分散ソリューションを推定するために、MOEAAR(Anatomical Restrictions)に基づく多目的進化的アルゴリズムが得られた。
論文 参考訳(メタデータ) (2021-07-21T19:37:27Z) - 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) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳(メタデータ) (2020-02-17T20:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。