論文の概要: DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2302.08224v2
• Date: Sat, 2 Dec 2023 21:27:23 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-06 01:41:42.721412
• Title: DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
• Title（参考訳）: DIFUSCO: 組合せ最適化のためのグラフベースの拡散解法
• Authors: Zhiqing Sun, Yiming Yang
• Abstract要約: グラフベースの拡散フレームワークであるDIFUSCOを導入する。 本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。 MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
• 参考スコア（独自算出の注目度）: 51.517956081644186
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neural network-based Combinatorial Optimization (CO) methods have shown promising results in solving various NP-complete (NPC) problems without relying on hand-crafted domain knowledge. This paper broadens the current scope of neural solvers for NPC problems by introducing a new graph-based diffusion framework, namely DIFUSCO. Our framework casts NPC problems as discrete {0, 1}-vector optimization problems and leverages graph-based denoising diffusion models to generate high-quality solutions. We investigate two types of diffusion models with Gaussian and Bernoulli noise, respectively, and devise an effective inference schedule to enhance the solution quality. We evaluate our methods on two well-studied NPC combinatorial optimization problems: Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Experimental results show that DIFUSCO strongly outperforms the previous state-of-the-art neural solvers, improving the performance gap between ground-truth and neural solvers from 1.76% to 0.46% on TSP-500, from 2.46% to 1.17% on TSP-1000, and from 3.19% to 2.58% on TSP10000. For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.
• Abstract（参考訳）: ニューラルネットワークに基づく組合せ最適化(CO)手法は、手作りのドメイン知識に頼ることなく、様々なNP完全(NPC)問題を解くという有望な結果を示している。 本稿では,新しいグラフベース拡散フレームワークdifuscoを導入することで,npc問題に対するニューラルソルバの現在の適用範囲を広げる。 本フレームワークは,NPC問題を離散ベクトル最適化問題とみなし,グラフに基づく分極拡散モデルを用いて高品質な解を生成する。 ガウスノイズとベルヌーイノイズの2種類の拡散モデルについて検討し,解の質を高めるための効果的な推論スケジュールを考案した。 本研究では,2つのNPC組合せ最適化問題であるトラベリングセールスマン問題(TSP)と最大独立セット(MIS)について検討した。 実験の結果,DIFUSCOは従来の最先端のニューラルソルバよりも優れ,TSP-500では1.76%から0.46%,TSP-1000では2.46%から1.17%,TSP10000では3.19%から2.58%に向上した。 MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。

関連論文リスト

• Neural Solver Selection for Combinatorial Optimization [23.449310200885893]
  本稿では,特徴抽出,選択モデル,選択戦略を含むニューラルソルバのコーディネートを行うための,最初の汎用フレームワークを提案する。 提案するフレームワークは,インスタンスを効果的に分散し,結果として得られる複合解法により性能が大幅に向上することを示す。
  論文  参考訳（メタデータ） (2024-10-13T02:05:41Z)
• Quantum-Inspired Mean Field Probabilistic Model for Combinatorial Optimization Problems [15.435730759218776]
  擬似非制約二項最適化問題の解を近似する新しい量子インスパイア平均場(QIMF)確率モデルを開発した。 実験により,ポートフォリオ選択,重み付きマックスカット問題,イジングモデルといった大規模問題に対するソリューション評価の大幅な改善が示された。
  論文  参考訳（メタデータ） (2024-06-01T01:53:11Z)
• Implicit Stochastic Gradient Descent for Training Physics-informed Neural Networks [51.92362217307946]
  物理インフォームドニューラルネットワーク(PINN)は、前方および逆微分方程式問題の解法として効果的に実証されている。 PINNは、近似すべきターゲット関数が高周波またはマルチスケールの特徴を示す場合、トレーニング障害に閉じ込められる。 本稿では,暗黙的勾配降下法(ISGD)を用いてPINNを訓練し,トレーニングプロセスの安定性を向上させることを提案する。
  論文  参考訳（メタデータ） (2023-03-03T08:17:47Z)
• 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)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  最先端の凸学習手法は、クライアントが異なるデータ分布を持つ場合、集中型よりもはるかにパフォーマンスが劣る。 我々は、この格差は、非NISTityが提示した課題に大きく起因していることを示す。 本稿では,Train-Convexify Neural Network (TCT) 手法を提案する。
  論文  参考訳（メタデータ） (2022-07-13T16:58:22Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
  論文  参考訳（メタデータ） (2022-06-01T10:35:29Z)
• Graph Neural Network Guided Local Search for the Traveling Salesperson Problem [5.906031288935515]
  グラフニューラルネットワーク(GNN)とガイドローカルサーチ(GLS)に基づくトラベリングセールスパーソン問題(TSP)を解決するためのハイブリッドデータ駆動型アプローチを提案する。 提案手法では,次のベストラーニングベースベンチマークよりも10倍,平均最適性ギャップ2.5%の解を求める。
  論文  参考訳（メタデータ） (2021-10-11T14:06:08Z)
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning [8.819672165548477]
  本稿では,マルチプルオプティマス(POMO)を用いたポリシー最適化について紹介する。 POMOは、幅広いCO問題に適用可能であり、CO溶液の表現における対称性を利用するように設計されている。 我々は,旅行セールスマン(TSP),キャパシタンドカールーティング(CVRP),0-1knapsack(KP)の3つの一般的なNPハード問題を解くことで,POMOの有効性を実証した。
  論文  参考訳（メタデータ） (2020-10-30T00:57:50Z)
• Efficient and Scalable Bayesian Neural Nets with Rank-1 Factors [36.56528603807598]
  そこで,各重み行列はランク1部分空間上の分布のみを含むBNNのランク1パラメータ化を提案する。 また、複数のモードをキャプチャするために、混合近似後続法を用いて再検討し、典型的な混合法とは異なり、この手法はメモリ増加を著しく小さくする。 ImageNetのResNet-50、CIFAR-10/100のWide ResNet 28-10、MIMIC-IIIのRNNでは、ランク1のBNNはログ、精度、キャリブレーションで最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2020-05-14T17:58:59Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

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

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