Fugu-MT 論文翻訳(概要): On the Use of Quality Diversity Algorithms for The Traveling Thief Problem

論文の概要: On the Use of Quality Diversity Algorithms for The Traveling Thief Problem

arxiv url: http://arxiv.org/abs/2112.08627v4
Date: Wed, 4 Jan 2023 00:54:29 GMT
ステータス: 処理完了
システム内更新日: 2023-03-04 09:37:53.368197
Title: On the Use of Quality Diversity Algorithms for The Traveling Thief Problem
Title（参考訳）: 移動泥棒問題に対する品質多様性アルゴリズムの利用について
Authors: Adel Nikfarjam, Aneta Neumann, and Frank Neumann
Abstract要約: 現実世界の最適化では、いくつかのサブプロブレムが相互作用し、主要な問題を形成するのが一般的である。本稿では,旅行セールスパーソン問題(TSP)とクナップサック問題(KP)の相互依存性を品質多様性(QD)アプローチを用いて検討する。
参考スコア（独自算出の注目度）: 11.590506672325668
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. There is an inter-dependency between the sub-problems, making it impossible to solve such a problem by focusing on only one component. The traveling thief problem~(TTP) belongs to this category and is formed by the integration of the traveling salesperson problem~(TSP) and the knapsack problem~(KP). In this paper, we investigate the inter-dependency of the TSP and the KP by means of quality diversity~(QD) approaches. QD algorithms provide a powerful tool not only to obtain high-quality solutions but also to illustrate the distribution of high-performing solutions in the behavioural space. We introduce a MAP-Elite based evolutionary algorithm using well-known TSP and KP search operators, taking the TSP and KP score as the behavioural descriptor. Afterwards, we conduct comprehensive experimental studies that show the usefulness of using the QD approach applied to the TTP. First, we provide insights regarding high-quality TTP solutions in the TSP/KP behavioural space. Afterwards, we show that better solutions for the TTP can be obtained by using our QD approach and it can improve the best-known solution for a number of TTP instances used for benchmarking in the literature.
Abstract（参考訳）: 実世界の最適化では、いくつかのサブプロブレムが相互作用し、主要な問題を形成するのが一般的である。サブプロブレムの間には依存関係があり、1つのコンポーネントだけに集中してそのような問題を解決することは不可能である。旅行泥棒問題〜(TTP)はこのカテゴリーに属し、旅行セールスパーソン問題〜(TSP)とknapsack問題〜(KP)の統合によって形成される。本稿では,品質多様性~(QD)アプローチを用いて,TSPとKPの相互依存性について検討する。 QDアルゴリズムは、高品質なソリューションを得るだけでなく、振る舞い空間における高性能なソリューションの分布を示す強力なツールを提供する。我々は、よく知られたTSPとKP探索演算子を用いてMAP-Eliteに基づく進化的アルゴリズムを導入し、TSPとKPのスコアを行動記述子とする。その後,TTPに適用したQDアプローチの有用性を示す総合的な実験を行った。まず、TSP/KPの振る舞い空間における高品質なTTPソリューションに関する洞察を提供する。その後、我々のQDアプローチを用いて、TTPのより良い解を得ることができ、文献におけるベンチマークに使用される多くのTPインスタンスの最もよく知られた解を改善することができることを示す。

関連論文リスト

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)
Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
任意のOTコスト関数に対して連続的エントロピーOT(EOT)バリセンタを近似する新しいアルゴリズムを提案する。本手法は、弱いOTに基づくEOT問題の二重再構成に基づいている。
論文参考訳（メタデータ） (2023-10-02T11:24:36Z)
On Pitfalls of Test-Time Adaptation [82.8392232222119]
TTA(Test-Time Adaptation)は、分散シフトの下で堅牢性に取り組むための有望なアプローチとして登場した。 TTABは,10の最先端アルゴリズム,多種多様な分散シフト,および2つの評価プロトコルを含むテスト時間適応ベンチマークである。
論文参考訳（メタデータ） (2023-06-06T09:35:29Z)
Benchmarking the Reliability of Post-training Quantization: a Particular Focus on Worst-case Performance [53.45700148820669]
ポストトレーニング量子化(PTQ)は、独自のアーキテクチャやトレーニング手順を変更することなく、ディープニューラルネットワーク(DNN)を圧縮するための一般的な方法である。その有効性と利便性にもかかわらず、分散シフトやデータノイズといった極端ケースの存在下でのPTQ手法の信頼性は明らかにされていない。そこで本研究では,様々なPTQ手法を用いてこの問題について検討する。
論文参考訳（メタデータ） (2023-03-23T02:55:50Z)
Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning [59.14935871979047]
本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
論文参考訳（メタデータ） (2022-07-04T14:31:47Z)
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)
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)

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

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