論文の概要: The Transformer Network for the Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2103.03012v1
• Date: Thu, 4 Mar 2021 13:20:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-05 14:52:55.720872
• Title: The Transformer Network for the Traveling Salesman Problem
• Title（参考訳）: 旅行セールスマン問題のためのトランスフォーマーネットワーク
• Authors: Xavier Bresson and Thomas Laurent
• Abstract要約: 旅行セールスマン問題(TSP)は、1951年にフォン・ノイマンから始まった最も人気があり、最も研究された問題である。 切断面、分岐およびバウンド、ローカル検索、ラグランジアンリラクゼーション、シミュレートアニールなど、いくつかの最適化技術が発見されました。 過去5年間、(グラフ)ニューラルネットワークが新しいアルゴリズムを学習できる有望な技術の出現を見てきました。
• 参考スコア（独自算出の注目度）: 14.706386028691133
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling Salesman Problem (TSP) is the most popular and most studied combinatorial problem, starting with von Neumann in 1951. It has driven the discovery of several optimization techniques such as cutting planes, branch-and-bound, local search, Lagrangian relaxation, and simulated annealing. The last five years have seen the emergence of promising techniques where (graph) neural networks have been capable to learn new combinatorial algorithms. The main question is whether deep learning can learn better heuristics from data, i.e. replacing human-engineered heuristics? This is appealing because developing algorithms to tackle efficiently NP-hard problems may require years of research, and many industry problems are combinatorial by nature. In this work, we propose to adapt the recent successful Transformer architecture originally developed for natural language processing to the combinatorial TSP. Training is done by reinforcement learning, hence without TSP training solutions, and decoding uses beam search. We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)は1951年にフォン・ノイマンから始まった最も人気があり、最も研究されている組合せ問題である。 切断面、分岐およびバウンド、ローカル検索、ラグランジアンリラクゼーション、シミュレートアニールなど、いくつかの最適化技術が発見されました。 過去5年間、(グラフ)ニューラルネットワークが新しい組み合わせアルゴリズムを学習できる有望な技術の出現を見てきました。 主な疑問は、ディープラーニングがデータからより良いヒューリスティックを学習できるかどうかである。 人間工学のヒューリスティックを置き換える? NP-hard問題に効率的に対処するアルゴリズムを開発するには、長年の研究が必要であり、多くの業界問題が自然と組み合わせているため、これは魅力的である。 本研究では,自然言語処理用に開発されたトランスフォーマーアーキテクチャを組込みTSPに適応させることを提案する。 トレーニングは強化学習によって行われ、tspトレーニングソリューションがないため、デコーディングはビームサーチを使用する。 TSP50では0.004%、TSP100では0.39%の最適なギャップを持つ最近の学習ヒューリスティックに対するパフォーマンスの改善を報告する。

関連論文リスト

• Geometry-Informed Neural Operator for Large-Scale 3D PDEs [76.06115572844882]
  大規模偏微分方程式の解演算子を学習するために,幾何インフォームド・ニューラル演算子(GINO)を提案する。 我々はGINOを訓練し、わずか500点のデータポイントで車両表面の圧力を予測することに成功した。
  論文  参考訳（メタデータ） (2023-09-01T16:59:21Z)
• 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)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  最先端の凸学習手法は、クライアントが異なるデータ分布を持つ場合、集中型よりもはるかにパフォーマンスが劣る。 我々は、この格差は、非NISTityが提示した課題に大きく起因していることを示す。 本稿では,Train-Convexify Neural Network (TCT) 手法を提案する。
  論文  参考訳（メタデータ） (2022-07-13T16:58:22Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Solve routing problems with a residual edge-graph attention neural network [10.42872026679616]
  本稿では,NP-ハード最適化問題を解決するために,エンドツーエンドの深層強化学習フレームワークを提案する。 提案するフレームワークは、ニューラルネットワークモデルとトレーニングアルゴリズムの観点から、リテラシーのモデルを改善することを目指している。 具体的には、平均最適性ギャップは、100ノードのTSPで4.53%(ベスト citeR22として報告)から3.67%(ベスト citeR22で報告)、100ノードのCVRPで7.34%(ベスト citeR22で報告)から6.68%に縮小される。
  論文  参考訳（メタデータ） (2021-05-06T14:47:47Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
  自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。 本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。 その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
  論文  参考訳（メタデータ） (2020-02-04T20:00:28Z)

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

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