論文の概要: Theoretical Analyses of Evolutionary Algorithms on Time-Linkage OneMax
with General Weights
- arxiv url: http://arxiv.org/abs/2305.07098v1
- Date: Thu, 11 May 2023 19:01:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-15 14:45:33.843199
- Title: Theoretical Analyses of Evolutionary Algorithms on Time-Linkage OneMax
with General Weights
- Title（参考訳）: 一般化重み付き時間リンクOneMax上の進化的アルゴリズムの理論解析
- Authors: Weijie Zheng and Xin Yao
- Abstract要約: 一般時間リンク効果を解析し、絶対値が強度を反映し、符号が正あるいは負の影響を反映する一般重み付き時間リンクOneMaxについて考察する。
我々は, 時間リンク効果が小さい(0ドルと1ドル)以外は, ランダム化局所探索 (RLS) と (1+1)EA は, 正の確率で大域的最適値に収束できないことを証明した。
- 参考スコア（独自算出の注目度）: 9.89901717499058
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary computation has shown its superiority in dynamic optimization,
but for the (dynamic) time-linkage problems, some theoretical studies have
revealed the possible weakness of evolutionary computation. Since the
theoretically analyzed time-linkage problem only considers the influence of an
extremely strong negative time-linkage effect, it remains unclear whether the
weakness also appears in problems with more general time-linkage effects.
Besides, understanding in depth the relationship between time-linkage effect
and algorithmic features is important to build up our knowledge of what
algorithmic features are good at what kinds of problems. In this paper, we
analyze the general time-linkage effect and consider the time-linkage OneMax
with general weights whose absolute values reflect the strength and whose sign
reflects the positive or negative influence. We prove that except for some
small and positive time-linkage effects (that is, for weights $0$ and $1$),
randomized local search (RLS) and (1+1)EA cannot converge to the global optimum
with a positive probability. More precisely, for the negative time-linkage
effect (for negative weights), both algorithms cannot efficiently reach the
global optimum and the probability of failing to converge to the global optimum
is at least $1-o(1)$. For the not so small positive time-linkage effect
(positive weights greater than $1$), such a probability is at most $c+o(1)$
where $c$ is a constant strictly less than $1$.
- Abstract（参考訳）: 進化的計算は動的最適化において優位性を示しているが、(動的)時間リンク問題に対して、いくつかの理論的研究は進化的計算の弱点を明らかにしている。
理論的に解析された時間連鎖問題は、非常に強い負の時間連鎖効果の影響のみを考慮し、より一般的な時間連鎖効果の問題にも弱が現れるかどうかは不明である。
さらに,時間連鎖効果とアルゴリズム的特徴との関係を深く理解することは,アルゴリズム的特徴がどのような問題に優れているかを知る上で重要である。
本稿では,一般時間連鎖効果を分析し,絶対値が強みを反映し,符号が正または負の影響を反映する一般重み付き時間結合型onemaxについて考察する。
我々は, 時間リンク効果が小さい(0ドルと1ドル)以外は, ランダム化局所探索 (RLS) と (1+1)EA は, 正の確率で大域的最適値に収束できないことを証明した。
より正確には、負の時間リンク効果(負の重み付けの場合)では、両方のアルゴリズムは効率的に大域最適に到達できず、大域最適に収束しない確率は少なくとも1-o(1)$である。
それほど小さな正の時間リンク効果(正の重みが1ドルより大きい)に対して、そのような確率は少なくとも$c+o(1)$であり、$c$は厳密に1ドル以下である。
関連論文リスト
- Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function [2.038038953957366]
GOMEAは、リンク学習を利用して問題構造を効率的に活用する進化的アルゴリズムである。
GOMEAは確率の高い$O(m32k)$で解くことができ、$m$はサブファンクションの数、$k$はサブファンクションの長さである。
これは (1+1) 進化的 EA と比較して大きなスピードアップであり、これは$O(ln(m)(mk)k)$期待される評価を必要とする。
論文 参考訳（メタデータ） (2024-07-11T09:37:21Z) - Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - Towards Understanding the Generalizability of Delayed Stochastic
Gradient Descent [63.43247232708004]
非同期で実行される勾配降下は、大規模機械学習モデルのトレーニングにおいて重要な役割を果たす。
既存の一般化誤差境界は悲観的であり、非同期遅延と一般化の相関を明らかにすることはできない。
我々の理論的結果は、非同期遅延は遅延SGDアルゴリズムの一般化誤差を低減することを示唆している。
論文 参考訳（メタデータ） (2023-08-18T10:00:27Z) - Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。
本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
論文 参考訳（メタデータ） (2023-08-17T08:34:58Z) - 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) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳（メタデータ） (2021-10-29T06:35:44Z) - When Non-Elitism Meets Time-Linkage Problems [19.798298260257432]
Elitist (1+$lambda$)EAと非elitist (1,$lambda$)EAのパフォーマンスを比較することにより、非elitismの影響を分析します。
確率1$(1,$lambda$)EAがグローバルな最適値に到達でき、期待されるランタイムは$O(n3+clog n)$ with $lambda=c log_fracee-1 n$ for the constant $cge 1$であることを示す。
論文 参考訳（メタデータ） (2021-04-14T13:03:42Z) - 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) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Analysis of Evolutionary Algorithms on Fitness Function with
Time-linkage Property [27.660240128423176]
実世界のアプリケーションでは、多くの最適化問題には時間リンク性があり、すなわち、目的関数の値は現在の解と過去の解に依存する。
本稿では,時間連鎖関数の進化的アルゴリズムを厳格に解析する第一歩を踏み出した。
論文 参考訳（メタデータ） (2020-04-26T07:56:40Z) - Revisiting SGD with Increasingly Weighted Averaging: Optimization and
Generalization Perspectives [50.12802772165797]
平均化手法は、全ての反復解を一つの解に結合する。
実験は、他の平均化方式と比較して、トレードオフと平均化の有効性を示した。
論文 参考訳（メタデータ） (2020-03-09T18:14:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。