論文の概要: Surrogate Assisted Optimisation for Travelling Thief Problems
- arxiv url: http://arxiv.org/abs/2005.06695v1
- Date: Thu, 14 May 2020 02:49:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-03 05:24:31.393108
- Title: Surrogate Assisted Optimisation for Travelling Thief Problems
- Title（参考訳）: 旅行泥棒問題に対するsurrogateの最適化支援
- Authors: Majid Namazi, Conrad Sanderson, M.A. Hakim Newton, Abdul Sattar
- Abstract要約: トラベリング泥棒問題(TTP)は、2つの相互依存NPハードコンポーネントを含む多成分最適化問題である。
最近の最先端TTP解法は、根底にあるTPとKPの解を反復的かつインターリーブ的に修正している。
そこで本研究では,TTP ソリューションに繋がる初期 TSP ツアーの特徴を学習する適応的サロゲートモデルにより,探索をより効率的にすることを提案する。
- 参考スコア（独自算出の注目度）: 14.836145520657592
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The travelling thief problem (TTP) is a multi-component optimisation problem
involving two interdependent NP-hard components: the travelling salesman
problem (TSP) and the knapsack problem (KP). Recent state-of-the-art TTP
solvers modify the underlying TSP and KP solutions in an iterative and
interleaved fashion. The TSP solution (cyclic tour) is typically changed in a
deterministic way, while changes to the KP solution typically involve a random
search, effectively resulting in a quasi-meandering exploration of the TTP
solution space. Once a plateau is reached, the iterative search of the TTP
solution space is restarted by using a new initial TSP tour. We propose to make
the search more efficient through an adaptive surrogate model (based on a
customised form of Support Vector Regression) that learns the characteristics
of initial TSP tours that lead to good TTP solutions. The model is used to
filter out non-promising initial TSP tours, in effect reducing the amount of
time spent to find a good TTP solution. Experiments on a broad range of
benchmark TTP instances indicate that the proposed approach filters out a
considerable number of non-promising initial tours, at the cost of omitting
only a small number of the best TTP solutions.
- Abstract（参考訳）: トラベリング泥棒問題 (TTP) は、トラベリングセールスマン問題 (TSP) とクナップサック問題 (KP) の2つの独立したNPハードコンポーネントを含む多成分最適化問題である。
最近の最先端TTP解法は、根底にあるTSPとKPの解を反復的かつインターリーブ的に修正している。
TSP解(巡回巡回)は典型的には決定論的に変化するが、KP解の変更は通常ランダムな探索を伴い、事実上TTP解空間の準蛇行的な探索をもたらす。
台地に達すると、新しい初期TSPツアーを用いて、TPソリューション空間の反復探索を再開する。
本稿では,適切なTTPソリューションをもたらす初期TSPツアーの特徴を学習するアダプティブサロゲートモデル(Support Vector Regressionのカスタマイズ形式に基づく)により,検索をより効率的にすることを提案する。
このモデルは、プロムしない初期のTSPツアーをフィルタリングするために使用され、結果として優れたTTPソリューションを見つけるのに要する時間を削減する。
幅広いベンチマークTTPインスタンスの実験から、提案手法は、最も優れたTTPソリューションのごく一部を省略するコストで、かなりの数の初期ツアーをフィルタリングすることを示している。
関連論文リスト
- Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem [12.34897099691387]
本稿では,旅行セールスマン問題(TSP)の学習方法を提案する。
1対1のピックアップ・アンド・デリバリノードのシーケンスで一番短いツアーを見つける。
PDTSPでは、各ピックアップノードを対応する配信ノードの前に訪問しなければならないという優先的な制約を満たさなければならない。
論文 参考訳（メタデータ） (2024-04-17T15:05:51Z) - Semi-Supervised Coupled Thin-Plate Spline Model for Rotation Correction and Beyond [84.56978780892783]
制御点が限られている複数のTPSを、より柔軟で強力な変換に繰り返し結合するCoupledTPSを提案する。
注記コストを考慮に入れた半教師付き学習手法を開発し、ラベルのないデータを活用することにより、ワープ品質を向上させる。
実験は、回転補正のための既存の最先端解よりもCoupledTPSの優位性と普遍性を示す。
論文 参考訳（メタデータ） (2024-01-24T13:03:28Z) - 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) - Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem [67.32731657297377]
トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。
近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。
本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
論文 参考訳（メタデータ） (2023-04-19T03:48:32Z) - Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
本稿では,連続確率分布間のエントロピー最適輸送(EOT)計画を計算するための新しいアルゴリズムを提案する。
提案アルゴリズムは,シュリンガーブリッジ問題(Schr"odinger Bridge problem)として知られるEOTの動的バージョンのサドル点再構成に基づく。
大規模EOTの従来の手法とは対照的に,我々のアルゴリズムはエンドツーエンドであり,単一の学習ステップで構成されている。
論文 参考訳（メタデータ） (2022-11-02T14:35:13Z) - Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning [59.14935871979047]
本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。
これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
論文 参考訳（メタデータ） (2022-07-04T14:31:47Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。