論文の概要: Learning to Optimise General TSP Instances
- arxiv url: http://arxiv.org/abs/2010.12214v2
- Date: Tue, 3 Nov 2020 11:51:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-03 22:08:03.982615
- Title: Learning to Optimise General TSP Instances
- Title（参考訳）: 一般的なTSPインスタンスを最適化する学習
- Authors: Nasrin Sultana, Jeffrey Chan, A. K. Qin, Tabinda Sarwar
- Abstract要約: トラベリングセールスマン問題(TSP)は古典的な最適化問題である。
ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。
本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
- 参考スコア（独自算出の注目度）: 2.6782615615913348
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Travelling Salesman Problem (TSP) is a classical combinatorial
optimisation problem. Deep learning has been successfully extended to
meta-learning, where previous solving efforts assist in learning how to
optimise future optimisation instances. In recent years, learning to optimise
approaches have shown success in solving TSP problems. However, they focus on
one type of TSP problem, namely ones where the points are uniformly distributed
in Euclidean spaces and have issues in generalising to other embedding spaces,
e.g., spherical distance spaces, and to TSP instances where the points are
distributed in a non-uniform manner. An aim of learning to optimise is to train
once and solve across a broad spectrum of (TSP) problems. Although supervised
learning approaches have shown to achieve more optimal solutions than
unsupervised approaches, they do require the generation of training data and
running a solver to obtain solutions to learn from, which can be time-consuming
and difficult to find reasonable solutions for harder TSP instances. Hence this
paper introduces a new learning-based approach to solve a variety of different
and common TSP problems that are trained on easier instances which are faster
to train and are easier to obtain better solutions. We name this approach the
non-Euclidean TSP network (NETSP-Net). The approach is evaluated on various TSP
instances using the benchmark TSPLIB dataset and popular instance generator
used in the literature. We performed extensive experiments that indicate our
approach generalises across many types of instances and scales to instances
that are larger than what was used during training.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、古典的な組合せ最適化問題である。
ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来の最適化インスタンスの最適化方法の学習を支援する。
近年,TSP問題の解決にアプローチを最適化する学習が成功している。
しかし、それらはあるタイプの TSP 問題、すなわち点がユークリッド空間に一様に分布し、球面距離空間などの他の埋め込み空間や点が一様でない方法で分布する TSP インスタンスに一般化する問題に焦点をあてている。
最適化を学習する目的は、一度トレーニングを行い、幅広い範囲(TSP)の問題を解決することである。
教師なし学習アプローチは、教師なしのアプローチよりも最適なソリューションを実現することが示されているが、より難しいTSPインスタンスの適切なソリューションを見つけるには、トレーニングデータの生成と、学習するソリューションを得るために解決者を実行する必要がある。
そこで,本研究では,学習がより容易で,より良い解を得るのがより容易なインスタンスをトレーニングする,さまざまな,共通的なTSP問題を解決するための,新たな学習ベースのアプローチを提案する。
このアプローチを非ユークリッドTSPネットワーク(NETSP-Net)と呼ぶ。
この手法は、ベンチマークTSPLIBデータセットと文献で使われる一般的なインスタンスジェネレータを用いて、様々なTSPインスタンス上で評価される。
トレーニングで使用したものよりも大きなインスタンスに,さまざまなタイプのインスタンスとスケールを一般化するアプローチを示す,広範な実験を実施しました。
関連論文リスト
- Cascaded Large-Scale TSP Solving with Unified Neural Guidance: Bridging Local and Population-based Search [23.528483405321975]
UNiCSは、旅行セールスマン問題に対する新しい統合神経誘導型カスケード解決器である。
ステート・オブ・ザ・アーティカルなメソッドを一貫して上回り、ランタイムのアドバンテージはさまざまな予算で一貫しています。
論文 参考訳（メタデータ） (2025-01-24T06:56:27Z) - GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
グラフ拡散型ソリューション生成(GDSG)法を提案する。
このアプローチは、おそらく最適な解に収束しながら、最適以下のデータセットを扱うように設計されている。
グラフニューラルネットワーク(GNN)を用いたマルチタスク拡散モデルとしてGDSGを構築し,高品質な解の分布を求める。
論文 参考訳（メタデータ） (2024-12-11T11:13:43Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem [67.32731657297377]
トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。
近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。
本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
論文 参考訳（メタデータ） (2023-04-19T03:48:32Z) - 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) - Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning [59.14935871979047]
本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。
これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
論文 参考訳（メタデータ） (2022-07-04T14:31:47Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳（メタデータ） (2022-05-31T09:51:48Z) - Learning to Solve Travelling Salesman Problem with Hardness-adaptive
Curriculum [42.28343071442175]
本稿では,既存手法の10倍の精度でインスタンスを生成するハードネス適応型ジェネレータを提案する。
提案手法は, 最適性ギャップの観点から, 最先端モデルに対する大幅な改善を実現する。
論文 参考訳（メタデータ） (2022-04-07T05:59:05Z) - Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。
私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
論文 参考訳（メタデータ） (2021-04-19T14:35:14Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Towards Feature-free TSP Solver Selection: A Deep Learning Approach [35.05032046810422]
トラベリングセールスマン問題(TSP)は古典的なNPハード問題であり、多くの分野や産業で広く応用されている。
本稿では,TSPソルバ選択のためのディープラーニングフレームワークであるCTASを提案する。
論文 参考訳（メタデータ） (2020-06-01T04:48:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。