論文の概要: Ant Colony Sampling with GFlowNets for Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2403.07041v2
- Date: Wed, 22 May 2024 21:18:43 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-25 06:09:38.969422
- Title: Ant Colony Sampling with GFlowNets for Combinatorial Optimization
- Title(参考訳): 組合せ最適化のためのGFlowNetsによるAnt Colonyサンプリング
- Authors: Minsu Kim, Sanghyeok Choi, Hyeonah Kim, Jiwoo Son, Jinkyoo Park, Yoshua Bengio,
- Abstract要約: 本稿では、最適化(CO)のためのニューラルネットワークによる確率的探索アルゴリズムであるGFACS(Generative Flow Ant Colony Sampler)を紹介する。
GFACSは生成フローネットワーク(GFlowNets)と、確率的探索アルゴリズムであるアリコロニー最適化(ACO)を統合している。
- 参考スコア(独自算出の注目度): 68.84985459701007
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces the Generative Flow Ant Colony Sampler (GFACS), a neural-guided probabilistic search algorithm for solving combinatorial optimization (CO). GFACS integrates generative flow networks (GFlowNets), an emerging amortized inference method, with ant colony optimization (ACO), a promising probabilistic search algorithm. Specifically, we use GFlowNets to learn a constructive policy in combinatorial spaces for enhancing ACO by providing an informed prior distribution over decision variables conditioned on input graph instances. Furthermore, we introduce a novel off-policy training algorithm for scaling conditional GFlowNets into large-scale combinatorial spaces by leveraging local search and shared energy normalization. Our experimental results demonstrate that GFACS outperforms baseline ACO algorithms in seven CO tasks and is competitive with problem-specific heuristics for vehicle routing problems.
- Abstract(参考訳): 本稿では,組合せ最適化(CO)のためのニューラルネットワークを用いた確率的探索アルゴリズムであるGFACS(Generative Flow Ant Colony Sampler)を紹介する。
GFACSは生成フローネットワーク(GFlowNets)と、確率的探索アルゴリズムであるアリコロニー最適化(ACO)を統合している。
具体的には、GFlowNetsを用いて、入力グラフインスタンスに条件付き決定変数に関する情報的事前分布を提供することにより、ACOを強化するための組合せ空間における構築ポリシーを学習する。
さらに, 局所探索と共有エネルギー正規化を利用して, 条件付きGFlowNetを大規模組合せ空間に拡張するための新しいオフ政治学習アルゴリズムを提案する。
実験の結果、GFACSは7つのCOタスクにおいてベースラインACOアルゴリズムよりも優れており、車両ルーティング問題に対する問題固有ヒューリスティックと競合することが示された。
関連論文リスト
- Federated Conditional Stochastic Optimization [110.513884892319]
条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。
本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-10-04T01:47:37Z) - Thompson sampling for improved exploration in GFlowNets [75.89693358516944]
生成フローネットワーク(Generative Flow Networks, GFlowNets)は、合成対象物上の分布からのサンプリングを、学習可能なアクションポリシーを用いたシーケンシャルな意思決定問題として扱う、アモータイズされた変分推論アルゴリズムである。
2つの領域において、TS-GFNは、過去の研究で使われたオフ・ポリティクス・サーベイ・ストラテジーよりも、探索を改善し、目標分布への収束を早くすることを示す。
論文 参考訳(メタデータ) (2023-06-30T14:19:44Z) - GQFedWAvg: Optimization-Based Quantized Federated Learning in General
Edge Computing Systems [11.177402054314674]
エッジコンピューティングにおけるフェデレートラーニング(FL)の最適実装は際立った問題であった。
一般エッジコンピューティングシステムと一様あるいは一様でない計算・通信システムとを適切に適合させることができる最適化量子化FLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-13T02:18:24Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳(メタデータ) (2023-05-26T15:13:09Z) - Stochastic Generative Flow Networks [89.34644133901647]
生成フローネットワーク(GFlowNets)は「制御としての推論」のレンズを通して複雑な構造をサンプリングすることを学ぶ
既存のGFlowNetsは決定論的環境にのみ適用でき、動的処理によるより一般的なタスクではフェールする。
本稿では,GFlowNetsを環境に拡張する新しいアルゴリズムであるGFlowNetsを紹介する。
論文 参考訳(メタデータ) (2023-02-19T03:19:40Z) - Distributional GFlowNets with Quantile Flows [73.73721901056662]
Generative Flow Networks(GFlowNets)は、エージェントが一連の意思決定ステップを通じて複雑な構造を生成するためのポリシーを学ぶ確率的サンプルの新たなファミリーである。
本研究では,GFlowNetの分散パラダイムを採用し,各フロー関数を分散化し,学習中により情報的な学習信号を提供する。
GFlowNet学習アルゴリズムは,リスク不確実性のあるシナリオを扱う上で不可欠な,リスクに敏感なポリシーを学習することができる。
論文 参考訳(メタデータ) (2023-02-11T22:06:17Z) - Hybrid Henry Gas Solubility Optimization Algorithm with Dynamic
Cluster-to-Algorithm Mapping for Search-based Software Engineering Problems [1.0323063834827413]
本稿ではHenry Gas Solubility Optimization(HGSO)アルゴリズムの新しい変種であるHGSO(Hybrid HGSO)について述べる。
前者とは異なり、HHGSOは異なるメタヒューリスティックアルゴリズムを提供する複数のクラスタを同じ集団内で共存させることができる。
HHGSOは、適応的な切替係数を持つペナル化および報酬モデルによる動的クラスタ-アルゴリズムマッピングを発明し、メタヒューリスティックなハイブリダイゼーションのための新しいアプローチを提供する。
論文 参考訳(メタデータ) (2021-05-31T12:42:15Z) - Generalized Self-Adapting Particle Swarm Optimization algorithm with
archive of samples [0.0]
本稿では,M-GAPSOと呼ばれるアルゴリズムの新バージョンを紹介する。
GAPSOの当初の定式化と比較すると、グローバル再起動管理スキーム、R-Treeベースインデックス内のサンプル収集、グローバルな粒子性能に基づくサンプリング動作の適応、ローカル検索への具体的なアプローチの4つの特徴がある。
論文 参考訳(メタデータ) (2020-02-28T00:03:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。