論文の概要: Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights

• arxiv url: http://arxiv.org/abs/2102.05778v1
• Date: Wed, 10 Feb 2021 23:40:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-12 00:31:39.821170
• Title: Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights
• Title（参考訳）: 確率制約ナップサック問題に対する rls と (1+1) ea の実行時間解析
• Authors: Yue Xie, Aneta Neumann, Frank Neumann, Andrew M. Sutton
• Abstract要約: 本研究では,ランダム化探索アルゴリズム (RSA) と基本進化アルゴリズム (EA) のランタイム解析を行った。 本稿では,重み相関と異なる種類の利益プロファイルが,確率制約条件下での両アルゴリズムの実行動作にどのように影響するかを示す。
• 参考スコア（独自算出の注目度）: 15.402666674186936
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Addressing a complex real-world optimization problem is a challenging task. The chance-constrained knapsack problem with correlated uniform weights plays an important role in the case where dependent stochastic components are considered. We perform runtime analysis of a randomized search algorithm (RSA) and a basic evolutionary algorithm (EA) for the chance-constrained knapsack problem with correlated uniform weights. We prove bounds for both algorithms for producing a feasible solution. Furthermore, we investigate the behavior of the algorithms and carry out analyses on two settings: uniform profit value and the setting in which every group shares an arbitrary profit profile. We provide insight into the structure of these problems and show how the weight correlations and the different types of profit profiles influence the runtime behavior of both algorithms in the chance-constrained setting.
• Abstract（参考訳）: 複雑な実世界の最適化問題に対処するのは難しい課題です。 一致した一様重みを持つ確率制約クナプサック問題は、従属確率成分が考慮される場合において重要な役割を果たす。 確率的探索アルゴリズム(rsa)と基本進化アルゴリズム(ea)のランタイム解析を行い,一様重みが相関する確率制約ナップサック問題を解く。 両アルゴリズムが実現可能な解を生成するための境界を証明します。 さらに,アルゴリズムの挙動を調査し,一様利益値と各グループが任意の利益プロファイルを共有する設定の2つの設定で分析を行う。 これらの問題の構造について考察し,確率制約条件下での重み相関と利益プロファイルの違いが両アルゴリズムの動作にどのように影響するかを示す。

関連論文リスト

• Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications [38.98556852157875]
  ランダムな重みの確率分布が未知であるがサンプルデータのみが利用可能であるCCMCKPの実践シナリオに注目した。 CCMCKPを解決するために,データ駆動型適応局所探索(DDALS)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-26T13:35:05Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem [12.791789710379057]
  本稿では,Makespan Scheduling問題の確率制約版を提案する。 古典的ランダム化局所探索と (1+1) EAの理論的性能について検討する。 具体的には、Chance-Constrained Makespan Scheduling問題の2つの変種とその計算複雑性について検討する。
  論文  参考訳（メタデータ） (2022-12-22T04:31:23Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Stochastic Constrained DRO with a Complexity Independent of Sample Size [38.56406595022129]
  クルバック分散制約DRO問題の解法として,非凸損失と凸損失の両方に適用可能なアルゴリズムを提案し,解析する。 非損失に対する$$$ilon定常解を見つけるのにほぼ最適な複雑さを確立し、広いアプリケーションに最適な解を求めるのに最適なバッチの複雑さを確立します。
  論文  参考訳（メタデータ） (2022-10-11T19:11:19Z)
• Analysis of Quality Diversity Algorithms for the Knapsack Problem [14.12876643502492]
  我々は,knapsack問題における動的プログラミング動作のシミュレーションにQDパラダイムを適用した。 予測された擬似ポリノミカル時間内に最適解を計算することができることを示す。
  論文  参考訳（メタデータ） (2022-07-28T12:15:33Z)
• Evolutionary Algorithms for Limiting the Effect of Uncertainty for the Knapsack Problem with Stochastic Profits [14.352521012951865]
  我々は、利益が不確実性を伴うクナプサック問題を考察する。 我々は、不確実性の影響を制限するために、尾の不平等に基づいて利益を扱う様々な方法を導入する。
  論文  参考訳（メタデータ） (2022-04-12T07:56:50Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。 これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2022-03-14T15:21:18Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。 この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。 次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
  論文  参考訳（メタデータ） (2022-01-21T04:25:35Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)

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

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