論文の概要: Improved Runtime Results for Simple Randomised Search Heuristics on
Linear Functions with a Uniform Constraint
- arxiv url: http://arxiv.org/abs/2010.10885v1
- Date: Wed, 21 Oct 2020 10:42:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 22:40:34.553741
- Title: Improved Runtime Results for Simple Randomised Search Heuristics on
Linear Functions with a Uniform Constraint
- Title(参考訳): 一様制約付き線形関数の単純なランダム化探索ヒューリスティックに対する実行時間の改善
- Authors: Frank Neumann and Mojgan Pourhassan and Carsten Witt
- Abstract要約: 均一制約下での線形関数のクラスについて検討し、ランダム化局所探索(RLS)の期待最適時間について検討する。
RLS に対して $Theta(n2)$ の厳密な境界を証明し、(1+1) EA の既知上界を改善する。
- 参考スコア(独自算出の注目度): 11.228244128564512
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the last decade remarkable progress has been made in development of
suitable proof techniques for analysing randomised search heuristics. The
theoretical investigation of these algorithms on classes of functions is
essential to the understanding of the underlying stochastic process. Linear
functions have been traditionally studied in this area resulting in tight
bounds on the expected optimisation time of simple randomised search algorithms
for this class of problems. Recently, the constrained version of this problem
has gained attention and some theoretical results have also been obtained on
this class of problems. In this paper we study the class of linear functions
under uniform constraint and investigate the expected optimisation time of
Randomised Local Search (RLS) and a simple evolutionary algorithm called (1+1)
EA. We prove a tight bound of $\Theta(n^2)$ for RLS and improve the previously
best known upper bound of (1+1) EA from $O(n^2 \log (Bw_{\max}))$ to $O(n^2\log
B)$ in expectation and to $O(n^2 \log n)$ with high probability, where
$w_{\max}$ and $B$ are the maximum weight of the linear objective function and
the bound of the uniform constraint, respectively. Also, we obtain a tight
bound of $O(n^2)$ for the (1+1) EA on a special class of instances. We
complement our theoretical studies by experimental investigations that consider
different values of $B$ and also higher mutation rates that reflect the fact
that $2$-bit flips are crucial for dealing with the uniform constraint.
- Abstract(参考訳): 過去10年間で、ランダム化された探索ヒューリスティックを解析するための適切な証明手法の開発が目覚ましい進歩を遂げた。
これらのアルゴリズムの関数のクラスに関する理論的研究は、基礎となる確率過程の理解に不可欠である。
線形関数はこの領域で伝統的に研究されており、この問題に対する単純なランダム化探索アルゴリズムの期待最適時間に厳密な境界がある。
近年、制約付きバージョンが注目され、このタイプの問題についてもいくつかの理論的な結果が得られている。
本稿では,一様制約下での線形関数のクラスを調べ,ランダム化局所探索 (rls) の期待最適化時間と (1+1) ea と呼ばれる単純な進化アルゴリズムについて検討する。
rls に対する $\theta(n^2)$ の厳密な境界を証明し、(1+1) ea の既知の上限を、期待値の $o(n^2 \log (bw_{\max}))$ to $o(n^2\log b)$ から高確率で $o(n^2 \log n)$ へと改善する。
また、特別なインスタンスのクラス上の (1+1) EA に対して$O(n^2)$ の厳密な境界を得る。
b$の異なる値を考える実験的調査と、2ドルビットのフリップが一様制約に対処するために不可欠であるという事実を反映した突然変異率の上昇によって、理論的研究を補完します。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳(メタデータ) (2023-06-03T17:05:13Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳(メタデータ) (2023-03-22T03:05:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳(メタデータ) (2022-12-03T02:45:23Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳(メタデータ) (2022-03-30T11:39:00Z) - Focused Jump-and-Repair Constraint Handling for Fixed-Parameter
Tractable Graph Problems Closed Under Induced Subgraphs [3.495114525631289]
グラフ問題における不可能な子孫の確率的修復に使用できる調整されたジャンプ・アンド・リペア操作を備えた(1+1)EAについて検討する。
論文 参考訳(メタデータ) (2022-03-25T19:36:02Z) - A stochastic linearized proximal method of multipliers for convex
stochastic optimization with expectation constraints [8.133190610747974]
計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。
予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
論文 参考訳(メタデータ) (2021-06-22T07:24:17Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-05-05T18:28:42Z) - Analysis of Evolutionary Algorithms on Fitness Function with
Time-linkage Property [27.660240128423176]
実世界のアプリケーションでは、多くの最適化問題には時間リンク性があり、すなわち、目的関数の値は現在の解と過去の解に依存する。
本稿では,時間連鎖関数の進化的アルゴリズムを厳格に解析する第一歩を踏み出した。
論文 参考訳(メタデータ) (2020-04-26T07:56:40Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。