論文の概要: Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives

• arxiv url: http://arxiv.org/abs/2002.06766v1
• Date: Mon, 17 Feb 2020 04:36:15 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-31 12:28:15.658653
• Title: Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives
• Title（参考訳）: 末尾拘束目標に基づく動的確率制約ナップサック問題の進化的二目的最適化
• Authors: Hirad Assimi, Oscar Harper, Yue Xie, Aneta Neumann, Frank Neumann
• Abstract要約: 本稿では,各項目の重みが容量制約の対象となる動的チャンス制約knapsack問題について考察する。 目的は、総重量がキャパシティを超える確率に基づく総利益を最大化することである。 与えられた解に対する最小限のキャパシティを見積もる追加の目的を導入する。
• 参考スコア（独自算出の注目度）: 12.634782111072585
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Real-world combinatorial optimization problems are often stochastic and dynamic. Therefore, it is essential to make optimal and reliable decisions with a holistic approach. In this paper, we consider the dynamic chance-constrained knapsack problem where the weight of each item is stochastic, the capacity constraint changes dynamically over time, and the objective is to maximize the total profit subject to the probability that total weight exceeds the capacity. We make use of prominent tail inequalities such as Chebyshev's inequality, and Chernoff bound to approximate the probabilistic constraint. Our key contribution is to introduce an additional objective which estimates the minimal capacity bound for a given stochastic solution that still meets the chance constraint. This objective helps to cater for dynamic changes to the stochastic problem. We apply single- and multi-objective evolutionary algorithms to the problem and show how bi-objective optimization can help to deal with dynamic chance-constrained problems.
• Abstract（参考訳）: 実世界の組合せ最適化問題はしばしば確率的かつ動的である。 したがって、総合的なアプローチで最適かつ信頼性の高い意思決定を行うことが不可欠である。 本稿では,各項目の重量が確率的であり,容量制約が時間とともに動的に変化し,総重量が容量を超える確率に基づいて総利益を最大化することを目的とした動的確率制約ナップサック問題を考える。 チェビシェフの不等式(chebyshev's inequality)やチャーノフ・バウンド(chernoff bound)のような顕著な尾の不等式を用いて確率的制約を近似する。 我々の重要な貢献は、まだチャンス制約を満たす確率的解の最小容量を推定する追加の目的を導入することである。 この目的は、確率問題に対する動的変化に対応するのに役立つ。 我々は,単一および多目的進化アルゴリズムを問題に適用し,2目的最適化が動的確率制約問題に対する対処にどのように役立つかを示す。

関連論文リスト

• Stochastic Q-learning for Large Discrete Action Spaces [79.1700188160944]
  離散的な行動空間を持つ複雑な環境では、強化学習(RL)において効果的な意思決定が重要である 我々は、$n$アクションの集合全体を最適化するのとは対照的に、おそらく$mathcalO(log(n)$)$のような変数の集合のみを考える。 提示された値ベースのRL手法には、Q-learning、StochDQN、StochDDQNなどが含まれる。
  論文  参考訳（メタデータ） (2024-05-16T17:58:44Z)
• Multi-Objective Evolutionary Algorithms with Sliding Window Selection for the Dynamic Chance-Constrained Knapsack Problem [2.5690340428649328]
  静的および動的重み制約下での利益を伴うknapsack問題に対する多目的進化的アプローチを提案する。 我々は、期待される利益を最大化し、分散を最小化する双方向の定式化を考える。 重み制約を緩和して3目的の定式化を導出する。
  論文  参考訳（メタデータ） (2024-04-12T03:07:15Z)
• Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem [9.617143859697322]
  動的制約付き制約付きクナプサック問題に対する3目的進化アルゴリズムの利用について検討する。 動的成分を同時に扱える3つの客観的定式化を導入し,制約に要求される信頼度に依存しない。 本分析では, 動的確率制約クナプサック問題に対処する上で, 2-対象の定式化よりも3-対象の定式化の利点を強調した。
  論文  参考訳（メタデータ） (2024-04-09T04:47:01Z)
• Addressing The Knapsack Challenge Through Cultural Algorithm Optimization [0.0]
  我々は,0-1knapsack問題の解法に特化して設計された,新しい文化アルゴリズムの変種を紹介する。 提案アルゴリズムは,集団を改良するための信念空間と,交叉率と突然変異率を動的に調節する2つの重要な機能を導入している。 我々は,このアルゴリズムがグローバルな最適点を一貫して見つけ出す上で,顕著な効率性を示す証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-30T17:05:19Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  独立して通常は分散しているコンポーネントのシナリオについて研究する。 期待されるコストとその分散をトレードオフする問題を多目的に定式化する。 また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
  論文  参考訳（メタデータ） (2021-09-13T09:24:23Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。 このアプローチは多くの実装と最適化の課題をもたらします。 提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
  論文  参考訳（メタデータ） (2021-03-18T14:26:26Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Specific Single- and Multi-Objective Evolutionary Algorithms for the Chance-Constrained Knapsack Problem [14.352521012951865]
  我々は、チャンス制約付きknapsack問題に対して、新しい効果的な多目的モデルを提案する。 実験結果から, 進化的多目的アルゴリズムを用いた場合, 性能が大幅に向上することが示唆された。
  論文  参考訳（メタデータ） (2020-04-07T08:46:51Z)

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

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