論文の概要: Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection

• arxiv url: http://arxiv.org/abs/2005.13289v1
• Date: Wed, 27 May 2020 11:36:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-28 09:06:54.328317
• Title: Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection
• Title（参考訳）: 不正確なTSP解の随時挙動と自動アルゴリズム選択の展望
• Authors: Jakob Bossek and Pascal Kerschke and Heike Trautmann
• Abstract要約: トラベリング・サレスパーソン・プロブレム(TSP)は、最もよく知られたNPハード最適化問題の1つである。 我々は、不正確なTSPソルバの任意の動作に対処することで、既存のベンチマーク研究を拡張した。 その結果、解法の性能ランキングは、集中した近似品質に大きく依存していることが判明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling-Salesperson-Problem (TSP) is arguably one of the best-known NP-hard combinatorial optimization problems. The two sophisticated heuristic solvers LKH and EAX and respective (restart) variants manage to calculate close-to optimal or even optimal solutions, also for large instances with several thousand nodes in reasonable time. In this work we extend existing benchmarking studies by addressing anytime behaviour of inexact TSP solvers based on empirical runtime distributions leading to an increased understanding of solver behaviour and the respective relation to problem hardness. It turns out that performance ranking of solvers is highly dependent on the focused approximation quality. Insights on intersection points of performances offer huge potential for the construction of hybridized solvers depending on instance features. Moreover, instance features tailored to anytime performance and corresponding performance indicators will highly improve automated algorithm selection models by including comprehensive information on solver quality.
• Abstract（参考訳）: travel-salesperson-problem (tsp) はnp-hard combinatorial optimizationの最もよく知られた問題の1つである。 2つの洗練されたヒューリスティック解法 LKH と EAX とそれぞれの(再起動)変種は、数千のノードを持つ大規模インスタンスに対しても、最適もしくは最適な解を計算する。 本研究では,経験的ランタイム分布に基づく不正確なtspソルバの時間的挙動に対処し,既存のベンチマーク研究を拡張することにより,ソルバの動作と問題の難易度との関係について理解を深める。 その結果,解法の性能ランキングは集中近似の品質に大きく依存していることが判明した。 性能の交差点点に関する洞察は、インスタンスの特徴に応じてハイブリダイズされたソルバを構築する大きな可能性をもたらす。 さらに、インスタンス機能とそれに対応するパフォーマンスインジケータは、解法の品質に関する包括的な情報を含むことによって、アルゴリズムの自動選択モデルを大幅に改善する。

関連論文リスト

• Switchable Decision: Dynamic Neural Generation Networks [98.61113699324429]
  本稿では,各データインスタンスのリソースを動的に割り当てることで,推論を高速化するスイッチブルな決定を提案する。 提案手法は, 同一の精度を維持しながら, 推論時のコスト低減に有効である。
  論文  参考訳（メタデータ） (2024-05-07T17:44:54Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Learning to repeatedly solve routing problems [5.08128537391027]
  データのマイナーチェンジ後に問題の再最適化について学習した。 元のソリューションのエッジを考慮すれば、最適なソリューションに留まる確率の高いソリューションを予測し、修正することが目標です。 この解の偏差予測は問題の複雑さを減らし、解を高速化する。
  論文  参考訳（メタデータ） (2022-12-15T19:33:54Z)
• Learning to Schedule Heuristics for the Simultaneous Stochastic Optimization of Mining Complexes [2.538209532048867]
  提案したL2P(Learning-to-perturb)ハイパーヒューリスティックは,マルチ隣り合うシミュレートアニールアルゴリズムである。 L2Pは、効率、堅牢性、一般化能力に重点を置いて、いくつかの実世界の鉱業施設で試験されている。 その結果,反復回数を30～50%削減し,計算時間を30～45%削減した。
  論文  参考訳（メタデータ） (2022-02-25T18:20:14Z)
• Learning Hard Optimization Problems: A Data Generation Perspective [44.4747903763245]
  本稿では,トレーニングデータのボラティリティと,それを近似する能力について述べる。 そこで本研究では,教師付きタスクに対処可能な最適化問題に対して,(実際にあるいは近似的に)解を生成(生成)する方法を提案する。
  論文  参考訳（メタデータ） (2021-06-04T17:03:44Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  未知パラメータで最適化問題を解くには、未知パラメータの値を予測し、これらの値を用いて問題を解くための予測モデルを学ぶ必要がある。 最近の研究によると、複雑なトレーニングモデルパイプラインのレイヤーとして最適化の問題を含めると、観測されていない意思決定の繰り返しを予測することになる。 我々は,大規模最適化問題の低次元サロゲートモデルを学習することにより,解の質を向上させることができることを示す。
  論文  参考訳（メタデータ） (2020-06-18T19:11:54Z)

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

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