論文の概要: 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などの進化的多目的アルゴリズムのネットワーク問題に対する挙動について検討した。
実験結果から, グリーディアルゴリズムと比較して, 大幅な性能向上が得られた。
関連論文リスト
- Benchmarking Algorithms for Submodular Optimization Problems Using
IOHProfiler [22.08617448389877]
本稿では,部分モジュラ最適化問題に対するベンチマークアルゴリズムのセットアップを提案する。
その焦点は反復探索アルゴリズムの開発であり、実装はIOHknownrに提供され、統合されている。
提案手法は,IOHファウンサーに組み込まれている様々な部分モジュラ最適化問題について述べるとともに,反復探索アルゴリズムを様々な設定で解析・比較するために,その設定をどのように利用できるかを示す。
論文 参考訳(メタデータ) (2023-02-02T23:36:23Z) - Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms
on General Cover Problems [16.98107289469868]
いくつかの近似機構は本質的に多くの進化的アルゴリズムに埋め込まれているようである。
我々は、一般化された単純多目的進化アルゴリズムのための統合分析フレームワークを提案することにより、そのような関係を同定する。
論文 参考訳(メタデータ) (2022-10-03T01:25:53Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳(メタデータ) (2022-09-15T07:22:58Z) - An Application of a Multivariate Estimation of Distribution Algorithm to
Cancer Chemotherapy [59.40521061783166]
癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。
より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。
我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
論文 参考訳(メタデータ) (2022-05-17T15:28:46Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳(メタデータ) (2021-10-18T14:00:22Z) - 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) - Maximizing Submodular or Monotone Functions under Partition Matroid
Constraints by Multi-objective Evolutionary Algorithms [16.691265882753346]
GSEMOと呼ばれる単純な進化的アルゴリズムは、部分モジュラ函数の近似を効率的に行うことが示されている。
我々は理論結果を拡張し、濃度制約を一般化するマトロイド制約を分割する。
論文 参考訳(メタデータ) (2020-06-23T05:37:29Z) - 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) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳(メタデータ) (2020-02-17T20:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。