論文の概要: Evolutionary Multi-Objective Algorithms for the Knapsack Problems with
Stochastic Profits
- arxiv url: http://arxiv.org/abs/2303.01695v1
- Date: Fri, 3 Mar 2023 03:28:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-06 16:09:22.552298
- Title: Evolutionary Multi-Objective Algorithms for the Knapsack Problems with
Stochastic Profits
- Title(参考訳): 確率的利益をもつKnapsack問題に対する進化的多目的アルゴリズム
- Authors: Kokila Perera and Aneta Neumann and Frank Neumann
- Abstract要約: 我々は、ある商品の利益に対する一定の信頼を保証するため、利益を伴うknapsack問題のバージョンを検討する。
利益率制約付きクナップサック問題の多目的定式化を導入し, 両目的性評価法を3つ設計する。
両設定のベンチマークにおいて,提案手法の有効性を示す。
- 参考スコア(独自算出の注目度): 13.026567958569965
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary multi-objective algorithms have been widely shown to be
successful when utilized for a variety of stochastic combinatorial optimization
problems. Chance constrained optimization plays an important role in complex
real-world scenarios, as it allows decision makers to take into account the
uncertainty of the environment. We consider a version of the knapsack problem
with stochastic profits to guarantee a certain level of confidence in the
profit of the solutions. We introduce the multi-objective formulations of the
profit chance constrained knapsack problem and design three bi-objective
fitness evaluation methods that work independently of the specific confidence
level required. We evaluate our approaches using well-known multi-objective
evolutionary algorithms GSEMO and NSGA-II. In addition, we introduce a
filtering method for GSEMO that improves the quality of the final population by
periodically removing certain solutions from the interim populations based on
their confidence level. We show the effectiveness of our approaches on several
benchmarks for both settings where the knapsack items have fixed uniform
uncertainties and uncertainties that are positively correlated with the
expected profit of an item.
- Abstract(参考訳): 進化的多目的アルゴリズムは、様々な確率的組合せ最適化問題に利用できることが広く示されている。
環境の不確実性を考慮して意思決定を行うことができるため、環境制約最適化は複雑な現実世界のシナリオにおいて重要な役割を果たす。
我々は,クナプサック問題の確率的利益によるバージョンを,解の利益に対する一定の信頼度を保証するために検討する。
本稿では,利益機会制約クナップサック問題の多目的定式化と,要求される特定の信頼度レベルとは独立に動作する3つの多目的適合性評価手法を提案する。
我々は,よく知られた多目的進化アルゴリズムgsemoとnsga-iiを用いてアプローチを評価する。
また,GSEMOにおいて,信頼度に基づいて一定解を定期的に除去することにより,最終個体群の品質を向上するフィルタリング手法を提案する。
我々は,クナップサック項目が固定された不確実性と,期待される利益と正に相関する不確実性を有するような条件下でのいくつかのベンチマークにおけるアプローチの有効性を示す。
関連論文リスト
- Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。
本手法は, 精度の高い問題に特に適している。
提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
論文 参考訳(メタデータ) (2023-11-08T00:10:21Z) - Addressing The Knapsack Challenge Through Cultural Algorithm
Optimization [0.0]
我々は,0-1knapsack問題の解法に特化して設計された,新しい文化アルゴリズムの変種を紹介する。
提案アルゴリズムは,集団を改良するための信念空間と,交叉率と突然変異率を動的に調節する2つの重要な機能を導入している。
我々は,このアルゴリズムがグローバルな最適点を一貫して見つけ出す上で,顕著な効率性を示す証拠を提供する。
論文 参考訳(メタデータ) (2023-10-30T17:05:19Z) - Multi-Objective GFlowNets [59.16787189214784]
本稿では,多目的最適化の文脈において,多様な候補を生成する問題について検討する。
薬物発見やマテリアルデザインといった機械学習の多くの応用において、目標は、競合する可能性のある目標のセットを同時に最適化する候補を生成することである。
GFlowNetsをベースとした多目的GFlowNets(MOGFNs)を提案する。
論文 参考訳(メタデータ) (2022-10-23T16:15:36Z) - Evolutionary Algorithms for Limiting the Effect of Uncertainty for the
Knapsack Problem with Stochastic Profits [14.352521012951865]
我々は、利益が不確実性を伴うクナプサック問題を考察する。
我々は、不確実性の影響を制限するために、尾の不平等に基づいて利益を扱う様々な方法を導入する。
論文 参考訳(メタデータ) (2022-04-12T07:56:50Z) - 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) - Policy Gradient Bayesian Robust Optimization for Imitation Learning [49.881386773269746]
我々は、期待される性能とリスクのバランスをとるために、新しいポリシー勾配スタイルのロバスト最適化手法PG-BROILを導出する。
その結果,PG-BROILはリスクニュートラルからリスク・アバースまでの行動のファミリを創出できる可能性が示唆された。
論文 参考訳(メタデータ) (2021-06-11T16:49:15Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds
Globally Optimal Policy [95.98698822755227]
本研究は,リスクに敏感な深層強化学習を,分散リスク基準による平均報酬条件下で研究する試みである。
本稿では,ポリシー,ラグランジュ乗算器,フェンシェル双対変数を反復的かつ効率的に更新するアクタ批判アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-28T05:02:26Z) - Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
また, 共通最適化手法は, 問題が適度に大きい場合, 変分近似の精度が低下することを示した。
これらの結果から,基礎となるアルゴリズムをマルコフ連鎖の生成とみなして,より堅牢で正確な最適化フレームワークを開発する。
論文 参考訳(メタデータ) (2020-09-01T19:12:11Z) - Specific Single- and Multi-Objective Evolutionary Algorithms for the
Chance-Constrained Knapsack Problem [14.352521012951865]
我々は、チャンス制約付きknapsack問題に対して、新しい効果的な多目的モデルを提案する。
実験結果から, 進化的多目的アルゴリズムを用いた場合, 性能が大幅に向上することが示唆された。
論文 参考訳(メタデータ) (2020-04-07T08:46:51Z) - Evolutionary Bi-objective Optimization for the Dynamic
Chance-Constrained Knapsack Problem Based on Tail Bound Objectives [12.634782111072585]
本稿では,各項目の重みが容量制約の対象となる動的チャンス制約knapsack問題について考察する。
目的は、総重量がキャパシティを超える確率に基づく総利益を最大化することである。
与えられた解に対する最小限のキャパシティを見積もる追加の目的を導入する。
論文 参考訳(メタデータ) (2020-02-17T04:36:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。