論文の概要: Towards Feature-free TSP Solver Selection: A Deep Learning Approach
- arxiv url: http://arxiv.org/abs/2006.00715v2
- Date: Wed, 14 Apr 2021 10:28:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 07:06:01.253623
- Title: Towards Feature-free TSP Solver Selection: A Deep Learning Approach
- Title（参考訳）: 特徴のないTSPソルバー選択に向けて:ディープラーニングアプローチ
- Authors: Kangfei Zhao, Shengcai Liu, Yu Rong, Jeffrey Xu Yu
- Abstract要約: トラベリングセールスマン問題(TSP)は古典的なNPハード問題であり、多くの分野や産業で広く応用されている。
本稿では,TSPソルバ選択のためのディープラーニングフレームワークであるCTASを提案する。
- 参考スコア（独自算出の注目度）: 35.05032046810422
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Travelling Salesman Problem (TSP) is a classical NP-hard problem and has
broad applications in many disciplines and industries. In a large scale
location-based services system, users issue TSP queries concurrently, where a
TSP query is a TSP instance with $n$ points. In the literature, many advanced
TSP solvers are developed to find high-quality solutions. Such solvers can
solve some TSP instances efficiently but may take an extremely long time for
some other instances. Due to the diversity of TSP instances, it is well-known
that there exists no universal best solver dominating all other solvers on all
possible TSP instances. To solve TSP efficiently, in addition to developing new
TSP solvers, it needs to find a per-instance solver for each TSP instance,
which is known as the TSP solver selection problem. In this paper, for the
first time, we propose a deep learning framework, \CTAS, for TSP solver
selection in an end-to-end manner. Specifically, \CTAS exploits deep
convolutional neural networks to extract informative features from TSP
instances and involves data argumentation strategies to handle the scarcity of
labeled TSP instances. Moreover, to support large scale TSP solver selection,
we construct a challenging TSP benchmark dataset with 6,000 instances, which is
known as the largest TSP benchmark. Our \CTAS achieves over 2$\times$ speedup
of the average running time, comparing the single best solver, and outperforms
the state-of-the-art statistical models.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)は古典的なNPハード問題であり、多くの分野や産業で広く応用されている。
大規模位置情報ベースのサービスシステムでは、ユーザがTSPクエリを同時に発行し、TSPクエリは、$n$ポイントのTSPインスタンスである。
文献では、多くの高度なTSP解法が高品質な解を見つけるために開発されている。
このような解法はTSPインスタンスを効率的に解けるが、他のインスタンスでは極めて長い時間がかかる。
TSP インスタンスの多様性のため、可能な全ての TSP インスタンス上で他のすべての解決者を支配する普遍的ベストソルバは存在しないことが知られている。
TSP を効率的に解くためには,新しい TSP ソルバの開発に加えて,TSP ソルバ選択問題として知られる各 TSP インスタンスに対して,インスタンスごとのソルバを求める必要がある。
本稿では,tspソルバをエンドツーエンドで選択するための深層学習フレームワークである \ctasを提案する。
具体的には、CTASは深層畳み込みニューラルネットワークを利用して、TSPインスタンスから情報的特徴を抽出し、ラベル付きTSPインスタンスの不足を処理するためのデータ議論戦略を含む。
さらに、大規模TSPソルバ選択をサポートするため、6,000インスタンスのTSPベンチマークデータセットを構築し、最大のTSPベンチマークとして知られている。
我々のCTASは平均走行時間の2$\times$スピードアップを達成し、1つの最良の解法を比較し、最先端の統計モデルより優れています。
関連論文リスト
- Cascaded Large-Scale TSP Solving with Unified Neural Guidance: Bridging Local and Population-based Search [23.528483405321975]
UNiCSは、旅行セールスマン問題に対する新しい統合神経誘導型カスケード解決器である。
ステート・オブ・ザ・アーティカルなメソッドを一貫して上回り、ランタイムのアドバンテージはさまざまな予算で一貫しています。
論文 参考訳（メタデータ） (2025-01-24T06:56:27Z) - Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem [67.32731657297377]
トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。
近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。
本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
論文 参考訳（メタデータ） (2023-04-19T03:48:32Z) - H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman
Problem [11.310986634385742]
本稿では,大規模トラベリングセールスマン問題(TSP)に対処する階層的強化学習(H-TSP)に基づくエンドツーエンド学習フレームワークを提案する。
我々は,H-TSPがSOTA検索に匹敵する結果が得られることを示し,時間消費を2桁まで削減する(3.32s vs. 395.85s)。
ソリューションの品質に関してはまだSOTAの結果にギャップがあるが、H-TSPは実用的なアプリケーション、特にオンコールルーティングや乗車などの時間に敏感なアプリケーションに有用であると考えている。
論文 参考訳（メタデータ） (2023-04-19T03:10:30Z) - Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning [59.14935871979047]
本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。
これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
論文 参考訳（メタデータ） (2022-07-04T14:31:47Z) - Learning to Solve Travelling Salesman Problem with Hardness-adaptive
Curriculum [42.28343071442175]
本稿では,既存手法の10倍の精度でインスタンスを生成するハードネス適応型ジェネレータを提案する。
提案手法は, 最適性ギャップの観点から, 最先端モデルに対する大幅な改善を実現する。
論文 参考訳（メタデータ） (2022-04-07T05:59:05Z) - Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep
Learning Method [44.4747903763245]
ジョブショップスケジューリング問題(Jobs shop Scheduling Problem、JSP)は、様々な産業目的のために日常的に解決される標準最適化問題である。
問題はNPハードであり、中規模のインスタンスでも計算が困難である。
本稿では,問題に対する効率的かつ正確な近似を提供するためのディープラーニングアプローチについて検討する。
論文 参考訳（メタデータ） (2021-10-12T21:15:19Z) - Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances [55.64521598173897]
本稿では,旅行セールスマン問題(TSP)のヒートマップ構築に繰り返し使用可能な,小規模モデルのトレーニングを試みる。
ヒートマップは強化学習アプローチ(モンテカルロツリーサーチ)に供給され、高品質のソリューションの検索を案内します。
実験結果によると、この新しいアプローチは、既存の機械学習ベースのTSPアルゴリズムを明らかに上回る。
論文 参考訳（メタデータ） (2020-12-19T11:06:30Z) - Learning to Optimise General TSP Instances [2.6782615615913348]
トラベリングセールスマン問題(TSP)は古典的な最適化問題である。
ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。
本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
論文 参考訳（メタデータ） (2020-10-23T07:37:16Z) - Solving the Clustered Traveling Salesman Problem via TSP methods [16.304413942851397]
クラスタ化トラベリングセールスマン問題(CTSP)は、一般的なトラベリングセールスマン問題(TSP)の変種である。
本研究ではCTSPをよく研究されたTSPに変換することでCTSPを解く変換手法について検討する。
論文 参考訳（メタデータ） (2020-07-10T08:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。