論文の概要: Sliding Window Bi-Objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular Functions
- arxiv url: http://arxiv.org/abs/2407.09731v2
- Date: Wed, 7 Aug 2024 05:13:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-08 14:56:01.249106
- Title: Sliding Window Bi-Objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular Functions
- Title（参考訳）: Sliding Window Bi-Objective Evolutionary Algorithms fortimizing Chance-Constrained Monotone Submodular Function (特集:ユビキタスコンピューティング)
- Authors: Xiankun Yan, Aneta Neumann, Frank Neumann,
- Abstract要約: 本稿では,[21]で導入されたスライディング・セレクションのアプローチを,確率制約付き単調部分モジュラ関数の最適化に適用する。
SW-GSEMOアルゴリズムは,実行環境に影響を及ぼす重要な要因として,個体数制限に成功していることを示す。
- 参考スコア（独自算出の注目度）: 10.506038775815094
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Variants of the GSEMO algorithm using multi-objective formulations have been successfully analyzed and applied to optimize chance-constrained submodular functions. However, due to the effect of the increasing population size of the GSEMO algorithm considered in these studies from the algorithms, the approach becomes ineffective if the number of trade-offs obtained grows quickly during the optimization run. In this paper, we apply the sliding-selection approach introduced in [21] to the optimization of chance-constrained monotone submodular functions. We theoretically analyze the resulting SW-GSEMO algorithm which successfully limits the population size as a key factor that impacts the runtime and show that this allows it to obtain better runtime guarantees than the best ones currently known for the GSEMO. In our experimental study, we compare the performance of the SW-GSEMO to the GSEMO and NSGA-II on the maximum coverage problem under the chance constraint and show that the SW-GSEMO outperforms the other two approaches in most cases. In order to get additional insights into the optimization behavior of SW-GSEMO, we visualize the selection behavior of SW-GSEMO during its optimization process and show it beats other algorithms to obtain the highest quality of solution in variable instances.
- Abstract（参考訳）: 多目的定式化を用いたGSEMOアルゴリズムの変数を解析し,確率制約付き部分モジュラー関数の最適化に応用した。
しかし,これらの研究で考慮されたGSEMOアルゴリズムの個体数増加の影響により,最適化実行中に得られたトレードオフ数が急速に増加すると,この手法は効果が低下する。
本稿では,[21]で導入されたスライディング・セレクションのアプローチを,確率制約付き単調部分モジュラ関数の最適化に適用する。
GSEMOアルゴリズムは,実行環境に影響を及ぼす重要な要因として個体群サイズを制限し,現在GSEMOで知られているものよりも優れた実行保証が得られることを示す。
本研究では,SW-GSEMO と GSEMO と NSGA-II の最大カバレッジ問題における性能を比較し,SW-GSEMO が他の2つのアプローチよりも優れていることを示す。
SW-GSEMOの最適化動作に関するさらなる知見を得るため、SW-GSEMOの最適化過程における選択挙動を可視化し、他のアルゴリズムに勝って可変インスタンスにおける解の最高品質を得ることを示す。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - Sampling-based Pareto Optimization for Chance-constrained Monotone Submodular Problems [10.506038775815094]
本稿では,確率制約を直接評価するサンプリングベース手法を提案する。
より困難な設定でこの問題に対処するため、強化されたGSEMOアルゴリズムが導入された。
ASW-GSEMOとサンプリングベースの評価手法は、他のアルゴリズムよりも優れている。
論文 参考訳（メタデータ） (2024-04-18T05:15:20Z) - 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) - Towards Self-adaptive Mutation in Evolutionary Multi-Objective
Algorithms [10.609857097723266]
自己適応が多目的進化アルゴリズムに与える影響について検討する。
単一目的最適化とハイパーボリュームに基づく突然変異率の適応は,GSEMOの収束を早めることができることを示す。
本稿では,単一目的の最適化を考慮し,各ソリューションの突然変異率を個別に調整する自己適応突然変異GSEMOを提案する。
論文 参考訳（メタデータ） (2023-03-08T14:26:46Z) - An Empirical Evaluation of Zeroth-Order Optimization Methods on
AI-driven Molecule Optimization [78.36413169647408]
分子目的を最適化するための様々なZO最適化手法の有効性について検討する。
ZO符号に基づく勾配降下(ZO-signGD)の利点を示す。
本稿では,Guurcamol スイートから広く使用されているベンチマークタスクに対して,ZO 最適化手法の有効性を示す。
論文 参考訳（メタデータ） (2022-10-27T01:58:10Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - EOS: a Parallel, Self-Adaptive, Multi-Population Evolutionary Algorithm
for Constrained Global Optimization [68.8204255655161]
EOSは実数値変数の制約付きおよび制約なし問題に対する大域的最適化アルゴリズムである。
これはよく知られた微分進化(DE)アルゴリズムに多くの改良を加えている。
その結果、EOSisは、最先端の単一人口自己適応Dアルゴリズムと比較して高い性能を達成可能であることが証明された。
論文 参考訳（メタデータ） (2020-07-09T10:19:22Z) - Maximizing Submodular or Monotone Functions under Partition Matroid
Constraints by Multi-objective Evolutionary Algorithms [16.691265882753346]
GSEMOと呼ばれる単純な進化的アルゴリズムは、部分モジュラ函数の近似を効率的に行うことが示されている。
我々は理論結果を拡張し、濃度制約を一般化するマトロイド制約を分割する。
論文 参考訳（メタデータ） (2020-06-23T05:37:29Z) - Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [11.807734722701786]
ここでは制約は成分を伴い、制約はアルファの小さな確率でのみ破ることができる。
GSEMOアルゴリズムは, 単調な部分モジュラ関数に対して, 最悪の性能保証が得られることを示す。
実験結果から, 進化的多目的アルゴリズムを用いることで, 性能が大幅に向上することが示唆された。
論文 参考訳（メタデータ） (2020-06-20T00:17:44Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳（メタデータ） (2020-02-13T05:42:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。