論文の概要: The $(1+(\lambda,\lambda))$ Global SEMO Algorithm

• arxiv url: http://arxiv.org/abs/2210.03618v1
• Date: Fri, 7 Oct 2022 15:18:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-10 12:39:02.300533
• Title: The $(1+(\lambda,\lambda))$ Global SEMO Algorithm
• Title（参考訳）: 1+(\lambda,\lambda)$ Global SEMOアルゴリズム
• Authors: Benjamin Doerr, Omar El Hadri, Adrien Pinard
• Abstract要約: 我々は、$(lambda,lambda)$の遺伝的計算を多目的進化計算に転送できることを示した。 我々は,従来のグローバルSEMOアルゴリズムの変種である$(lambda,lambda)$ global SEMOアルゴリズムを定義し,OneMinMaxアルゴリズムがグローバルSEMOよりもベンチマークで高速であることを証明した。
• 参考スコア（独自算出の注目度）: 8.34061303235504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The $(1+(\lambda,\lambda))$ genetic algorithm is a recently proposed single-objective evolutionary algorithm with several interesting properties. We show that its main working principle, mutation with a high rate and crossover as repair mechanism, can be transported also to multi-objective evolutionary computation. We define the $(1+(\lambda,\lambda))$ global SEMO algorithm, a variant of the classic global SEMO algorithm, and prove that it optimizes the OneMinMax benchmark asymptotically faster than the global SEMO. Following the single-objective example, we design a one-fifth rule inspired dynamic parameter setting (to the best of our knowledge for the first time in discrete multi-objective optimization) and prove that it further improves the runtime to $O(n^2)$, whereas the best runtime guarantee for the global SEMO is only $O(n^2 \log n)$.
• Abstract（参考訳）: 1+(\lambda,\lambda))$ 遺伝的アルゴリズムは、最近提案されたいくつかの興味深い特性を持つ1目的進化アルゴリズムである。 我々は,その主な作業原理である高いレートの変異と修復機構としてのクロスオーバーが,多目的進化計算にも応用可能であることを示す。 我々は,従来のグローバルSEMOアルゴリズムの変種である$(1+(\lambda,\lambda)$ Global SEMOアルゴリズムを定義し,OneMinMaxベンチマークをグローバルSEMOよりも漸近的に高速に最適化することを証明する。 単目的の例に続いて、我々は1/5ルールにインスパイアされた動的パラメータ設定を設計し(離散多目的最適化において初めて知識を最大限に活用するために)、ランタイムをさらに$O(n^2)$に改善する一方、グローバルSEMOの最良のランタイム保証は$O(n^2 \log n)$にしかならないことを証明した。

関連論文リスト

• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。 本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
  論文  参考訳（メタデータ） (2023-08-17T08:34:58Z)
• The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
  NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。 従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して、初めて証明された性能保証を与える。
  論文  参考訳（メタデータ） (2023-05-22T19:59:19Z)
• Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise [7.421135890148154]
  対象関数にノイズが存在する場合の古典的ベンチマークの最初の解析を行う。 ビット単位の先行ノイズが$p le alpha/n$, $alpha$ a suitable constant であることを示す。 すべての解が各イテレーションで再評価されると、ノイズレート$p = omega(log(n)/n2)$がスーパーポリノミカルランタイムにつながることが証明される。
  論文  参考訳（メタデータ） (2023-05-17T14:48:06Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。 我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
  論文  参考訳（メタデータ） (2022-11-03T14:12:51Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
  主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。 LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
  論文  参考訳（メタデータ） (2021-11-15T17:10:40Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [15.56430085052365]
  OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。 確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。 また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
  論文  参考訳（メタデータ） (2020-12-14T03:07:39Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property [27.660240128423176]
  実世界のアプリケーションでは、多くの最適化問題には時間リンク性があり、すなわち、目的関数の値は現在の解と過去の解に依存する。 本稿では,時間連鎖関数の進化的アルゴリズムを厳格に解析する第一歩を踏み出した。
  論文  参考訳（メタデータ） (2020-04-26T07:56:40Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。