論文の概要: Analysis of Quality Diversity Algorithms for the Knapsack Problem

• arxiv url: http://arxiv.org/abs/2207.14037v1
• Date: Thu, 28 Jul 2022 12:15:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-29 12:10:13.418966
• Title: Analysis of Quality Diversity Algorithms for the Knapsack Problem
• Title（参考訳）: Knapsack問題に対する品質多様性アルゴリズムの解析
• Authors: Adel Nikfarjam, Anh Viet Do, Frank Neumann
• Abstract要約: 我々は,knapsack問題における動的プログラミング動作のシミュレーションにQDパラダイムを適用した。 予測された擬似ポリノミカル時間内に最適解を計算することができることを示す。
• 参考スコア（独自算出の注目度）: 14.12876643502492
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quality diversity (QD) algorithms have been shown to be very successful when dealing with problems in areas such as robotics, games and combinatorial optimization. They aim to maximize the quality of solutions for different regions of the so-called behavioural space of the underlying problem. In this paper, we apply the QD paradigm to simulate dynamic programming behaviours on knapsack problem, and provide a first runtime analysis of QD algorithms. We show that they are able to compute an optimal solution within expected pseudo-polynomial time, and reveal parameter settings that lead to a fully polynomial randomised approximation scheme (FPRAS). Our experimental investigations evaluate the different approaches on classical benchmark sets in terms of solutions constructed in the behavioural space as well as the runtime needed to obtain an optimal solution.
• Abstract（参考訳）: 品質多様性(qd)アルゴリズムは、ロボット工学、ゲーム、組合せ最適化といった分野の問題に対処する際に非常に成功することが示されている。 彼らは、基盤となる問題のいわゆる行動空間の異なる領域に対するソリューションの品質を最大化することを目指している。 本稿では,knapsack問題における動的プログラミング動作のシミュレーションにQDパラダイムを適用し,QDアルゴリズムの最初の実行時解析を行う。 予測された擬似多項式時間内に最適解を計算できることを示し、完全な多項式ランダム化近似スキーム(FPRAS)につながるパラメータ設定を明らかにする。 実験により,古典的なベンチマークセットに対する様々なアプローチを,行動空間に構築されたソリューションと,最適解を得るために必要なランタイムの観点から評価した。

関連論文リスト

• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。 このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
  論文  参考訳（メタデータ） (2024-07-29T13:54:28Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Don't Bet on Luck Alone: Enhancing Behavioral Reproducibility of Quality-Diversity Solutions in Uncertain Domains [2.639902239625779]
  アーカイブ再現性向上アルゴリズム(ARIA)を紹介する。 ARIAは、アーカイブに存在するソリューションの品質を改善するプラグイン・アンド・プレイのアプローチである。 提案アルゴリズムは,任意のアーカイブの品質とディスクリプタ空間のカバレッジを少なくとも50%向上させることを示す。
  論文  参考訳（メタデータ） (2023-04-07T14:45:14Z)
• Doubly Stochastic Matrix Models for Estimation of Distribution Algorithms [2.28438857884398]
  本稿では,自然置換問題のマッチングと割当てにDSM(Douubly Matrices)を用いる方法について検討する。 具体的には、分散アルゴリズムの推定の枠組みを採用し、DSMを置換問題に対する既存の提案と比較する。 二次代入問題の事例に関する予備実験は、この研究の行を検証し、DSMが非常に競争力のある結果が得られることを示した。
  論文  参考訳（メタデータ） (2023-04-05T14:36:48Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。 凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。 切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
  論文  参考訳（メタデータ） (2023-03-28T01:30:40Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints [13.896724650508087]
  古典的knapsack問題に対する単目的・多目的ベースライン進化アルゴリズムについて検討する。 この結果から, 動的変化を考慮に入れた集団を用いた多目的アプローチは, 多くのベンチマークシナリオにおいて明らかな優位性を有することが示された。
  論文  参考訳（メタデータ） (2020-04-27T03:50:24Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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