論文の概要: The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics

• arxiv url: http://arxiv.org/abs/2002.01070v1
• Date: Tue, 4 Feb 2020 00:57:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-04 02:41:32.743631
• Title: The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics
• Title（参考訳）: ノード重み依存トラベルセールスパーソン問題:近似アルゴリズムとランダム探索ヒューリスティックス
• Authors: Jakob Bossek, Katrin Casel, Pascal Kerschke and Frank Neumann
• Abstract要約: 車両経路の領域におけるいくつかの重要な最適化問題は、古典的旅行セールスパーソン問題(TSP)の変種と見なすことができる。 本稿では,ツアー中に訪れたノードの重みに関して,旅行コストが増大するという意味で,ウェイトがそのような問題に与える影響について検討する。
• 参考スコア（独自算出の注目度）: 10.946271021892922
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several important optimization problems in the area of vehicle routing can be seen as a variant of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the traveling thief problem (TTP) has gained increasing interest over the last 5 years. In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour. This provides abstractions of important TSP variants such as the Traveling Thief Problem and time dependent TSP variants, and allows to study precisely the increase in difficulty caused by weight dependence. We provide a 3.59-approximation for this weight dependent version of TSP with metric distances and bounded positive weights. Furthermore, we conduct experimental investigations for simple randomized local search with classical mutation operators and two variants of the state-of-the-art evolutionary algorithm EAX adapted to the weighted TSP. Our results show the impact of the node weights on the position of the nodes in the resulting tour.
• Abstract（参考訳）: 車両経路の領域におけるいくつかの重要な最適化問題は、古典的旅行販売問題(TSP)の変種と見なすことができる。 進化計算の分野では,過去5年間で旅行盗難問題(TTP)の関心が高まっている。 本稿では,旅行中に訪れたノードの重みに対して移動コストが増加するという観点から,このような問題に対する重みの影響について検討する。 これにより、トラベリング・ティーフ問題や時間依存のTSP変種といった重要なTSP変種を抽象化し、重量依存による難易度の増加を正確に研究することができる。 計量距離と有界正の重みを持つTSPのこの重み依存バージョンに対する3.59近似を提供する。 さらに、古典的突然変異演算子と、重み付きTSPに適応した最先端進化アルゴリズムEAXの2つの変種を用いて、単純なランダム化局所探索実験を行った。 その結果,ノード重みがツアー中のノードの位置に与える影響が示唆された。

関連論文リスト

• On the Impact of Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem [13.026567958569965]
  動的環境におけるノード重み付け販売員問題(W-TSP)について検討する。 問題の動的設定では、時間とともにTSPツアーの一部として収集されるアイテムが変更される。 最初の実験では,このような変化がツアーの最適化に与える影響について検討した。
  論文  参考訳（メタデータ） (2023-05-30T11:39:49Z)
• Neural Functional Transformers [99.98750156515437]
  本稿では,ニューラルファンクショナルトランスフォーマー (NFT) と呼ばれる新しい変分同変量空間層を定義するために,アテンション機構を用いる。 NFTは重み空間の置換対称性を尊重し、注意の利点を取り入れ、複数の領域で顕著な成功を収めた。 Inr2Arrayは暗黙的ニューラル表現(INR)の重みから置換不変表現を計算する新しい方法である。
  論文  参考訳（メタデータ） (2023-05-22T23:38:27Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• SRRT: Exploring Search Region Regulation for Visual Object Tracking [58.68120400180216]
  探索領域規則追跡(SRRT)と呼ばれる新しい追跡パラダイムを提案する。 SRRTでは,各フレームに対して最適な探索領域を動的に推定するために,提案された探索領域レギュレータを適用している。 大規模なLaSOTベンチマークでは、SRRTはSiamRPN++とTransTをAUCの4.6%と3.1%で改善した。
  論文  参考訳（メタデータ） (2022-07-10T11:18:26Z)
• Averaging Spatio-temporal Signals using Optimal Transport and Soft Alignments [110.79706180350507]
  Fr'teche は双対性を意味し, 時間的バレシェセンタを定義するために提案した損失が有効であることを示す。 手書き文字と脳画像データによる実験は、我々の理論的発見を裏付けるものである。
  論文  参考訳（メタデータ） (2022-03-11T09:46:22Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  最適輸送のためのニューラルネットワークに基づく解法の性能を評価する。 既存の解法では,下流タスクでは良好に機能するにもかかわらず,最適な輸送マップを復元できないことがわかった。
  論文  参考訳（メタデータ） (2021-06-03T15:59:28Z)
• The Implicit Biases of Stochastic Gradient Descent on Deep Neural Networks with Batch Normalization [44.30960913470372]
  バッチ正規化(BN-DNN)を伴うディープニューラルネットワークは、その正規化操作のために重み付け再スケーリングには不変である。 BN-DNNにおける勾配降下(SGD)の暗黙バイアスについて検討し,重量減衰の有効性に関する理論的説明を行う。
  論文  参考訳（メタデータ） (2021-02-06T03:40:20Z)
• Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation [8.620967398331265]
  旅行泥棒問題(TTP)は多くの学者を引き付ける挑戦的な最適化問題です。 本論文では,TTPを理論的および実証的に検討する。 提案した選択項目と逆順序のソート項目の定式化によって算出されたスコア値に基づくアルゴリズムを提案し,この問題を解く。
  論文  参考訳（メタデータ） (2020-12-16T12:06:05Z)
• Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions [13.026567958569965]
  トラベリング・ティーフ問題(TTP)は、2つの最適化問題を組み合わせることでそのような相互作用に対処する。 ノードウェイト依存トラベリングセールスパーソン問題(W-TSP)と呼ばれる新しい問題が導入され、ノードがツアーのコストに影響を与える重みを持つ。 W-TSP と TTP の最適ツアーの構造と適合度関数の相互利用の影響について検討した。
  論文  参考訳（メタデータ） (2020-06-05T07:07:28Z)
• Surrogate Assisted Optimisation for Travelling Thief Problems [14.836145520657592]
  トラベリング泥棒問題(TTP)は、2つの相互依存NPハードコンポーネントを含む多成分最適化問題である。 最近の最先端TTP解法は、根底にあるTPとKPの解を反復的かつインターリーブ的に修正している。 そこで本研究では,TTP ソリューションに繋がる初期 TSP ツアーの特徴を学習する適応的サロゲートモデルにより,探索をより効率的にすることを提案する。
  論文  参考訳（メタデータ） (2020-05-14T02:49:16Z)
• Revisiting Initialization of Neural Networks [72.24615341588846]
  ヘッセン行列のノルムを近似し, 制御することにより, 層間における重みのグローバルな曲率を厳密に推定する。 Word2Vec と MNIST/CIFAR 画像分類タスクの実験により,Hessian ノルムの追跡が診断ツールとして有用であることが確認された。
  論文  参考訳（メタデータ） (2020-04-20T18:12:56Z)

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

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