論文の概要: Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms

• arxiv url: http://arxiv.org/abs/2006.11444v2
• Date: Fri, 01 Nov 2024 02:12:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-04 14:33:34.957904
• Title: Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms
• Title（参考訳）: 進化的多目的アルゴリズムを用いたモノトンチャンス制約部分モジュラ関数の最適化
• Authors: Aneta Neumann, Frank Neumann,
• Abstract要約: ここでは制約は成分を伴い、制約はアルファの小さな確率でのみ破ることができる。 GSEMOアルゴリズムは, 単調な部分モジュラ関数に対して, 最悪の性能保証が得られることを示す。 実験結果から, 進化的多目的アルゴリズムを用いることで, 性能が大幅に向上することが示唆された。
• 参考スコア（独自算出の注目度）: 11.807734722701786
• License:
• Abstract: Many real-world optimization problems can be stated in terms of submodular functions. Furthermore, these real-world problems often involve uncertainties which may lead to the violation of given constraints. A lot of evolutionary multi-objective algorithms following the Pareto optimization approach have recently been analyzed and applied to submodular problems with different types of constraints. We present a first runtime analysis of evolutionary multi-objective algorithms based on Pareto optimization for chance-constrained submodular functions. Here the constraint involves stochastic components and the constraint can only be violated with a small probability of alpha. We investigate the classical GSEMO algorithm for two different bi-objective formulations using tail bounds to determine the feasibility of solutions. We show that the algorithm GSEMO obtains the same worst case performance guarantees for monotone submodular functions as recently analyzed greedy algorithms for the case of uniform IID weights and uniformly distributed weights with the same dispersion when using the appropriate bi-objective formulation. As part of our investigations, we also point out situations where the use of tail bounds in the first bi-objective formulation can prevent GSEMO from obtaining good solutions in the case of uniformly distributed weights with the same dispersion if the objective function is submodular but non-monotone due to a single element impacting monotonicity. Furthermore, we investigate the behavior of the evolutionary multi-objective algorithms GSEMO, NSGA-II and SPEA2 on different submodular chance-constrained network problems. Our experimental results show that the use of evolutionary multi-objective algorithms leads to significant performance improvements compared to state-of-the-art greedy algorithms for submodular optimization.
• Abstract（参考訳）: 多くの実世界の最適化問題は、部分モジュラ函数の観点で説明できる。 さらに、これらの現実世界の問題は、しばしば与えられた制約違反につながる不確実性を伴う。 パレート最適化に追従する多くの進化的多目的アルゴリズムが、最近分析され、異なる種類の制約を持つ部分モジュラー問題に適用されている。 本稿では、確率制約付き部分モジュラー関数に対するパレート最適化に基づく進化的多目的アルゴリズムの最初の実行時解析について述べる。 ここでは、制約は確率成分を伴い、制約はアルファの小さな確率でのみ破ることができる。 本稿では,古典的GSEMOアルゴリズムを用いて2つの異なる双対象の定式化を行い,解の実現可能性について検討する。 GSEMOアルゴリズムは,一様IID重みと一様分散重みに対して,最近解析されたgreedyアルゴリズムと同様に,単調な部分モジュラー関数に対する最悪の性能保証が得られることを示す。 本研究の一環として, 単調性に影響を及ぼす単調な単調な単調な要素により, 対象関数が非単調で非単調な場合, GSEMO が一様分散重みを持つ場合, GSEMO が良い解を得るのを防止できる状況も指摘した。 さらに,進化的多目的アルゴリズムGSEMO,NSGA-II,SPEA2のネットワーク問題に対する挙動について検討した。 実験の結果,進化的多目的アルゴリズムを用いることで,非モジュラー最適化のための最先端のグリードアルゴリズムと比較して,大幅な性能向上が得られた。

関連論文リスト

• Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization [9.852567834643288]
  我々は、制約付き部分モジュラー問題の異なるクラスに対して証明可能な成功を収めた、初めての単目的アルゴリズムを紹介する。 私たちのアルゴリズムは$(lambda)$-EAと$(+1)$-EAの変種です。
  論文  参考訳（メタデータ） (2024-06-19T10:08:12Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。 重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。 学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
  論文  参考訳（メタデータ） (2024-05-01T09:34:42Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• A novel multiobjective evolutionary algorithm based on decomposition and multi-reference points strategy [14.102326122777475]
  分解に基づく多目的進化アルゴリズム(MOEA/D)は、多目的最適化問題(MOP)を解く上で、極めて有望なアプローチであると考えられている。 本稿では,よく知られたPascoletti-Serafiniスキャラライゼーション法とマルチ参照ポイントの新たな戦略により,MOEA/Dアルゴリズムの改良を提案する。
  論文  参考訳（メタデータ） (2021-10-27T02:07:08Z)
• 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 [11.310502327308575]
  独立して通常は分散しているコンポーネントのシナリオについて研究する。 期待されるコストとその分散をトレードオフする問題を多目的に定式化する。 また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
  論文  参考訳（メタデータ） (2021-09-13T09:24:23Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  サブグループフィードバックを取り入れた新しいGPレグレッションを導入する。 我々の修正された回帰は、以前のアプローチと比べて、明らかにばらつきを減らし、したがってより正確な後続を減らした。 我々は2つの異なる社会問題に対してアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2021-07-07T03:57:22Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints [13.896724650508087]
  古典的knapsack問題に対する単目的・多目的ベースライン進化アルゴリズムについて検討する。 この結果から, 動的変化を考慮に入れた集団を用いた多目的アプローチは, 多くのベンチマークシナリオにおいて明らかな優位性を有することが示された。
  論文  参考訳（メタデータ） (2020-04-27T03:50:24Z)
• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization [0.0]
  自己調整および自己適応機構は、二進探索空間の進化的アルゴリズムにおける静的設定よりも確実に優れている。 我々は、既存の進化アルゴリズムのモジュールとして追加できる、停滞検出と呼ばれるメカニズムを提案する。
  論文  参考訳（メタデータ） (2020-04-07T11:02:10Z)

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

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