論文の概要: Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum

• arxiv url: http://arxiv.org/abs/2204.03236v1
• Date: Thu, 7 Apr 2022 05:59:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-08 14:13:01.033409
• Title: Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum
• Title（参考訳）: ハードネス適応型カリキュラムを用いたトラベリングセールスマン問題の解法
• Authors: Zeyang Zhang, Ziwei Zhang, Xin Wang, Wenwu Zhu
• Abstract要約: 本稿では,既存手法の10倍の精度でインスタンスを生成するハードネス適応型ジェネレータを提案する。 提案手法は, 最適性ギャップの観点から, 最先端モデルに対する大幅な改善を実現する。
• 参考スコア（独自算出の注目度）: 42.28343071442175
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Various neural network models have been proposed to tackle combinatorial optimization problems such as the travelling salesman problem (TSP). Existing learning-based TSP methods adopt a simple setting that the training and testing data are independent and identically distributed. However, the existing literature fails to solve TSP instances when training and testing data have different distributions. Concretely, we find that different training and testing distribution will result in more difficult TSP instances, i.e., the solution obtained by the model has a large gap from the optimal solution. To tackle this problem, in this work, we study learning-based TSP methods when training and testing data have different distributions using adaptive-hardness, i.e., how difficult a TSP instance can be for a solver. This problem is challenging because it is non-trivial to (1) define hardness measurement quantitatively; (2) efficiently and continuously generate sufficiently hard TSP instances upon model training; (3) fully utilize instances with different levels of hardness to learn a more powerful TSP solver. To solve these challenges, we first propose a principled hardness measurement to quantify the hardness of TSP instances. Then, we propose a hardness-adaptive generator to generate instances with different hardness. We further propose a curriculum learner fully utilizing these instances to train the TSP solver. Experiments show that our hardness-adaptive generator can generate instances ten times harder than the existing methods, and our proposed method achieves significant improvement over state-of-the-art models in terms of the optimality gap.
• Abstract（参考訳）: 旅行セールスマン問題(TSP)のような組合せ最適化問題に対処するために,様々なニューラルネットワークモデルが提案されている。 既存の学習ベースのTSP手法は、トレーニングデータとテストデータが独立して同一に分散されているという単純な設定を採用する。 しかし、既存の文献では、トレーニングやテストデータが異なる分布を持つ場合、TSPインスタンスを解決できない。 具体的には、異なるトレーニングとテストの分布がより難しいTSPインスタンスをもたらすこと、すなわち、モデルによって得られる解は最適解と大きなギャップを持つ。 この問題に対処するため、本研究では、適応硬度を用いてデータが異なる分布を持つ場合、すなわち、TSPインスタンスが解き手にとっていかに困難であるかを学習ベースのTSP手法について検討する。 この問題は,(1) 硬度測定を定量的に定義することが自明ではないこと,(2) モデルトレーニング時に十分な硬度TSPインスタンスを効率よく連続的に生成すること,(3) より強力なTSPソルバを学習するために,異なる硬度を持つインスタンスを十分に活用すること,などが問題となっている。 これらの課題を解決するために,まずTSPインスタンスの硬さを定量化する原理的硬さ測定法を提案する。 次に,硬度が異なるインスタンスを生成するための硬度適応型生成器を提案する。 さらに、これらのインスタンスをフル活用してTSPソルバを訓練するカリキュラム学習者を提案する。 実験により,本手法は既存手法の10倍の難易度でインスタンスを生成することができ,提案手法は最適性ギャップの点で最先端モデルよりも大幅に改善できることを示した。

関連論文リスト

• Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problem [36.88003015541172]
  そこで本稿では,TSP と Time Windows (TSPTW) の正当性を改善するために,ルックアヘッド情報を用いた新しい学習手法を提案する。 多様なデータセットに関する包括的な実験により、MUSLAは既存のベースラインを上回り、一般化可能性を示す。
  論文  参考訳（メタデータ） (2024-03-08T13:49:21Z)
• On Pitfalls of Test-Time Adaptation [82.8392232222119]
  TTA(Test-Time Adaptation)は、分散シフトの下で堅牢性に取り組むための有望なアプローチとして登場した。 TTABは,10の最先端アルゴリズム,多種多様な分散シフト,および2つの評価プロトコルを含むテスト時間適応ベンチマークである。
  論文  参考訳（メタデータ） (2023-06-06T09:35:29Z)
• Unsupervised Training for Neural TSP Solver [2.9398911304923447]
  本稿では,トラベリングセールスマン問題を解決するための教師なし学習手法を提案する。 我々は、TSPの整数線型プログラムを緩和して、正しいインスタンスラベルを必要としない損失関数を構築する。 私たちのアプローチは、強化学習よりも安定しており、トレーニングも簡単です。
  論文  参考訳（メタデータ） (2022-07-27T17:33:29Z)
• Dynamic Contrastive Distillation for Image-Text Retrieval [90.05345397400144]
  画像テキスト検索モデルを圧縮するための新しいプラグイン動的コントラスト蒸留(DCD)フレームワークを提案する。 提案したDCD戦略を2つの最先端の視覚言語事前訓練モデル、すなわち ViLT と METER に適用することに成功している。 MS-COCOとFlickr30Kベンチマークの実験では、DCDフレームワークの有効性と効率が示されている。
  論文  参考訳（メタデータ） (2022-07-04T14:08:59Z)
• Efficient Test-Time Model Adaptation without Forgetting [60.36499845014649]
  テストタイム適応は、トレーニングとテストデータの間の潜在的な分散シフトに取り組むことを目指している。 信頼性および非冗長なサンプルを同定するためのアクティブなサンプル選択基準を提案する。 また、重要なモデルパラメータを劇的な変化から制約するFisher regularizerを導入します。
  論文  参考訳（メタデータ） (2022-04-06T06:39:40Z)
• Learning Mixtures of Linear Dynamical Systems [94.49754087817931]
  そこで我々は,2段階のメタアルゴリズムを開発し,各基底構造LPSモデルを誤り$tildeO(sqrtd/T)$.sqrtd/T)まで効率的に復元する。 提案手法の有効性を検証し,数値実験による理論的研究を検証する。
  論文  参考訳（メタデータ） (2022-01-26T22:26:01Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  トラベリングセールスマン問題(TSP)は古典的な最適化問題である。 ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。 本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2020-10-23T07:37:16Z)
• Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation [120.69747175899421]
  ワッサーシュタインのような最適輸送(OT)距離は、GANやドメイン適応のようないくつかの領域で使用されている。 本稿では,現代のディープラーニングアプリケーションに適用可能な,ロバストなOT最適化の計算効率のよい2つの形式を提案する。 提案手法では, ノイズの多いデータセット上で, 外部分布で劣化したGANモデルをトレーニングすることができる。
  論文  参考訳（メタデータ） (2020-10-12T17:13:40Z)
• Towards Feature-free TSP Solver Selection: A Deep Learning Approach [35.05032046810422]
  トラベリングセールスマン問題(TSP)は古典的なNPハード問題であり、多くの分野や産業で広く応用されている。 本稿では,TSPソルバ選択のためのディープラーニングフレームワークであるCTASを提案する。
  論文  参考訳（メタデータ） (2020-06-01T04:48:36Z)
• Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems [5.370742369840518]
  機械学習モデルでは、最適解の一部ではないと予測される最適化問題から決定変数を強引に除去できることを示す。 1) 問題の特徴,2) 問題のサイズ,3) 問題タイプ。 未使用変数の予測精度は、テストインスタンスがトレーニングセットからさらに離れているため、自然に劣化するが、異なるTSP問題でテストしても、機械学習モデルは有用な予測を行う。
  論文  参考訳（メタデータ） (2020-05-12T15:09:20Z)

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

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