  Many real-world applications have the time-linkage property, and the only
theoretical analysis is recently given by Zheng, et al. (TEVC 2021) on their
proposed time-linkage OneMax problem, OneMax$_{(0,1^n)}$. However, only two
elitist algorithms (1+1)EA and ($\mu$+1)EA are analyzed, and it is unknown
whether the non-elitism mechanism could help to escape the local optima existed
in OneMax$_{(0,1^n)}$. In general, there are few theoretical results on the
benefits of the non-elitism in evolutionary algorithms. In this work, we
analyze on the influence of the non-elitism via comparing the performance of
the elitist (1+$\lambda$)EA and its non-elitist counterpart (1,$\lambda$)EA. We
prove that with probability $1-o(1)$ (1+$\lambda$)EA will get stuck in the
local optima and cannot find the global optimum, but with probability $1$,
(1,$\lambda$)EA can reach the global optimum and its expected runtime is
$O(n^{3+c}\log n)$ with $\lambda=c \log_{\frac{e}{e-1}} n$ for the constant
$c\ge 1$. Noting that a smaller offspring size is helpful for escaping from the
local optima, we further resort to the compact genetic algorithm where only two
individuals are sampled to update the probabilistic model, and prove its
expected runtime of $O(n^3\log n)$. Our computational experiments also verify
the efficiency of the two non-elitist algorithms.
