論文の概要: Solving the Travelling Thief Problem based on Item Selection Weight and
Reverse Order Allocation
- arxiv url: http://arxiv.org/abs/2012.08888v1
- Date: Wed, 16 Dec 2020 12:06:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-04 13:29:43.733327
- Title: Solving the Travelling Thief Problem based on Item Selection Weight and
Reverse Order Allocation
- Title(参考訳): 商品選択重量と逆順序割当に基づく旅行泥棒問題の解法
- Authors: Lei Yang, Zitong Zhang, Xiaotian Jia, Peipei Kang, Wensheng Zhang,
Dongya Wang
- Abstract要約: 旅行泥棒問題(TTP)は多くの学者を引き付ける挑戦的な最適化問題です。
本論文では,TTPを理論的および実証的に検討する。
提案した選択項目と逆順序のソート項目の定式化によって算出されたスコア値に基づくアルゴリズムを提案し,この問題を解く。
- 参考スコア(独自算出の注目度): 8.620967398331265
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Travelling Thief Problem (TTP) is a challenging combinatorial
optimization problem that attracts many scholars. The TTP interconnects two
well-known NP-hard problems: the Travelling Salesman Problem (TSP) and the 0-1
Knapsack Problem (KP). Increasingly algorithms have been proposed for solving
this novel problem that combines two interdependent sub-problems. In this
paper, TTP is investigated theoretically and empirically. An algorithm based on
the score value calculated by our proposed formulation in picking items and
sorting items in the reverse order in the light of the scoring value is
proposed to solve the problem. Different approaches for solving the TTP are
compared and analyzed; the experimental investigations suggest that our
proposed approach is very efficient in meeting or beating current
state-of-the-art heuristic solutions on a comprehensive set of benchmark TTP
instances.
- Abstract(参考訳): トラベリング・ティーフ問題(TTP)は、多くの学者を惹きつける組合せ最適化問題である。
TTPは、トラベルセールスマン問題(TSP)と0-1クナップサック問題(KP)の2つのよく知られたNPハード問題を相互接続している。
2つの相互依存サブプロブレムを組み合わせた新しい問題の解法が提案されている。
本稿では,TTPを理論的,実証的に検討する。
提案手法は,提案手法によって算出されたスコア値に基づいて,スコア値に照らして,逆順にアイテムを並べ替える手法を提案する。
実験により,提案手法はベンチマークTTPインスタンスの総合的なセット上で,現在の最先端のヒューリスティックソリューションに適合あるいは打ち勝つ上で極めて効率的であることが示唆された。
関連論文リスト
- On the Convergence of Momentum-Based Algorithms for Federated Stochastic
Bilevel Optimization Problems [22.988563731766586]
特に,このような問題を最適化するための運動量に基づく2つのアルゴリズムを開発した。
我々はこれらの2つのアルゴリズムの収束率を確立し、それらのサンプルと通信の複雑さを提供した。
論文 参考訳(メタデータ) (2022-04-28T06:14:21Z) - A deep learning method for solving stochastic optimal control problems
driven by fully-coupled FBSDEs [0.2064612766965483]
本稿では,完全結合前方微分方程式(FBSDEs,略してFBSDEs)によって駆動される高次元最適制御問題の,ディープラーニングによる数値解に着目した。
まず,この問題をStackelberg差分ゲーム(リーダ・フォロワー問題)に変換し,リーダーのコスト関数と追従者のコストがディープニューラルネットワークを介して最適化されるクロス最適化手法(COCO法)を開発する。
数値的な結果については,実用新案による投資消費問題の2つの例を計算し,両例が有効であることを示す。
論文 参考訳(メタデータ) (2022-04-12T13:31:19Z) - Instance-Dependent Confidence and Early Stopping for Reinforcement
Learning [99.57168572237421]
強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。
この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。
次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
論文 参考訳(メタデータ) (2022-01-21T04:25:35Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳(メタデータ) (2022-01-05T13:37:27Z) - Achievability and Impossibility of Exact Pairwise Ranking [1.0878040851638]
雑音のあるペアワイズ比較に基づいて,$n$アイテムのランクを回復する問題を考察する。
本分析では, パラメトリック限界と正確に一致した, 正確な要件に対して, 情報理論上および下限の鋭い情報を与えた。
論文 参考訳(メタデータ) (2021-11-19T03:16:29Z) - On the Convergence of Projected Alternating Maximization for Equitable
and Optimal Transport [36.97843660480747]
本稿では,多くの応用例を有する等価・最適輸送(EOT)問題について検討する。
離散分布の場合、EOT問題は線形プログラム(LP)として定式化できる。
このLPは一般解法では禁止的に大きいため、Scetbon etal citescetbonequitable はエントロピー正則化を加えることによって問題を摂動することを示唆している。
彼らは、エントロピー正規化EOTの双対を解くための予測交互化アルゴリズム(PAM)を提案した。
論文 参考訳(メタデータ) (2021-09-29T04:32:06Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳(メタデータ) (2021-07-15T02:13:03Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳(メタデータ) (2021-05-05T03:36:00Z) - PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective
Optimization Problems [0.0]
提案アルゴリズムは,実モデルのモデルによって定義される一連の代理問題の解法に基づく。
また,最適化ランドスケープのための最適なサロゲートモデルとナビゲーション戦略のメタ検索を行う。
論文 参考訳(メタデータ) (2021-03-19T11:18:03Z) - Batch Bayesian Optimization on Permutations using Acquisition Weighted
Kernels [86.11176756341114]
決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。
本研究では,理論特性の知見を得るための後悔分析法を提案する。
二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
論文 参考訳(メタデータ) (2021-02-26T10:15:57Z) - Generalization in portfolio-based algorithm selection [97.74604695303285]
ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。
ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
論文 参考訳(メタデータ) (2020-12-24T16:33:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。