論文の概要: On the Use of Bi-Objective Evolutionary Algorithms for the Stochastic MKP under Dynamic Constraints

• arxiv url: http://arxiv.org/abs/2604.10930v1
• Date: Mon, 13 Apr 2026 02:59:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-14 20:13:16.28536
• Title: On the Use of Bi-Objective Evolutionary Algorithms for the Stochastic MKP under Dynamic Constraints
• Title（参考訳）: 動的制約下における確率的MKPに対する2目的進化アルゴリズムの利用について
• Authors: Ishara Hewa Pathiranage, Aneta Neumann,
• Abstract要約: 多重knapsack問題(MKP)は、容量制約を受ける複数のknapsackにアイテムを割り当てることで古典的なknapsack問題を一般化する。 信頼度レベルにおいて、利益とキャパシティ満足度をバランスさせる双目的最適化の定式化として問題を定式化する。
• 参考スコア（独自算出の注目度）: 3.6439154309310013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multiple knapsack problem (MKP) generalizes the classical knapsack problem by assigning items to multiple knapsacks subject to capacity constraints. It is used to model many real-world resource allocation and scheduling problems. In practice, these optimization problems often involve stochastic and dynamic components. Evolutionary algorithms provide a flexible framework for addressing such problems under uncertainty and dynamic changes. In this paper, we investigate a stochastic and dynamic variant of MKP with chance constraints, where the item weights are modeled as independent normally distributed random variables and knapsack capacities change during the optimization process. We formulate the problem as a bi-objective optimization formulation that balances profit maximization and probabilistic capacity satisfaction at a given confidence level. We conduct an empirical comparison of four widely used multi-objective evolutionary algorithms (MOEAs), representing both decomposition- and dominance-based search paradigms. The algorithms are evaluated under varying uncertainty levels, confidence thresholds, and dynamic change settings. The results provide comparative insights into the behavior of decomposition-based and dominance-based MOEAs for stochastic MKP under dynamic constraints.
• Abstract（参考訳）: 多重knapsack問題(MKP)は、容量制約を受ける複数のknapsackにアイテムを割り当てることで古典的なknapsack問題を一般化する。 多くの実世界の資源割り当てとスケジューリングの問題をモデル化するために使用される。 実際には、これらの最適化問題は確率的および動的成分を含むことが多い。 進化的アルゴリズムは、不確実性と動的変化の下でそのような問題に対処するための柔軟なフレームワークを提供する。 本稿では,MKPの確率的・動的変種について検討し,各項目の重みを正規分布変数としてモデル化し,最適化過程中にknapsackの容量が変化することを示す。 本稿では,信頼度レベルにおいて,利益の最大化と確率的キャパシティ満足度をバランスさせる双目的最適化の定式化として,この問題を定式化する。 我々は、分解と支配に基づく探索のパラダイムを表わす4つの広く使われている多目的進化アルゴリズム(MOEA)を実証的に比較する。 アルゴリズムは、さまざまな不確実性レベル、信頼性閾値、動的変更設定で評価される。 その結果, 動的制約下での確率的MKPに対する分解型および支配型MOEAの挙動を比較検討した。

関連論文リスト

• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。 これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。 我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
  論文  参考訳（メタデータ） (2024-10-14T12:10:06Z)
• Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems [2.66854711376491]
  提案された力学はラグランジアン近似に基づくもので、ADMMの代替となる。 我々は、様々な構造的特性を利用して、提案された力学に対する大域的(指数的)収束保証を確立する。 我々の仮定は原始双対力学の(指数的な)安定性を証明するために必要なものよりもはるかに弱い。
  論文  参考訳（メタデータ） (2024-08-28T17:43:18Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  我々はスムーズな(摂動された)ポリシーを解析し、線形オラクルが使用する方向に対して制御されたランダムな摂動を付加する。 我々の主な貢献は、過剰リスクを摂動バイアス、統計的推定誤差、最適化誤差に分解する一般化境界である。 車両のスケジューリングやスムーズ化がトラクタブルトレーニングと制御された一般化の両方を可能にしていることを示す。
  論文  参考訳（メタデータ） (2024-07-24T12:00:30Z)
• 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)
• Ensemble Kalman Filtering Meets Gaussian Process SSM for Non-Mean-Field and Online Inference [47.460898983429374]
  我々は,非平均場(NMF)変動推定フレームワークにアンサンブルカルマンフィルタ(EnKF)を導入し,潜在状態の後方分布を近似する。 EnKFとGPSSMのこの新しい結婚は、変分分布の学習における広範なパラメータ化の必要性をなくすだけでなく、エビデンスの下限(ELBO)の解釈可能でクローズドな近似を可能にする。 得られたEnKF支援オンラインアルゴリズムは、データ適合精度を確保しつつ、モデル正規化を組み込んで過度適合を緩和し、目的関数を具現化する。
  論文  参考訳（メタデータ） (2023-12-10T15:22:30Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  本稿では,平均場近似ポリシ最適化(MF-PPO)アルゴリズムを提案する。 我々は,MF-PPOが収束のサブ線形速度で世界的最適政策を達成することを証明した。 特に、置換不変ニューラルアーキテクチャによって引き起こされる誘導バイアスは、MF-PPOが既存の競合より優れていることを示す。
  論文  参考訳（メタデータ） (2021-05-18T04:35:41Z)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  経験的最適化は現代の機械学習の中心であるが、その成功における役割はまだ不明である。 分散による離散乗法雑音のパラメータによく現れることを示す。 最新のステップサイズやデータを含む重要な要素について、詳細な分析を行い、いずれも最先端のニューラルネットワークモデルで同様の結果を示す。
  論文  参考訳（メタデータ） (2020-06-11T09:58:01Z)
• Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints [13.896724650508087]
  古典的knapsack問題に対する単目的・多目的ベースライン進化アルゴリズムについて検討する。 この結果から, 動的変化を考慮に入れた集団を用いた多目的アプローチは, 多くのベンチマークシナリオにおいて明らかな優位性を有することが示された。
  論文  参考訳（メタデータ） (2020-04-27T03:50:24Z)
• Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives [12.634782111072585]
  本稿では,各項目の重みが容量制約の対象となる動的チャンス制約knapsack問題について考察する。 目的は、総重量がキャパシティを超える確率に基づく総利益を最大化することである。 与えられた解に対する最小限のキャパシティを見積もる追加の目的を導入する。
  論文  参考訳（メタデータ） (2020-02-17T04:36:15Z)

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

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