論文の概要: NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun
Heuristic for Solving the Traveling Salesman Problem
- arxiv url: http://arxiv.org/abs/2110.07983v1
- Date: Fri, 15 Oct 2021 10:14:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-18 23:00:37.802585
- Title: NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun
Heuristic for Solving the Traveling Salesman Problem
- Title（参考訳）: NeuroLKH: ディープラーニングモデルとLin-Kernighan-Helsgaunヒューリスティックを組み合わせたトラベリングセールスマン問題の解法
- Authors: Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang
- Abstract要約: 我々は、Lin-Kernighan-Helsgaun(LKH)とディープラーニングを組み合わせた新しいアルゴリズムNeuroLKHを提案する。
具体的には、エッジスコアの教師付き学習とノードペナルティの教師なし学習を併用したスパースグラフネットワーク(SGN)を訓練する。
幅広い問題サイズで1つのモデルをトレーニングすることで、NeuroLKHはLKHを大幅に上回り、はるかに大きなサイズで一般化する。
- 参考スコア（独自算出の注目度）: 14.605192361813454
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present NeuroLKH, a novel algorithm that combines deep learning with the
strong traditional heuristic Lin-Kernighan-Helsgaun (LKH) for solving Traveling
Salesman Problem. Specifically, we train a Sparse Graph Network (SGN) with
supervised learning for edge scores and unsupervised learning for node
penalties, both of which are critical for improving the performance of LKH.
Based on the output of SGN, NeuroLKH creates the edge candidate set and
transforms edge distances to guide the searching process of LKH. Extensive
experiments firmly demonstrate that, by training one model on a wide range of
problem sizes, NeuroLKH significantly outperforms LKH and generalizes well to
much larger sizes. Also, we show that NeuroLKH can be applied to other routing
problems such as Capacitated Vehicle Routing Problem (CVRP), Pickup and
Delivery Problem (PDP), and CVRP with Time Windows (CVRPTW).
- Abstract（参考訳）: 我々は,旅行セールスマン問題の解法として,ディープラーニングとLin-Kernighan-Helsgaun(LKH)を併用した新しいアルゴリズムNeuroLKHを提案する。
具体的には、エッジスコアの教師付き学習とノードペナルティの教師なし学習を備えたスパースグラフネットワーク(sgn)をトレーニングし、どちらもlkhの性能向上に不可欠である。
SGNの出力に基づいて、NeuroLKHはエッジ候補セットを生成し、エッジ距離を変換してLKHの探索プロセスを導く。
大規模な実験では、幅広い問題サイズで1つのモデルを訓練することで、NeuroLKHはLKHを著しく上回り、はるかに大きなサイズで一般化することを示した。
また, CVRP(Capacitated Vehicle Routing Problem)やPDP(Pickup and Delivery Problem), CVRP with Time Windows(CVRPTW)といった他のルーティング問題にもNeuroLKHが適用可能であることを示す。
関連論文リスト
- How Feature Learning Can Improve Neural Scaling Laws [86.9540615081759]
我々は,カーネル限界を超えたニューラルスケーリング法則の解法モデルを開発する。
モデルのサイズ、トレーニング時間、利用可能なデータの総量によるパフォーマンスのスケールアップ方法を示す。
論文 参考訳（メタデータ） (2024-09-26T14:05:32Z) - Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
組合せ最適化(英: Combinatorial Optimization、CO)は、計算機科学、応用数学などにおける基本的な問題である。
本稿では, 正線形制約下でのCO問題の解法として, 非自己回帰ニューラルネットワーク群を設計する。
本研究では,施設位置,最大被覆率,旅行セールスマン問題を含む代表的CO問題の解決において,この枠組みの有効性を検証する。
論文 参考訳（メタデータ） (2024-09-06T14:58:31Z) - Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale
Generalization [15.189182646851865]
本稿では、この重要な問題に対処する強力な一般化能力を持つ新しい軽量重復号器(LEHD)モデルを提案する。
提案するLEHDモデルに対して,データ効率のトレーニング手法とフレキシブルな解法機構を開発する。
提案したLEHDモデルは,建設的NCOの最先端性能を大幅に向上させることができることを確認した。
論文 参考訳（メタデータ） (2023-10-12T02:18:50Z) - Fixing the NTK: From Neural Network Linearizations to Exact Convex
Programs [63.768739279562105]
学習目標に依存しない特定のマスクウェイトを選択する場合、このカーネルはトレーニングデータ上のゲートReLUネットワークのNTKと等価であることを示す。
この目標への依存の欠如の結果として、NTKはトレーニングセット上の最適MKLカーネルよりもパフォーマンスが良くない。
論文 参考訳（メタデータ） (2023-09-26T17:42:52Z) - Label Deconvolution for Node Representation Learning on Large-scale
Attributed Graphs against Learning Bias [75.44877675117749]
本稿では,GNNの逆写像に対する新しい,スケーラブルな近似による学習バイアスを軽減するために,ラベルの効率的な正規化手法,すなわちラベルのデコンボリューション(LD)を提案する。
実験では、LDはOpen Graphデータセットのベンチマークで最先端のメソッドを大幅に上回っている。
論文 参考訳（メタデータ） (2023-09-26T13:09:43Z) - Learning Lipschitz Functions by GD-trained Shallow Overparameterized
ReLU Neural Networks [12.018422134251384]
このクラスでは、トレーニングエラーのほとんどゼロにトレーニングされたニューラルネットワークが矛盾していることが示される。
ReLUアクティベーション関数によって誘導されるカーネルのヒルベルト空間上で、何らかの早期停止規則が最適率(過剰リスク)を与えることが保証されたとき、同じ規則を極大最適率を達成するために使うことができることを示す。
論文 参考訳（メタデータ） (2022-12-28T14:56:27Z) - Learning to Solve Combinatorial Graph Partitioning Problems via
Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。
最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文 参考訳（メタデータ） (2022-05-27T17:13:10Z) - Online Limited Memory Neural-Linear Bandits with Likelihood Matching [53.18698496031658]
本研究では,探索学習と表現学習の両方が重要な役割を果たす課題を解決するために,ニューラルネットワークの帯域について検討する。
破滅的な忘れ込みに対して耐性があり、完全にオンラインである可能性の高いマッチングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-07T14:19:07Z) - Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm
for the Traveling Salesman Problem [12.851149098610096]
VSR-LKHという可変戦略強化手法を提案する。
3つの強化学習法(q-learning, sarsa, monte carlo)とlin-kernighan-helsgaun(lkh)と呼ばれるよく知られたtspアルゴリズムを組み合わせる。
VSR-LKHはLKHの柔軟性のない操作を置き換え、強化学習によって各探索ステップで選択を学習する。
論文 参考訳（メタデータ） (2020-12-08T14:58:36Z) - Reinforcement Learning via Gaussian Processes with Neural Network Dual
Kernels [0.0]
ニューラルネットワーク二重カーネルは回帰学習や強化学習に効率的に適用可能であることを示す。
我々は、よく理解されたマウンテンカー問題を用いて、デュアルカーネルで権限を持つGPが、従来のラジアル基底関数カーネルと同様に、少なくとも性能を発揮することを示した。
論文 参考訳（メタデータ） (2020-04-10T18:36:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。