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

In the last decade remarkable progress has been made in development ofsuitable proof techniques for analysing randomised search heuristics. Thetheoretical investigation of these algorithms on classes of functions isessential to the understanding of the underlying stochastic process. Linearfunctions have been traditionally studied in this area resulting in tightbounds on the expected optimisation time of simple randomised search algorithmsfor this class of problems. Recently, the constrained version of this problemhas gained attention and some theoretical results have also been obtained onthis class of problems. In this paper we study the class of linear functionsunder uniform constraint and investigate the expected optimisation time ofRandomised 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 previouslybest known upper bound of (1+1) EA from $O(n^2 \log (Bw_{\max}))$ to $O(n^2\logB)$ 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 andthe bound of the uniform constraint, respectively. Also, we obtain a tightbound of $O(n^2)$ for the (1+1) EA on a special class of instances. Wecomplement our theoretical studies by experimental investigations that considerdifferent values of $B$ and also higher mutation rates that reflect the factthat $2$-bit flips are crucial for dealing with the uniform constraint.

Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform Constraint