論文の概要: GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems
- arxiv url: http://arxiv.org/abs/2405.12475v1
- Date: Tue, 21 May 2024 03:33:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-22 14:28:21.083037
- Title: GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems
- Title（参考訳）: GASE:車両経路問題の解法のためのエッジフュージョンを用いたグラフ注意サンプリング
- Authors: Zhenwei Wang, Ruibin Bai, Fazlullah Khan, Ender Ozcan, Tiehua Zhang,
- Abstract要約: 車両のルーティング問題を解決するためにEdges Fusionフレームワークを用いた適応型グラフ注意サンプリングを提案する。
提案手法は,既存の手法を2.08%-6.23%上回り,より強力な一般化能力を示す。
- 参考スコア（独自算出の注目度）: 6.084414764415137
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Learning-based methods have become increasingly popular for solving vehicle routing problems due to their near-optimal performance and fast inference speed. Among them, the combination of deep reinforcement learning and graph representation allows for the abstraction of node topology structures and features in an encoder-decoder style. Such an approach makes it possible to solve routing problems end-to-end without needing complicated heuristic operators designed by domain experts. Existing research studies have been focusing on novel encoding and decoding structures via various neural network models to enhance the node embedding representation. Despite the sophisticated approaches applied, there is a noticeable lack of consideration for the graph-theoretic properties inherent to routing problems. Moreover, the potential ramifications of inter-nodal interactions on the decision-making efficacy of the models have not been adequately explored. To bridge this gap, we propose an adaptive Graph Attention Sampling with the Edges Fusion framework (GASE),where nodes' embedding is determined through attention calculation from certain highly correlated neighbourhoods and edges, utilizing a filtered adjacency matrix. In detail, the selections of particular neighbours and adjacency edges are led by a multi-head attention mechanism, contributing directly to the message passing and node embedding in graph attention sampling networks. Furthermore, we incorporate an adaptive actor-critic algorithm with policy improvements to expedite the training convergence. We then conduct comprehensive experiments against baseline methods on learning-based VRP tasks from different perspectives. Our proposed model outperforms the existing methods by 2.08\%-6.23\% and shows stronger generalization ability, achieving state-of-the-art performance on randomly generated instances and real-world datasets.
- Abstract（参考訳）: 学習ベースの手法は、ほぼ最適性能と高速な推論速度のため、車両のルーティング問題を解決するために人気が高まっている。
その中でも、深層強化学習とグラフ表現の組み合わせにより、ノードトポロジー構造とエンコーダ-デコーダスタイルの特徴を抽象化することができる。
このようなアプローチにより、ドメインの専門家が設計した複雑なヒューリスティック演算子を必要とせずに、ルーティング問題をエンドツーエンドで解決することができる。
既存の研究は、ノード埋め込み表現を強化するために、様々なニューラルネットワークモデルによる新しいエンコーディングとデコード構造に注目している。
高度なアプローチが適用されているにも拘わらず、ルーティング問題に固有のグラフ理論的性質について考慮されていないことは顕著である。
さらに, モデル決定の有効性に対するノイズ間相互作用の潜在的影響については, 十分に検討されていない。
このギャップを埋めるため,エッジ・フュージョン・フレームワーク(GASE)を用いた適応グラフ注意サンプリングを提案する。
詳細は、特定の近傍と隣接エッジの選択はマルチヘッドアテンション機構によって導かれ、グラフアテンションサンプリングネットワークにおけるメッセージパッシングとノード埋め込みに直接寄与する。
さらに,適応的アクター批判アルゴリズムにポリシーの改善を加え,トレーニング収束を高速化する。
そして、異なる視点から学習に基づくVRPタスクのベースライン手法に対する総合的な実験を行う。
提案モデルでは,既存の手法を2.08\%-6.23\%で上回り,より強力な一般化能力を示し,ランダムに生成されたインスタンスや実世界のデータセット上で最先端の性能を実現する。
関連論文リスト
- Learning to Identify Graphs from Node Trajectories in Multi-Robot
Networks [15.36505600407192]
本稿では,グローバル収束保証付きグラフトポロジを効率的に発見する学習ベースアプローチを提案する。
マルチロボット生成および群れ処理におけるグラフの同定におけるアプローチの有効性を実証する。
論文 参考訳（メタデータ） (2023-07-10T07:09:12Z) - Interpolation-based Correlation Reduction Network for Semi-Supervised
Graph Learning [49.94816548023729]
補間型相関低減ネットワーク(ICRN)と呼ばれる新しいグラフコントラスト学習手法を提案する。
提案手法では,決定境界のマージンを大きくすることで,潜在特徴の識別能力を向上させる。
この2つの設定を組み合わせることで、豊富なラベル付きノードと稀に価値あるラベル付きノードから豊富な監視情報を抽出し、離散表現学習を行う。
論文 参考訳（メタデータ） (2022-06-06T14:26:34Z) - Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent
Signals: Application to Hyperspectral Imaging [71.57324258813675]
相互依存信号のデータセットは、列が強い依存を示す行列として定義される。
ニューラルネットワークは、事前に構造として機能し、基礎となる信号相互依存性を明らかにするために使用される。
ディープ・アンローリングとディープ・平衡に基づくアルゴリズムが開発され、高度に解釈可能で簡潔なディープ・ラーニング・ベース・アーキテクチャを形成する。
論文 参考訳（メタデータ） (2022-03-29T21:00:39Z) - A Differentiable Approach to Combinatorial Optimization using Dataless
Neural Networks [20.170140039052455]
我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。
特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
論文 参考訳（メタデータ） (2022-03-15T19:21:31Z) - Improved Dual Correlation Reduction Network [40.792587861237166]
改良二重相関低減ネットワーク(IDCRN)と呼ばれる新しいディープグラフクラスタリングアルゴリズムを提案する。
クロスビュー特徴相関行列をアイデンティティ行列に近似することにより、特徴の異なる次元間の冗長性を低減できる。
また,グラフ畳み込みネットワーク(GCN)における過度にスムースな問題による表現の崩壊を,伝播正規化項によって回避する。
論文 参考訳（メタデータ） (2022-02-25T07:48:32Z) - Neural combinatorial optimization beyond the TSP: Existing architectures
under-represent graph structure [9.673093148930876]
我々は、最近のニューラルネットワークが実際に重要なグラフ問題にどのように適用できるのか、その分析を行う。
距離問題の構造的表現を増大させることは、多目的自律型問題解決者を学ぶという、まだ曖昧な目標に向けた有望なステップであることを示す。
論文 参考訳（メタデータ） (2022-01-03T14:14:28Z) - Bayesian Graph Contrastive Learning [55.36652660268726]
本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。
提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。
いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
論文 参考訳（メタデータ） (2021-12-15T01:45:32Z) - Anomaly Detection on Attributed Networks via Contrastive Self-Supervised
Learning [50.24174211654775]
本論文では,アトリビュートネットワーク上の異常検出のためのコントラスト型自己監視学習フレームワークを提案する。
このフレームワークは、新しいタイプのコントラストインスタンスペアをサンプリングすることで、ネットワークデータからのローカル情報を完全に活用します。
高次元特性と局所構造から情報埋め込みを学習するグラフニューラルネットワークに基づくコントラスト学習モデルを提案する。
論文 参考訳（メタデータ） (2021-02-27T03:17:20Z) - Graph Representation Learning via Graphical Mutual Information
Maximization [86.32278001019854]
本稿では,入力グラフとハイレベルな隠蔽表現との相関を測る新しい概念であるGMIを提案する。
我々は,グラフニューラルエンコーダの入力と出力の間でGMIを最大化することで訓練された教師なし学習モデルを開発する。
論文 参考訳（メタデータ） (2020-02-04T08:33:49Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳（メタデータ） (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。