論文の概要: Boosting Graph Search with Attention Network for Solving the General
Orienteering Problem
- arxiv url: http://arxiv.org/abs/2109.04730v1
- Date: Fri, 10 Sep 2021 08:23:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-13 21:09:43.006228
- Title: Boosting Graph Search with Attention Network for Solving the General
Orienteering Problem
- Title(参考訳): 汎用性問題解決のための注意ネットワークによるグラフ検索の強化
- Authors: Zongtao Liu, Jing Xu, Jintao Su, Tao Xiao and Yang Yang
- Abstract要約: 本稿では,ビームサーチと学習アルゴリズムを組み合わせたオリエンテーリング問題の解法を提案する。
我々は,ノード間の距離を入力とするアテンションネットワークを用いてアルゴリズムを取得し,強化学習フレームワークを用いて学習する。
提案手法は,幅広いベースラインを超えることができ,最適あるいは高度に専門化されたアプローチに近い結果が得られる。
- 参考スコア(独自算出の注目度): 7.0786689796236155
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently, several studies have explored the use of neural network to solve
different routing problems, which is an auspicious direction. These studies
usually design an encoder-decoder based framework that uses encoder embeddings
of nodes and the problem-specific context to produce node sequence(path), and
further optimize the produced result on top by beam search. However, existing
models can only support node coordinates as input, ignore the self-referential
property of the studied routing problems, and lack the consideration about the
low reliability in the initial stage of node selection, thus are hard to be
applied in real-world.
In this paper, we take the orienteering problem as an example to tackle these
limitations. We propose a novel combination of a variant beam search algorithm
and a learned heuristic for solving the general orienteering problem. We
acquire the heuristic with an attention network that takes the distances among
nodes as input, and learn it via a reinforcement learning framework. The
empirical studies show that our method can surpass a wide range of baselines
and achieve results close to the optimal or highly specialized approach. Also,
our proposed framework can be easily applied to other routing problems. Our
code is publicly available.
- Abstract(参考訳): 近年,ニューラルネットワークを用いて異なる経路問題を解く研究がいくつか行われている。
これらの研究は通常、ノードのエンコーダ埋め込みと問題固有のコンテキストを用いてノードシーケンス(path)を生成し、さらにビームサーチによって生成された結果を最適化するエンコーダデコーダベースのフレームワークを設計する。
しかし、既存のモデルはノード座標を入力としてのみサポートし、研究されたルーティング問題の自己参照性を無視し、ノード選択の初期段階における信頼性の低い考慮を欠いているため、実世界では適用が困難である。
本稿では,これらの制約に対処する例として,オリエンテーリング問題を挙げる。
汎用指向性問題の解法として,可変ビーム探索アルゴリズムと学習ヒューリスティックを組み合わせた新しい手法を提案する。
我々は,ノード間の距離を入力とする注意ネットワークを用いてヒューリスティックを取得し,強化学習フレームワークを用いて学習する。
実験により,本手法は広い範囲のベースラインを越え,最適あるいは高度に専門化されたアプローチに近い結果が得られることを示した。
また,提案するフレームワークは他のルーティング問題にも容易に適用できる。
私たちのコードは公開されています。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - Symmetry-preserving graph attention network to solve routing problems at
multiple resolutions [1.9304772860080408]
問題解決のために,最初の完全同変モデルとトレーニングを導入する。
入力グラフのマルチスケール構造を捉えることが不可欠である。
本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
論文 参考訳(メタデータ) (2023-10-24T06:22:20Z) - Learning to Identify Graphs from Node Trajectories in Multi-Robot
Networks [15.36505600407192]
本稿では,グローバル収束保証付きグラフトポロジを効率的に発見する学習ベースアプローチを提案する。
マルチロボット生成および群れ処理におけるグラフの同定におけるアプローチの有効性を実証する。
論文 参考訳(メタデータ) (2023-07-10T07:09:12Z) - Neural Algorithmic Reasoning Without Intermediate Supervision [21.852775399735005]
我々は、中間的監督に訴えることなく、入出力ペアからのみニューラルネットワーク推論を学ぶことに集中する。
我々は、アルゴリズムの軌跡にアクセスできることなく、モデルの中間計算を正規化できる自己教師対象を構築する。
CLRSic Algorithmic Reasoning Benchmarkのタスクにおいて,提案手法はトラジェクトリを教師する手法と競合することを示す。
論文 参考訳(メタデータ) (2023-06-23T09:57:44Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳(メタデータ) (2022-11-01T18:33:20Z) - Neural Networks for Local Search and Crossover in Vehicle Routing: A
Possible Overkill? [10.882329986831087]
我々は,Hybrid Genetic Search(HGS)を改善するために,グラフニューラルネットワーク(GNN)のヒートマップ形式での予測の利用を検討した。
ノード関連性の尺度を用いて,より高度な戦略を活用すれば,性能を大幅に向上できることを示す。
しかし,当初の期待とは裏腹に,ヒートマップは単純な距離測定よりも有意なアドバンテージを示さなかった。
論文 参考訳(メタデータ) (2022-09-09T22:08:17Z) - Combining Optimal Path Search With Task-Dependent Learning in a Neural
Network [4.1712273169097305]
コスト値をシナプス重みに変換することにより,経路探索問題のニューラルネットワーク表現を定義することができることを示す。
ネットワーク学習機構は, ネットワーク内の重みを手作業に応じて強化し, ネットワークの重み付けに適応できることを示す。
論文 参考訳(メタデータ) (2022-01-26T18:29:00Z) - Feature Importance-aware Graph Attention Network and Dueling Double Deep
Q-Network Combined Approach for Critical Node Detection Problems [61.48763653120301]
クリティカルノード問題(Critical Node Problem, CNP)は、ネットワークから重要なノードの集合を見つけることを目的とした問題である。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳(メタデータ) (2021-12-03T14:23:05Z) - Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner
with Evolution-Based Optimization [49.207538634692916]
そこで我々は、効率よくトレーニング可能なルータを形成するための新しい回路ルーティングアルゴリズム、Randing Costを提案する。
提案手法では,A*ルータが適切な経路を見つけるのに役立つコストマップと呼ばれる新しい変数群を導入する。
我々のアルゴリズムはエンドツーエンドで訓練されており、人工データや人間の実演は一切使用しない。
論文 参考訳(メタデータ) (2021-10-08T07:22:45Z) - Decentralized Personalized Federated Learning for Min-Max Problems [82.6119578133503]
本稿では,より広い範囲の最適化問題を含むサドル点問題に対して,PFLを初めて検討した。
この問題に対処するための新しいアルゴリズムを提案し、滑らかな(強く)凸-(強く)凹点問題を理論的に解析する。
両線形問題に対する数値実験と, 対向雑音を有するニューラルネットワークは, 提案手法の有効性を実証する。
論文 参考訳(メタデータ) (2021-06-14T10:36:25Z) - Differentiable Causal Discovery from Interventional Data [141.41931444927184]
本稿では、介入データを活用可能なニューラルネットワークに基づく理論的基盤化手法を提案する。
提案手法は,様々な環境下での美術品の状態と良好に比較できることを示す。
論文 参考訳(メタデータ) (2020-07-03T15:19:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。