論文の概要: Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables
- arxiv url: http://arxiv.org/abs/2109.05799v3
- Date: Thu, 22 Aug 2024 00:24:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-25 14:30:57.246649
- Title: Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables
- Title（参考訳）: 正規分散確率変数を用いたチャンス制約最適化問題に対する単目的・多目的進化アルゴリズムの実行時解析
- Authors: Frank Neumann, Carsten Witt,
- Abstract要約: 独立して通常は分散しているコンポーネントのシナリオについて研究する。
期待されるコストとその分散をトレードオフする問題を多目的に定式化する。
また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
- 参考スコア（独自算出の注目度）: 11.310502327308575
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Chance constrained optimization problems allow to model problems where constraints involving stochastic components should only be violated with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance constrained optimization. We study the scenario of stochastic components that are independent and normally distributed. Considering the simple single-objective (1+1) EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We show that multi-objective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem. In order to deal with potentially exponentially many trade-offs in the multi-objective formulation, we propose and analyze improved convex multi-objective approaches. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multi-objective and the improved convex multi-objective approach in practice.
- Abstract（参考訳）: チャンス制約最適化問題により、確率的成分を含む制約が小さな確率でのみ破られるような問題をモデル化することができる。
進化的アルゴリズムがこのシナリオに適用され、高品質な結果が得られることが示されている。
本稿では,確率制約最適化のための進化的アルゴリズムの理論的理解に寄与する。
独立で通常分散している確率成分のシナリオについて検討する。
単純な単目的 (1+1) EA を考えると、追加の一様制約を課すことで、非常に制限されたシナリオに対する局所最適化と指数最適化時間が得られることが示されている。
したがって、期待されるコストとその分散をトレードオフする問題の多目的定式化を導入する。
この定式化を利用する際には,多目的進化的アルゴリズムが極めて有効であることを示し,制約に課される任意の信頼度に対する最適解を含む解の集合を求める。
さらに,本手法は,最小分散木問題に対する最適解集合の計算にも有効であることを示す。
多目的の定式化において、潜在的に指数関数的に多くのトレードオフに対処するために、改良された凸多目的のアプローチを提案し、分析する。
NP-ハード確率的最小重み決定セット問題の事例に関する実験的研究は、実際、多目的の利点と改善された凸多目的のアプローチの利点を裏付けるものである。
関連論文リスト
- Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
最近の構造化学習手法のストリームは、様々な最適化問題に対する技術の実践的状態を改善している。
鍵となる考え方は、インスタンスを別々に扱うのではなく、インスタンス上の統計分布を利用することだ。
本稿では,最適化を容易にし,一般化誤差を改善するポリシを摂動することでリスクを円滑にする手法について検討する。
論文 参考訳（メタデータ） (2024-07-24T12:00:30Z) - Optimizing Chance-Constrained Submodular Problems with Variable
Uncertainties [12.095075636344536]
本稿では,制約付き多種多様な問題を捕捉する,確率制約付き部分モジュラー最適化問題について検討する。
所与の最適解に対する定数近似比という,高品質な解を得ることのできるグリーディアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-23T04:48:49Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - End-to-End Pareto Set Prediction with Graph Neural Networks for
Multi-objective Facility Location [10.130342722193204]
施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。
本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。
ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
論文 参考訳（メタデータ） (2022-10-27T07:15:55Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Integrated Conditional Estimation-Optimization [6.037383467521294]
確率のある不確実なパラメータを文脈的特徴情報を用いて推定できる実世界の多くの最適化問題である。
不確実なパラメータの分布を推定する標準的な手法とは対照的に,統合された条件推定手法を提案する。
当社のI CEOアプローチは、穏健な条件下で理論的に一貫性があることを示します。
論文 参考訳（メタデータ） (2021-10-24T04:49:35Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2021-09-23T17:38:24Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。