論文の概要: Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
- arxiv url: http://arxiv.org/abs/2012.10658v2
- Date: Wed, 24 Feb 2021 02:48:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-01 15:48:01.257507
- Title: Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
- Title(参考訳): 小さな事前学習モデルを任意に大規模TSPインスタンスに一般化する
- Authors: Zhang-Hua Fu, Kai-Bin Qiu, Hongyuan Zha
- Abstract要約: 本稿では,旅行セールスマン問題(TSP)のヒートマップ構築に繰り返し使用可能な,小規模モデルのトレーニングを試みる。
ヒートマップは強化学習アプローチ(モンテカルロツリーサーチ)に供給され、高品質のソリューションの検索を案内します。
実験結果によると、この新しいアプローチは、既存の機械学習ベースのTSPアルゴリズムを明らかに上回る。
- 参考スコア(独自算出の注目度): 55.64521598173897
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For the traveling salesman problem (TSP), the existing supervised learning
based algorithms suffer seriously from the lack of generalization ability. To
overcome this drawback, this paper tries to train (in supervised manner) a
small-scale model, which could be repetitively used to build heat maps for TSP
instances of arbitrarily large size, based on a series of techniques such as
graph sampling, graph converting and heat maps merging. Furthermore, the heat
maps are fed into a reinforcement learning approach (Monte Carlo tree search),
to guide the search of high-quality solutions. Experimental results based on a
large number of instances (with up to 10,000 vertices) show that, this new
approach clearly outperforms the existing machine learning based TSP
algorithms, and significantly improves the generalization ability of the
trained model.
- Abstract(参考訳): 旅行セールスマン問題 (TSP) では,既存の教師付き学習に基づくアルゴリズムは,一般化能力の欠如に重きをなしている。
この欠点を克服するために、グラフサンプリング、グラフ変換、ヒートマップの融合といった一連の手法に基づいて、任意の大きさのTSPインスタンスのヒートマップを反復的に構築することのできる小規模モデルを(教師付き方式で)訓練しようとする。
さらに、熱マップを強化学習アプローチ(モンテカルロ木探索)に投入し、高品質な解の探索を指導する。
多数のインスタンス(最大10,000の頂点を持つ)に基づく実験結果は、この新しいアプローチが既存の機械学習ベースのTSPアルゴリズムよりも明らかに優れており、トレーニングされたモデルの一般化能力が大幅に向上していることを示している。
関連論文リスト
- Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems [14.277867417951347]
大規模旅行セールスマン問題の解決における最近の進歩は、ヒートマップ誘導モンテカルロ木探索(MCTS)パラダイムを利用している。
簡単なベースライン法は,ヒートマップ生成における複雑なML手法より優れていることを示す。
本研究は,問題固有の手作り戦略に依存しているにもかかわらず,LKH-3に対するパラダイムの劣りを示すものである。
論文 参考訳(メタデータ) (2024-06-02T16:11:38Z) - An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for
Traveling Salesman Problems [22.792870849003137]
本研究では、トラベリングセールスマン問題(TSP)を解決するためのデータ駆動グラフ表現学習法を提案する。
残留ゲートエンコーダは遅延エッジ埋め込みを学習するために訓練され、次いでエッジ中心のデコーダでリンク予測をエンドツーエンドに出力する。
実験結果から,提案したエッジ対応グラフオートエンコーダモデルにより,高い競合性能が得られた。
論文 参考訳(メタデータ) (2023-10-10T11:42:49Z) - Generalizing Backpropagation for Gradient-Based Interpretability [103.2998254573497]
モデルの勾配は、半環を用いたより一般的な定式化の特別な場合であることを示す。
この観測により、バックプロパゲーションアルゴリズムを一般化し、他の解釈可能な統計を効率的に計算することができる。
論文 参考訳(メタデータ) (2023-07-06T15:19:53Z) - Travel the Same Path: A Novel TSP Solving Strategy [0.0]
我々は、必要に応じて適切な選択を行う決定論的アルゴリズムを支援する模倣学習フレームワークについて検討する。
我々は、模倣学習フレームワークの下で訓練されたグラフニューラルネットワークの強力な一般化能力を示す。
論文 参考訳(メタデータ) (2022-10-12T03:56:37Z) - A General Framework for Sample-Efficient Function Approximation in
Reinforcement Learning [132.45959478064736]
モデルベースとモデルフリー強化学習を統合した汎用フレームワークを提案する。
最適化に基づく探索のための分解可能な構造特性を持つ新しい推定関数を提案する。
本フレームワークでは,OPERA (Optimization-based Exploration with Approximation) という新しいサンプル効率アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-09-30T17:59:16Z) - Scaling Structured Inference with Randomization [64.18063627155128]
本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。
我々の手法は古典的DPベースの推論に広く適用できる。
また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
論文 参考訳(メタデータ) (2021-12-07T11:26:41Z) - Transformer-based Map Matching Model with Limited Ground-Truth Data
using Transfer-Learning Approach [6.510061176722248]
多くのトラジェクトリベースのアプリケーションでは、生のGPSトラジェクトリをデジタルマップの道路網にマッピングする必要がある。
本稿では,データの観点から地図マッチングの課題を考察し,深層学習に基づく地図マッチングモデルを提案する。
合成軌道データを生成し,トランスフォーマーモデルを事前学習し,有限個の接地トラスデータでモデルを微調整する。
論文 参考訳(メタデータ) (2021-08-01T11:51:11Z) - Model-free Representation Learning and Exploration in Low-rank MDPs [64.72023662543363]
低位mdpに対して,最初のモデルフリー表現学習アルゴリズムを提案する。
主要なアルゴリズムの貢献は新しいミニマックス表現の学習の目的です。
結果は複雑な環境にスケールする一般的な関数近似を収容できます。
論文 参考訳(メタデータ) (2021-02-14T00:06:54Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳(メタデータ) (2020-02-20T10:50:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。