論文の概要: Supplementing Recurrent Neural Networks with Annealing to Solve
Combinatorial Optimization Problems
- arxiv url: http://arxiv.org/abs/2207.08189v2
- Date: Thu, 26 Oct 2023 23:49:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-30 18:55:04.145503
- Title: Supplementing Recurrent Neural Networks with Annealing to Solve
Combinatorial Optimization Problems
- Title（参考訳）: 組合せ最適化問題を解くためのアニーリングによる繰り返しニューラルネットワークの補間
- Authors: Shoummo Ahsan Khandoker, Jawaril Munshad Abedin, Mohamed Hibat-Allah
- Abstract要約: 本稿では,実世界の最適化問題に対するアプローチとして,変分古典アニール (VCA) を用いる可能性を示す。
以上の結果から, VCA は相対誤差の点で, 平均1桁以上の限界でアニーリング (SA) を平均的に上回ることがわかった。
ベストケースシナリオでは、SAが最適解を見つけられなかった場合、VCAは優れた代替手段として機能する、と結論付けます。
- 参考スコア（独自算出の注目度）: 2.3642391095636484
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial optimization problems can be solved by heuristic algorithms
such as simulated annealing (SA) which aims to find the optimal solution within
a large search space through thermal fluctuations. The algorithm generates new
solutions through Markov-chain Monte Carlo techniques. This sampling scheme can
result in severe limitations, such as slow convergence and a tendency to stay
within the same local search space at small temperatures. To overcome these
shortcomings, we use the variational classical annealing (VCA) framework that
combines autoregressive recurrent neural networks (RNNs) with traditional
annealing to sample solutions that are uncorrelated. In this paper, we
demonstrate the potential of using VCA as an approach to solving real-world
optimization problems. We explore VCA's performance in comparison with SA at
solving three popular optimization problems: the maximum cut problem (Max-Cut),
the nurse scheduling problem (NSP), and the traveling salesman problem (TSP).
For all three problems, we find that VCA outperforms SA on average in the
asymptotic limit by one or more orders of magnitude in terms of relative error.
Interestingly, we reach large system sizes of up to $256$ cities for the TSP.
We also conclude that in the best case scenario, VCA can serve as a great
alternative when SA fails to find the optimal solution.
- Abstract（参考訳）: 組合せ最適化問題は、熱ゆらぎによる大規模な探索空間内での最適解を見つけることを目的としたシミュレートアニーリング(SA)のようなヒューリスティックアルゴリズムによって解決できる。
このアルゴリズムはマルコフ連鎖モンテカルロ法による新しい解を生成する。
このサンプリングスキームは、緩やかな収束や、小さな温度で同じ局所的な探索空間に留まる傾向など、厳しい制限をもたらす可能性がある。
これらの欠点を克服するために、自動回帰リカレントニューラルネットワーク(RNN)と従来のアニーリングを組み合わせた変分古典的アニーリング(VCA)フレームワークを、非相関なサンプルソリューションに使用しています。
本稿では,実世界の最適化問題に対するアプローチとして,VCAを用いる可能性を示す。
我々は,最大カット問題 (Max-Cut) ,看護スケジューリング問題 (NSP) ,旅行セールスマン問題 (TSP) の3つの一般的な最適化問題の解法において,VCAの性能をSAと比較した。
3つの問題すべてにおいて、vcaは平均的な漸近限界において平均で1桁以上の相対誤差でsaを上回ることが分かる。
興味深いことに、TSPのシステムサイズは最大で256ドルに達する。
また、ベストケースシナリオでは、SAが最適解を見つけられなかった場合、VCAは優れた代替手段として機能する。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
組合せ最適化(英: Combinatorial Optimization、CO)は、計算機科学、応用数学などにおける基本的な問題である。
本稿では, 正線形制約下でのCO問題の解法として, 非自己回帰ニューラルネットワーク群を設計する。
本研究では,施設位置,最大被覆率,旅行セールスマン問題を含む代表的CO問題の解決において,この枠組みの有効性を検証する。
論文 参考訳（メタデータ） (2024-09-06T14:58:31Z) - BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems [7.196057722218442]
制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。
COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。
提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
論文 参考訳（メタデータ） (2023-12-26T03:09:08Z) - 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) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳（メタデータ） (2023-05-26T15:13:09Z) - Learning to Solve the AC Optimal Power Flow via a Lagrangian Approach [9.561589138108811]
ACOPF問題に対するラグランジアンベースのアプローチを用いる。
トレーニングソリューションが最適以下であっても,我々のアプローチがグローバルな最適コストを得ることができることを示す。
論文 参考訳（メタデータ） (2021-10-04T18:29:08Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:09:12Z) - A Hybrid Framework Using a QUBO Solver For Permutation-Based
Combinatorial Optimization [5.460573052311485]
本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。
通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
論文 参考訳（メタデータ） (2020-09-27T07:15:25Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated
Algorithm Selection [0.0]
トラベリング・サレスパーソン・プロブレム(TSP)は、最もよく知られたNPハード最適化問題の1つである。
我々は、不正確なTSPソルバの任意の動作に対処することで、既存のベンチマーク研究を拡張した。
その結果、解法の性能ランキングは、集中した近似品質に大きく依存していることが判明した。
論文 参考訳（メタデータ） (2020-05-27T11:36:53Z) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳（メタデータ） (2020-02-17T20:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。