論文の概要: 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インスタンスの総合的なセット上で,現在の最先端のヒューリスティックソリューションに適合あるいは打ち勝つ上で極めて効率的であることが示唆された。
関連論文リスト
- Equivariant Deep Weight Space Alignment [54.65847470115314]
本稿では,ウェイトアライメント問題を解決するための学習を目的とした新しいフレームワークを提案する。
まず、重み調整が2つの基本対称性に一致することを証明し、それからこれらの対称性を尊重する深いアーキテクチャを提案する。
論文 参考訳（メタデータ） (2023-10-20T10:12:06Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
大規模言語モデルの複雑な推論能力を高めるために,textbftextitThought Propagation (TP)を提案する。
TP はまず LLM に対して,入力問題に関連する類似問題の集合を提案し,解決するよう促す。
TPは、類似問題の結果を再利用して、新しいソリューションを直接生成したり、スクラッチから得られた初期ソリューションを修正するための知識集約的な実行プランを導出する。
論文 参考訳（メタデータ） (2023-10-06T01:40:09Z) - Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle
Routing Problem with Time Windows [58.891409372784516]
本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。
RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
論文 参考訳（メタデータ） (2023-06-04T09:18:02Z) - Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path
Finding [25.11387753357413]
本稿では,多目的タスク割り当てと経路探索(MG-TAPF)問題を理論的およびアルゴリズム的観点から検討する。
理論的には、MG-TAPF問題は最適解法としてNPハードであることが証明される。
本稿では,多エージェントパス探索問題に対するアルゴリズムに基づくアルゴリズムを提案し,MG-TAPF問題を最適・準最適に解く。
論文 参考訳（メタデータ） (2022-08-02T03:17:29Z) - On the Use of Quality Diversity Algorithms for The Traveling Thief
Problem [11.590506672325668]
現実世界の最適化では、いくつかのサブプロブレムが相互作用し、主要な問題を形成するのが一般的である。
本稿では,旅行セールスパーソン問題(TSP)とクナップサック問題(KP)の相互依存性を品質多様性(QD)アプローチを用いて検討する。
論文 参考訳（メタデータ） (2021-12-16T05:08:39Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳（メタデータ） (2021-05-05T03:36:00Z) - Batch Bayesian Optimization on Permutations using Acquisition Weighted
Kernels [86.11176756341114]
決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。
本研究では,理論特性の知見を得るための後悔分析法を提案する。
二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
論文 参考訳（メタデータ） (2021-02-26T10:15:57Z) - 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) - A Non-Dominated Sorting Based Customized Random-Key Genetic Algorithm
for the Bi-Objective Traveling Thief Problem [7.088487500434561]
本稿では,よく研究されたトラベリングティーフ問題 (TTP) の2目的変種を解く方法を提案する。
BI-TTPは、旅行時間全体の最小化と、収集したアイテムの利益の最大化を目的としている。
提案手法は,問題固有の特徴をカスタマイズしたバイアスランダム鍵遺伝的アルゴリズムに基づく。
論文 参考訳（メタデータ） (2020-02-11T10:56:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。