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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Estimation of Distribution Algorithms (EDAs) are stochastic heuristics thatsearch for optimal solutions by learning and sampling from probabilisticmodels. Despite their popularity in real-world applications, there is littlerigorous understanding of their performance. Even for the Univariate MarginalDistribution Algorithm (UMDA) -- a simple population-based EDA assumingindependence between decision variables -- the optimisation time on the linearproblem OneMax was until recently undetermined. The incomplete theoreticalunderstanding of EDAs is mainly due to lack of appropriate analytical tools.  We show that the recently developed level-based theorem for non-elitistpopulations combined with anti-concentration results yield upper bounds on theexpected optimisation time of the UMDA. This approach results in the bound$\mathcal{O}(n\lambda\log \lambda+n^2)$ on two problems, LeadingOnes andBinVal, for population sizes $\lambda>\mu=\Omega(\log n)$, where $\mu$ and$\lambda$ are parameters of the algorithm. We also prove that the UMDA withpopulation sizes $\mu\in \mathcal{O}(\sqrt{n}) \cap \Omega(\log n)$ optimisesOneMax in expected time $\mathcal{O}(\lambda n)$, and for larger populationsizes $\mu=\Omega(\sqrt{n}\log n)$, in expected time$\mathcal{O}(\lambda\sqrt{n})$. The facility and generality of our argumentssuggest that this is a promising approach to derive bounds on the expectedoptimisation time of EDAs.

Level-Based Analysis of the Univariate Marginal Distribution Algorithm