Fugu-MT 論文翻訳(概要): Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization

論文の概要: Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization

arxiv url: http://arxiv.org/abs/2406.13414v1
Date: Wed, 19 Jun 2024 10:08:12 GMT
ステータス: 処理完了
システム内更新日: 2024-06-21 20:12:53.168202
Title: Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization
Title（参考訳）: サブモジュール最適化のためのアーカイブベース単一目的進化アルゴリズム
Authors: Frank Neumann, Günter Rudolph,
Abstract要約: 我々は、制約付き部分モジュラー問題の異なるクラスに対して証明可能な成功を収めた、初めての単目的アルゴリズムを紹介する。私たちのアルゴリズムは$(lambda)$-EAと$(+1)$-EAの変種です。
参考スコア（独自算出の注目度）: 9.852567834643288
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Constrained submodular optimization problems play a key role in the area of combinatorial optimization as they capture many NP-hard optimization problems. So far, Pareto optimization approaches using multi-objective formulations have been shown to be successful to tackle these problems while single-objective formulations lead to difficulties for algorithms such as the $(1+1)$-EA due to the presence of local optima. We introduce for the first time single-objective algorithms that are provably successful for different classes of constrained submodular maximization problems. Our algorithms are variants of the $(1+\lambda)$-EA and $(1+1)$-EA and increase the feasible region of the search space incrementally in order to deal with the considered submodular problems.
Abstract（参考訳）: 制約付き部分モジュラ最適化問題は、多くのNPハード最適化問題を捉える際に、組合せ最適化の領域において重要な役割を果たす。これまでのところ、多目的の定式化を用いたパレート最適化手法はこれらの問題に対処するのに成功し、一方単目的の定式化は局所最適化の存在により(1+1)$-EAのようなアルゴリズムの難しさを招いている。我々は、制約付き部分モジュラー最大化問題の異なるクラスに対して証明可能な成功を収めた、初めての単目的アルゴリズムを紹介する。我々のアルゴリズムは$(1+\lambda)$-EAと$(1+1)$-EAの変種であり、考慮された部分モジュラー問題に対処するために検索空間の実行可能な領域を漸進的に増加させる。

関連論文リスト

Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
論文参考訳（メタデータ） (2024-09-06T17:17:52Z)
Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文参考訳（メタデータ） (2024-06-21T05:57:08Z)
Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
論文参考訳（メタデータ） (2024-01-19T07:40:24Z)
Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
論文参考訳（メタデータ） (2023-12-28T23:15:18Z)
Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文参考訳（メタデータ） (2023-07-17T20:11:56Z)
Enhanced Opposition Differential Evolution Algorithm for Multimodal Optimization [0.2538209532048866]
現実の問題は、本質的には複数の最適値からなるマルチモーダルである。古典的な勾配に基づく手法は、目的関数が不連続あるいは微分不可能な最適化問題に対して失敗する。我々は,MMOPを解くために,拡張オポポジション微分進化(EODE)アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-08-23T16:18:27Z)
A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文参考訳（メタデータ） (2022-03-01T18:20:01Z)
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)
Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文参考訳（メタデータ） (2021-10-20T02:57:21Z)
Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
複数変数の非プロブレムに挑戦する新しい解を提案する。提案手法では,他の手法が一般的に失敗するケースに対して,効果的なイテレーションを実現することができる。
論文参考訳（メタデータ） (2020-09-09T10:45:00Z)
Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文参考訳（メタデータ） (2020-06-11T17:43:19Z)

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