English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In the first and so far only mathematical runtime analysis of anestimation-of-distribution algorithm (EDA) on a multimodal problem, Hasen\"ohrland Sutton (GECCO 2018) showed for any $k = o(n)$ that the compact geneticalgorithm (cGA) with any hypothetical population size $\mu = \Omega(ne^{4k} +n^{3.5+\varepsilon})$ with high probability finds the optimum of the$n$-dimensional jump function with jump size $k$ in time $O(\mu n^{1.5} \logn)$.  We significantly improve this result for small jump sizes $k \le \frac 1 {20}\ln n -1$. In this case, already for $\mu = \Omega(\sqrt n \log n) \cap\text{poly}(n)$ the runtime of the cGA with high probability is only $O(\mu\sqrt n)$. For the smallest admissible values of $\mu$, our result gives aruntime of $O(n \log n)$, whereas the previous one only shows$O(n^{5+\varepsilon})$. Since it is known that the cGA with high probabilityneeds at least $\Omega(\mu \sqrt n)$ iterations to optimize the unimodal OneMxfunction, our result shows that the cGA in contrast to most classicevolutionary algorithms here is able to cross moderate-sized valleys of lowfitness at no extra cost.  For large $k$, we show that the exponential (in $k$) runtime guarantee ofHasen\"ohrl and Sutton is tight and cannot be improved, also not by using asmaller hypothetical population size. We prove that any choice of thehypothetical population size leads to a runtime that, with high probability, isat least exponential in the jump size $k$. This result might be the firstnon-trivial exponential lower bound for EDAs that holds for arbitrary parametersettings.

The Runtime of the Compact Genetic Algorithm on Jump Functions