論文の概要: Optimising Monotone Chance-Constrained Submodular Functions Using
Evolutionary Multi-Objective Algorithms
- arxiv url: http://arxiv.org/abs/2006.11444v1
- Date: Sat, 20 Jun 2020 00:17:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 22:02:13.345535
- Title: Optimising Monotone Chance-Constrained Submodular Functions Using
Evolutionary Multi-Objective Algorithms
- Title(参考訳): 進化的多目的アルゴリズムを用いたモノトンチャンス制約部分モジュラ関数の最適化
- Authors: Aneta Neumann and Frank Neumann
- Abstract要約: 本稿では、確率制約付き部分モジュラー関数に対する進化的多目的アルゴリズムの最初の実行時解析について述べる。
本稿では,GSEMOアルゴリズムが最近解析されたgreedyアルゴリズムと同等の性能保証が得られることを示す。
- 参考スコア(独自算出の注目度): 15.389164392812276
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many real-world optimisation problems can be stated in terms of submodular
functions. A lot of evolutionary multi-objective algorithms 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 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 show that the GSEMO algorithm
obtains the same worst case performance guarantees as recently analyzed greedy
algorithms. Furthermore, we investigate the behavior of evolutionary
multi-objective algorithms such as GSEMO and NSGA-II on different submodular
chance constrained network problems. Our experimental results show that this
leads to significant performance improvements compared to the greedy algorithm.
- Abstract(参考訳): 多くの実世界の最適化問題は、部分モジュラ函数の観点で述べることができる。
多くの進化的多目的アルゴリズムが近年解析され、異なる種類の制約を持つ部分モジュラー問題に適用されている。
本稿では,確率制約付き部分モジュラ関数に対する進化的多目的アルゴリズムのランタイム解析について述べる。
ここで、制約は確率的成分を含み、制約はアルファのわずかな確率でのみ破ることができる。
gsemoアルゴリズムは,近年解析されたグリーディアルゴリズムと同じ最悪の場合性能保証が得られることを示す。
さらに,GSEMOやNSGA-IIなどの進化的多目的アルゴリズムのネットワーク問題に対する挙動について検討した。
実験結果から, グリーディアルゴリズムと比較して, 大幅な性能向上が得られた。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。