論文の概要: Solve routing problems with a residual edge-graph attention neural network

• arxiv url: http://arxiv.org/abs/2105.02730v1
• Date: Thu, 6 May 2021 14:47:47 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-07 13:19:19.187240
• Title: Solve routing problems with a residual edge-graph attention neural network
• Title（参考訳）: 残差エッジグラフアテンションニューラルネットワークによる経路問題の解法
• Authors: Kun Lei, Peng Guo, Yi Wang, Xiao Wu, Wenchao Zhao
• Abstract要約: 本稿では,NP-ハード最適化問題を解決するために,エンドツーエンドの深層強化学習フレームワークを提案する。 提案するフレームワークは、ニューラルネットワークモデルとトレーニングアルゴリズムの観点から、リテラシーのモデルを改善することを目指している。 具体的には、平均最適性ギャップは、100ノードのTSPで4.53%(ベスト citeR22として報告)から3.67%(ベスト citeR22で報告)、100ノードのCVRPで7.34%(ベスト citeR22で報告)から6.68%に縮小される。
• 参考スコア（独自算出の注目度）: 10.42872026679616
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For NP-hard combinatorial optimization problems, it is usually difficult to find high-quality solutions in polynomial time. The design of either an exact algorithm or an approximate algorithm for these problems often requires significantly specialized knowledge. Recently, deep learning methods provide new directions to solve such problems. In this paper, an end-to-end deep reinforcement learning framework is proposed to solve this type of combinatorial optimization problems. This framework can be applied to different problems with only slight changes of input (for example, for a traveling salesman problem (TSP), the input is the two-dimensional coordinates of nodes; while for a capacity-constrained vehicle routing problem (CVRP), the input is simply changed to three-dimensional vectors including the two-dimensional coordinates and the customer demands of nodes), masks and decoder context vectors. The proposed framework is aiming to improve the models in literacy in terms of the neural network model and the training algorithm. The solution quality of TSP and the CVRP up to 100 nodes are significantly improved via our framework. Specifically, the average optimality gap is reduced from 4.53\% (reported best \cite{R22}) to 3.67\% for TSP with 100 nodes and from 7.34\% (reported best \cite{R22}) to 6.68\% for CVRP with 100 nodes when using the greedy decoding strategy. Furthermore, our framework uses about 1/3$\sim$3/4 training samples compared with other existing learning methods while achieving better results. The results performed on randomly generated instances and the benchmark instances from TSPLIB and CVRPLIB confirm that our framework has a linear running time on the problem size (number of nodes) during the testing phase, and has a good generalization performance from random instance training to real-world instance testing.
• Abstract（参考訳）: np-ハードコンビネート最適化問題の場合、通常多項式時間で高品質な解を見つけることは困難である。 これらの問題に対する正確なアルゴリズムまたは近似アルゴリズムの設計は、しばしば非常に専門的な知識を必要とする。 近年,深層学習はそのような問題を解決する新しい方法を提供している。 本稿では,このような組合せ最適化問題を解決するために,エンドツーエンドの深層強化学習フレームワークを提案する。 このフレームワークは、入力のわずかな変更だけで異なる問題に適用できる(例えば、旅行セールスマン問題(TSP)では、入力はノードの2次元座標であり、キャパシティ制約付き車両ルーティング問題(CVRP)では、入力は2次元座標とノードの顧客要求を含む3次元ベクトルに単純に変換される。 提案するフレームワークは、ニューラルネットワークモデルとトレーニングアルゴリズムの観点から、リテラシーのモデルを改善することを目指している。 tsp と 100 ノードまでの cvrp のソリューション品質は,このフレームワークにより大幅に向上した。 具体的には、平均最適ギャップを、100ノードのtspでは4.53\%(ベスト・デコード)から3.67\%(ベスト・デコード戦略では7.34\%)から、100ノードのcvrpでは6.68\%に削減する。 さらに,既存の学習方法と比較して約1/3$\sim$3/4のトレーニングサンプルを用い,良好な結果を得た。 ランダムに生成されたインスタンスとtsplibとcvrplibのベンチマークインスタンスで行った結果から、テストフェーズ中の問題サイズ(ノード数)に対する線形実行時間が得られ、ランダムインスタンストレーニングから実世界のインスタンステストまで、優れた一般化性能が得られています。

関連論文リスト

• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• On Statistical Learning of Branch and Bound for Vehicle Routing Optimization [3.6922704509753084]
  我々は,計算コストの高いStrong Branching戦略の決定過程をエミュレートするためにニューラルネットワークを訓練する。 このアプローチは分岐とバウンドのアルゴリズムの性能にマッチするか、改善することができる。
  論文  参考訳（メタデータ） (2023-10-15T23:59:57Z)
• Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks [4.084365114504618]
  本稿では,ユークリッド旅行セールスマン問題(TSP)のアルゴリズム選択問題を再検討する。 我々はGINESと呼ばれる新しいグラフニューラルネットワーク(GNN)を提案する。 GINESは都市の座標と都市間の距離を入力として取ります。 これは、1つのデータセットにおける従来の手作りの機能ベースのアプローチよりも優れている。
  論文  参考訳（メタデータ） (2023-02-08T13:14:20Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• 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)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  最先端の凸学習手法は、クライアントが異なるデータ分布を持つ場合、集中型よりもはるかにパフォーマンスが劣る。 我々は、この格差は、非NISTityが提示した課題に大きく起因していることを示す。 本稿では,Train-Convexify Neural Network (TCT) 手法を提案する。
  論文  参考訳（メタデータ） (2022-07-13T16:58:22Z)
• A Continuous Optimisation Benchmark Suite from Neural Network Regression [0.0]
  ニューラルネットワークのトレーニングは、近年のディープラーニングの成功で注目を集めている最適化タスクである。 勾配降下変種は、大規模機械学習タスクにおける信頼性の高いパフォーマンスにおいて、最も一般的な選択である。 CORNNは、ニューラルネットワークのトレーニング問題に対して、連続的なブラックボックスアルゴリズムのパフォーマンスをベンチマークするスイートである。
  論文  参考訳（メタデータ） (2021-09-12T20:24:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
  本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。 我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。 計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
  論文  参考訳（メタデータ） (2020-01-12T15:54:20Z)

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

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