論文の概要: Analysis of Evolutionary Algorithms on Fitness Function with
Time-linkage Property
- arxiv url: http://arxiv.org/abs/2004.12304v4
- Date: Wed, 24 Feb 2021 01:13:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-09 13:19:09.702871
- Title: Analysis of Evolutionary Algorithms on Fitness Function with
Time-linkage Property
- Title（参考訳）: 時間リンク特性を持つフィトネス関数の進化的アルゴリズムの解析
- Authors: Weijie Zheng, Huanhuan Chen, Xin Yao
- Abstract要約: 実世界のアプリケーションでは、多くの最適化問題には時間リンク性があり、すなわち、目的関数の値は現在の解と過去の解に依存する。
本稿では,時間連鎖関数の進化的アルゴリズムを厳格に解析する第一歩を踏み出した。
- 参考スコア（独自算出の注目度）: 27.660240128423176
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In real-world applications, many optimization problems have the time-linkage
property, that is, the objective function value relies on the current solution
as well as the historical solutions. Although the rigorous theoretical analysis
on evolutionary algorithms has rapidly developed in recent two decades, it
remains an open problem to theoretically understand the behaviors of
evolutionary algorithms on time-linkage problems. This paper takes the first
step to rigorously analyze evolutionary algorithms for time-linkage functions.
Based on the basic OneMax function, we propose a time-linkage function where
the first bit value of the last time step is integrated but has a different
preference from the current first bit. We prove that with probability $1-o(1)$,
randomized local search and $(1+1)$ EA cannot find the optimum, and with
probability $1-o(1)$, $(\mu+1)$ EA is able to reach the optimum.
- Abstract（参考訳）: 実世界のアプリケーションでは、多くの最適化問題には時間-リンケージ特性、すなわち目的関数の値は、過去のソリューションと同様に現在のソリューションに依存する。
進化的アルゴリズムに関する厳密な理論解析は、近年急速に発展してきたが、時間連鎖問題における進化的アルゴリズムの挙動を理論的に理解するオープンな問題である。
本稿では,時間連鎖関数の進化的アルゴリズムを厳密に解析する第一歩を踏み出す。
基本のOneMax関数に基づいて、最後の時間ステップの最初のビット値が統合されるが、現在の第1ビットとは異なる好みを持つ時間リンク関数を提案する。
確率1-o(1)$、確率1-o(1)$、確率1+1$ EAが最適を見つけることができず、確率1-o(1)$、$(\mu+1)$ EAが最適に到達できることを示す。
関連論文リスト
- 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) - Time Complexity Analysis of Evolutionary Algorithms for 2-Hop
(1,2)-Minimum Spanning Tree Problem [20.624629608537894]
2-Hop (1,2)-Minimum Spanning Tree problem (略MSTP) の制約付きバージョンを進化アルゴリズムの文脈で検討し、NPハードであることが示されている。
2-ホップスパンニングツリーの特別な構造に着想を得て、(1+1) EA はエッジベース表現の探索点を持ち、これは問題にはあまり自然とは思えず、期待する時間に上限を与えて$frac32$-approximate の解を得る。
論文 参考訳（メタデータ） (2021-10-10T04:35:02Z) - 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) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Improved Runtime Results for Simple Randomised Search Heuristics on
Linear Functions with a Uniform Constraint [11.228244128564512]
均一制約下での線形関数のクラスについて検討し、ランダム化局所探索(RLS)の期待最適時間について検討する。
RLS に対して $Theta(n2)$ の厳密な境界を証明し、(1+1) EA の既知上界を改善する。
論文 参考訳（メタデータ） (2020-10-21T10:42:39Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - First Steps Towards a Runtime Analysis When Starting With a Good
Solution [8.34061303235504]
現実的な応用では、ランダムな解よりも優れた解を推測することができる。
我々は、異なるアルゴリズムがより良い初期解と全く異なる程度に利益を得ることを示す。
このことは、進化的アルゴリズムが良い初期解をうまく活用していることがまだ見つからないことを示唆している。
論文 参考訳（メタデータ） (2020-06-22T11:46:42Z) - 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) - Incorporating Expert Prior in Bayesian Optimisation via Space Warping [54.412024556499254]
大きな探索空間では、アルゴリズムは関数の最適値に達する前に、いくつかの低関数値領域を通過する。
このコールドスタートフェーズの1つのアプローチは、最適化を加速できる事前知識を使用することである。
本稿では,関数の事前分布を通じて,関数の最適性に関する事前知識を示す。
先行分布は、探索空間を最適関数の高確率領域の周りに拡張し、最適関数の低確率領域の周りに縮小するようにワープする。
論文 参考訳（メタデータ） (2020-03-27T06:18:49Z) - A new regret analysis for Adam-type algorithms [78.825194932103]
理論的には、オンライン凸最適化に対する後悔の保証は、急速に崩壊する$beta_1to0$スケジュールを必要とする。
最適なデータ依存リセット境界を一定の$beta_1$で導出できる新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-21T19:19:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。