論文の概要: 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目的最適化が動的確率制約問題に対する対処にどのように役立つかを示す。
関連論文リスト
- Addressing The Knapsack Challenge Through Cultural Algorithm
Optimization [0.0]
我々は,0-1knapsack問題の解法に特化して設計された,新しい文化アルゴリズムの変種を紹介する。
提案アルゴリズムは,集団を改良するための信念空間と,交叉率と突然変異率を動的に調節する2つの重要な機能を導入している。
我々は,このアルゴリズムがグローバルな最適点を一貫して見つけ出す上で,顕著な効率性を示す証拠を提供する。
論文 参考訳(メタデータ) (2023-10-30T17:05:19Z) - Optimizing Chance-Constrained Submodular Problems with Variable
Uncertainties [12.095075636344536]
本稿では,制約付き多種多様な問題を捕捉する,確率制約付き部分モジュラー最適化問題について検討する。
所与の最適解に対する定数近似比という,高品質な解を得ることのできるグリーディアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-23T04:48:49Z) - Unbalanced penalization: A new approach to encode inequality constraints
of combinatorial problems for quantum optimization algorithms [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - 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 [13.264683014487376]
独立かつ正規分布のコンポーネントのシナリオについて検討する。
付加的な一様制約を課すことは、既に局所最適であることを示す。
また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
論文 参考訳(メタデータ) (2021-09-13T09:24:23Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた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) - Heuristic Strategies for Solving Complex Interacting Stockpile Blending
Problem with Chance Constraints [14.352521012951865]
本稿では,材料グレードの不確実性について考察し,信頼性の高い制約を確実にするために使用される確率制約を導入する。
ストックパイルブレンディング問題と確率制約に対処するため, 2つの補修演算子を組み合わせた微分進化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-10T07:56:18Z) - Specific Single- and Multi-Objective Evolutionary Algorithms for the
Chance-Constrained Knapsack Problem [14.352521012951865]
我々は、チャンス制約付きknapsack問題に対して、新しい効果的な多目的モデルを提案する。
実験結果から, 進化的多目的アルゴリズムを用いた場合, 性能が大幅に向上することが示唆された。
論文 参考訳(メタデータ) (2020-04-07T08:46:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。