論文の概要: Multi-Objective Evolutionary Algorithms with Sliding Window Selection for the Dynamic Chance-Constrained Knapsack Problem

• arxiv url: http://arxiv.org/abs/2404.08219v1
• Date: Fri, 12 Apr 2024 03:07:15 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-15 16:05:17.456117
• Title: Multi-Objective Evolutionary Algorithms with Sliding Window Selection for the Dynamic Chance-Constrained Knapsack Problem
• Title（参考訳）: 動的チャンス制約Knapsack問題に対するスライディングウィンドウ選択を用いた多目的進化アルゴリズム
• Authors: Kokila Kasuni Perera, Aneta Neumann,
• Abstract要約: 静的および動的重み制約下での利益を伴うknapsack問題に対する多目的進化的アプローチを提案する。 我々は、期待される利益を最大化し、分散を最小化する双方向の定式化を考える。 重み制約を緩和して3目的の定式化を導出する。
• 参考スコア（独自算出の注目度）: 2.5690340428649328
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary algorithms are particularly effective for optimisation problems with dynamic and stochastic components. We propose multi-objective evolutionary approaches for the knapsack problem with stochastic profits under static and dynamic weight constraints. The chance-constrained problem model allows us to effectively capture the stochastic profits and associate a confidence level to the solutions' profits. We consider a bi-objective formulation that maximises expected profit and minimises variance, which allows optimising the problem independent of a specific confidence level on the profit. We derive a three-objective formulation by relaxing the weight constraint into an additional objective. We consider the GSEMO algorithm with standard and a sliding window-based parent selection to evaluate the objective formulations. Moreover, we modify fitness formulations and algorithms for the dynamic problem variant to store some infeasible solutions to cater to future changes. We conduct experimental investigations on both problems using the proposed problem formulations and algorithms. Our results show that three-objective approaches outperform approaches that use bi-objective formulations, and they further improve when GSEMO uses sliding window selection.
• Abstract（参考訳）: 進化的アルゴリズムは、動的および確率的成分の最適化問題に特に有効である。 静的および動的重み制約の下で確率的利益を持つknapsack問題に対する多目的進化的アプローチを提案する。 確率制約問題モデルにより、確率的利益を効果的に捉え、信頼性レベルをソリューションの利益に関連付けることができる。 我々は、期待される利益を最大化し、分散を最小限にし、利益に対する特定の信頼レベルに依存しない問題を最適化できる、双目的の定式化を考える。 重み制約を緩和して3目的の定式化を導出する。 本稿では,GSEMOアルゴリズムの標準およびスライディングウインドウに基づく親選択について検討し,目的とする定式化を評価する。 さらに、動的問題変種に対する適合度定式化とアルゴリズムを変更し、将来的な変化に対応するために、いくつかの実現不可能なソリューションを格納する。 提案した問題定式化とアルゴリズムを用いて,両問題を実験的に検討する。 以上の結果から,GSEMOがスライディングウインドウ選択を用いた場合,2目的の定式化を用いた3目的のアプローチの方が優れており,さらに改善されていることが明らかとなった。

関連論文リスト

• Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem [9.617143859697322]
  動的制約付き制約付きクナプサック問題に対する3目的進化アルゴリズムの利用について検討する。 動的成分を同時に扱える3つの客観的定式化を導入し,制約に要求される信頼度に依存しない。 本分析では, 動的確率制約クナプサック問題に対処する上で, 2-対象の定式化よりも3-対象の定式化の利点を強調した。
  論文  参考訳（メタデータ） (2024-04-09T04:47:01Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  機械学習における予測-Then-Forecast(PtO)パラダイムは、下流の意思決定品質を最大化することを目的としている。 本稿では,PtO法を拡張して,OWA(Nondifferentiable Ordered Weighted Averaging)の目的を最適化する。 この結果から,不確実性の下でのOWA関数の最適化とパラメトリック予測を効果的に統合できることが示唆された。
  論文  参考訳（メタデータ） (2024-02-12T16:33:35Z)
• Evolutionary Solution Adaption for Multi-Objective Metal Cutting Process Optimization [59.45414406974091]
  我々は,従来の最適化タスクから解を転送するアルゴリズムの能力を研究することのできる,システムの柔軟性のためのフレームワークを提案する。 NSGA-IIの柔軟性を2つの変種で検討し,1)2つのタスクの解を同時に最適化し,より適応性が高いと期待されるソース間の解を得る,2)活性化あるいは非活性化の異なる可能性に対応する能動的非アクティブなジェノタイプについて検討した。 その結果,標準NSGA-IIによる適応は目標目標への最適化に必要な評価回数を大幅に削減し,提案した変種は適応コストをさらに向上することがわかった。
  論文  参考訳（メタデータ） (2023-05-31T12:07:50Z)
• Evolutionary Multi-Objective Algorithms for the Knapsack Problems with Stochastic Profits [13.026567958569965]
  我々は、ある商品の利益に対する一定の信頼を保証するため、利益を伴うknapsack問題のバージョンを検討する。 利益率制約付きクナップサック問題の多目的定式化を導入し, 両目的性評価法を3つ設計する。 両設定のベンチマークにおいて,提案手法の有効性を示す。
  論文  参考訳（メタデータ） (2023-03-03T03:28:51Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• 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)
• Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
  また, 共通最適化手法は, 問題が適度に大きい場合, 変分近似の精度が低下することを示した。 これらの結果から,基礎となるアルゴリズムをマルコフ連鎖の生成とみなして,より堅牢で正確な最適化フレームワークを開発する。
  論文  参考訳（メタデータ） (2020-09-01T19:12:11Z)
• Adaptive Sampling of Pareto Frontiers with Binary Constraints Using Regression and Classification [0.0]
  本稿では,二項制約を持つブラックボックス多目的最適化問題に対する適応最適化アルゴリズムを提案する。 本手法は確率的回帰モデルと分類モデルに基づいており,最適化目標のサロゲートとして機能する。 また,予想される超体積計算を高速化するために,新しい楕円形トランケーション法を提案する。
  論文  参考訳（メタデータ） (2020-08-27T09:15:02Z)
• Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives [12.634782111072585]
  本稿では,各項目の重みが容量制約の対象となる動的チャンス制約knapsack問題について考察する。 目的は、総重量がキャパシティを超える確率に基づく総利益を最大化することである。 与えられた解に対する最小限のキャパシティを見積もる追加の目的を導入する。
  論文  参考訳（メタデータ） (2020-02-17T04:36:15Z)

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

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