論文の概要: Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential
- arxiv url: http://arxiv.org/abs/2407.08963v1
- Date: Fri, 12 Jul 2024 03:27:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-16 00:56:38.765918
- Title: Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential
- Title（参考訳）: 多様性最適化における局所最適性:非自明なオフスプリング人口は不可欠である
- Authors: Denis Antipov, Aneta Neumann, Frank Neumann,
- Abstract要約: 例えば$k$-vertexのカバー問題があり、これは通常の単目的最適化と多様性最適化の重大な違いを浮き彫りにしている。
さらに、$(mu + lambda)$ EA with $lambda ge mu$は、$k$-vertexのカバーで、事実上多様な集団を見つけることができることも示しています。
- 参考スコア（独自算出の注目度）: 10.506038775815094
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The main goal of diversity optimization is to find a diverse set of solutions which satisfy some lower bound on their fitness. Evolutionary algorithms (EAs) are often used for such tasks, since they are naturally designed to optimize populations of solutions. This approach to diversity optimization, called EDO, has been previously studied from theoretical perspective, but most studies considered only EAs with a trivial offspring population such as the $(\mu + 1)$ EA. In this paper we give an example instance of a $k$-vertex cover problem, which highlights a critical difference of the diversity optimization from the regular single-objective optimization, namely that there might be a locally optimal population from which we can escape only by replacing at least two individuals at once, which the $(\mu + 1)$ algorithms cannot do. We also show that the $(\mu + \lambda)$ EA with $\lambda \ge \mu$ can effectively find a diverse population on $k$-vertex cover, if using a mutation operator inspired by Branson and Sutton (TCS 2023). To avoid the problem of subset selection which arises in the $(\mu + \lambda)$ EA when it optimizes diversity, we also propose the $(1_\mu + 1_\mu)$ EA$_D$, which is an analogue of the $(1 + 1)$ EA for populations, and which is also efficient at optimizing diversity on the $k$-vertex cover problem.
- Abstract（参考訳）: 多様性最適化の主目的は、適合性にある程度の低い制約を満たす多様なソリューションを見つけることである。
進化的アルゴリズム(EA)は、自然に解の集団を最適化するために設計されているため、そのようなタスクにしばしば使用される。
EDOと呼ばれるこの多様性最適化のアプローチは、以前は理論的な観点から研究されてきたが、ほとんどの研究は、(\mu + 1)$ EAのような自明な子孫を持つEAのみを考慮に入れている。
そこで本論文では,従来の単一目的最適化と多様性最適化の重大な違い,すなわち,少なくとも2つの個人を一度に置き換えることによってのみ逃れることのできる局所的最適集団の存在,すなわち$(\mu + 1)$アルゴリズムでは不可能である,という問題を例に挙げる。
また、$(\mu + \lambda)$ EA with $\lambda \ge \mu$ は、ブランソン・アンド・サットン(TCS 2023)にインスパイアされた突然変異演算子を使用する場合、$k$-vertex カバー上の多様な集団を効果的に見つけることができることを示した。
多様性を最適化するとき、$(\mu + \lambda)$ EAに生じる部分集合選択の問題を避けるために、人口に対する$(1 + 1)$ EAの類似である$(1_\mu + 1_\mu)$ EA$_D$も提案する。
関連論文リスト
- Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem [10.697103866816958]
進化的多様性最適化(EDO)を3つの対象関数 LOTZ$_k$ 上で証明する。
GSEMOが全てのパレート最適解の集合を$O(kn3)$期待反復で計算することを示す。
両多様性尺度に非常によく似た振る舞いを示す実証的な研究で、我々の理論分析を補完する。
論文 参考訳（メタデータ） (2024-04-17T15:51:15Z) - Landscape Surrogate: Learning Decision Losses for Mathematical
Optimization Under Partial Information [48.784330281177446]
学習統合最適化の最近の研究は、最適化が部分的にのみ観察される場合や、専門家のチューニングなしに汎用性が不十分な環境では有望であることを示している。
本稿では,$fcirc mathbfg$の代替として,スムーズで学習可能なランドスケープサロゲートを提案する。
このサロゲートはニューラルネットワークによって学習可能で、$mathbfg$ソルバよりも高速に計算でき、トレーニング中に密度が高く滑らかな勾配を提供し、目に見えない最適化問題に一般化でき、交互最適化によって効率的に学習される。
論文 参考訳（メタデータ） (2023-07-18T04:29:16Z) - Rigorous Runtime Analysis of Diversity Optimization with GSEMO on
OneMinMax [13.026567958569965]
両目的のベンチマーク問題であるOneMinにおいて,GSEMOアルゴリズムの多様性向上による人口の多様性の最適化について検討した。
問題サイズ$n$が奇数である場合、期待時間$O(n2)$で最適な多様性を持つ集団が見つかることを証明している。
目標を達成するために、人口のランダムウォークを分析し、人口の変化頻度とその成果を反映する。
論文 参考訳（メタデータ） (2023-07-14T09:43:29Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Optimizer Amalgamation [124.33523126363728]
私たちは、Amalgamationという新しい問題の研究を動機付けています。"Teacher"アマルガメーションのプールを、より強力な問題固有のパフォーマンスを持つ単一の"学生"にどのように組み合わせるべきなのでしょうか?
まず、勾配降下による解析のプールをアマルガメートする3つの異なるメカニズムを定義する。
また, プロセスの分散を低減するため, 目標を摂動させることでプロセスの安定化を図る。
論文 参考訳（メタデータ） (2022-03-12T16:07:57Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function [0.0]
進化的アルゴリズムを動的に研究し、各世代ごとに異なる適合関数が選択される。
特に、最適化の最も難しい領域は最適化の周辺ではない。
論文 参考訳（メタデータ） (2020-10-26T08:55:53Z) - Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax [1.0965065178451106]
我々は、最適な突然変異率の分析を、OneMax問題の2つの変種に拡張する。
すべての集団サイズを2i mid 0 le i le 18$で計算します。
我々の結果は、一般的な進化的アプローチを測ることのできる低い境界を提供するばかりではない。
論文 参考訳（メタデータ） (2020-06-20T01:23:14Z) - 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) - Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the
Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
我々は,Spanning Tree (MST) 問題を単目的および多目的バージョンで検討する。
我々は、低い支配数の観点から低いランクのエッジの選択に重点を置くバイアス付き突然変異を導入する。
我々は、非偏見または偏見のあるエッジ選択を決定する突然変異演算子の組み合わせが、最悪の場合、上界(unbiased mutation)を示すことを示した。
論文 参考訳（メタデータ） (2020-04-22T07:47:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。