論文の概要: Exploration through Generation: Applying GFlowNets to Structured Search

• arxiv url: http://arxiv.org/abs/2510.21886v1
• Date: Thu, 23 Oct 2025 20:43:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 15:28:14.63596
• Title: Exploration through Generation: Applying GFlowNets to Structured Search
• Title（参考訳）: 生成による探索:構造化検索にGFlowNetを適用する
• Authors: Mark Phillip Matovic,
• Abstract要約: この研究は、トラベリングセールスパーソン問題、最小スパンニングツリー、最短パスという3つのグラフ最適化問題に生成フローネットワーク(GFlowNets)を適用した。 GFlowNetsは、報酬関数に比例してソリューションをサンプリングすることを学ぶ生成モデルである。 さまざまなサイズのベンチマークインスタンスの実験は、GFlowNetsが最適なソリューションを見つけることを学ぶことを示している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This work applies Generative Flow Networks (GFlowNets) to three graph optimization problems: the Traveling Salesperson Problem, Minimum Spanning Tree, and Shortest Path. GFlowNets are generative models that learn to sample solutions proportionally to a reward function. The models are trained using the Trajectory Balance loss to build solutions sequentially, se- lecting edges for spanning trees, nodes for paths, and cities for tours. Experiments on benchmark instances of varying sizes show that GFlowNets learn to find optimal solutions. For each problem type, multiple graph configurations with different numbers of nodes were tested. The generated solutions match those from classical algorithms (Dijkstra for shortest path, Kruskal for spanning trees, and exact solvers for TSP). Training convergence depends on problem complexity, with the number of episodes required for loss stabilization increasing as graph size grows. Once training converges, the generated solutions match known optima from classical algorithms across the tested instances. This work demonstrates that generative models can solve combinatorial optimization problems through learned policies. The main advantage of this learning-based approach is computational scalability: while classical algorithms have fixed complexity per instance, GFlowNets amortize computation through training. With sufficient computational resources, the framework could potentially scale to larger problem instances where classical exact methods become infeasible.
• Abstract（参考訳）: この研究は、トラベリングセールスパーソン問題、最小スパンニングツリー、最短パスという3つのグラフ最適化問題に生成フローネットワーク(GFlowNets)を適用した。 GFlowNetsは、報酬関数に比例してソリューションをサンプリングすることを学ぶ生成モデルである。 モデルはTrjectory Balance損失を使用してトレーニングされ、ソリューションをシーケンシャルに構築し、ツリーを横断するエッジをセレクトし、パスのノードを作り、ツアーの都市を作ります。 さまざまなサイズのベンチマークインスタンスの実験は、GFlowNetsが最適なソリューションを見つけることを学ぶことを示している。 各問題タイプについて、ノード数が異なる複数のグラフ構成をテストした。 生成した解は古典的アルゴリズム(最短経路のDijkstra、木を分散するKruskal、TSPの正確な解法)の解と一致する。 トレーニング収束は問題複雑性に依存し、グラフのサイズが大きくなるにつれて損失安定化に必要なエピソード数が増加する。 トレーニングが収束すると、生成されたソリューションは、テストインスタンス全体にわたる古典的アルゴリズムの既知の最適化にマッチする。 この研究は、生成モデルが学習ポリシーを通じて組合せ最適化問題を解くことを実証する。 古典的なアルゴリズムはインスタンス毎に一定の複雑性を持つが、GFlowNetsはトレーニングを通じて計算を記憶する。 十分な計算資源があれば、このフレームワークは、古典的な正確なメソッドが実現不可能な、より大きな問題インスタンスにスケールできる可能性がある。

関連論文リスト

• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) プルーニング手法は階層的に動作し、階層ごとのプルーニングエラーを最小限に抑え、完全な再トレーニングを回避する。 既存の手法は、刈り上げ対象の重量相互作用を無視する欲求凸に依存する。 提案手法は, 層ごとのプルーニング誤差を大幅に低減し, 最先端のGPTアーキテクチャにおいて高いベースラインを達成し, メモリ効率を保っている。
  論文  参考訳（メタデータ） (2025-10-15T16:13:44Z)
• Learning to Branch in Combinatorial Optimization with Graph Pointer Networks [17.729352126574902]
  本稿では,分岐境界における変数選択ポリシーを学習するためのグラフポインターネットワークモデルを提案する。 グラフニューラルネットワークとポインタ機構を組み合わせたモデルでは,解法状態から分岐変数決定への効果的マッピングが可能である。
  論文  参考訳（メタデータ） (2023-07-04T01:56:07Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Learning Sparse Fixed-Structure Gaussian Bayesian Networks [10.180716739570085]
  固定構造ガウスベイズネットワークを全変動距離で有界誤差まで学習する問題について検討する。 一般に使われているノード最小二乗回帰(LeastSquares)を分析し、ほぼ最適サンプルの複雑さがあることを証明した。 ポリツリーに特化したアルゴリズムであるCauchyEstTreeは、ほぼ最適サンプル複雑性を有することを示す。
  論文  参考訳（メタデータ） (2021-07-22T04:17:46Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)

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

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