# When Non-Elitism Meets Time-Linkage Problems

arXiv: https://arxiv.org/abs/2104.06831 · HTML: https://mlsanity.com/paper/2104.06831/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 14 Apr 2021.

## Builds on (most cited first, 13 of 13)

- [Does Comma Selection Help To Cope With Local Optima](https://mlsanity.com/paper/2004.01274/) (2020)
- [The Runtime of the Compact Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/1908.06527/) (2019)
- [On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help](https://mlsanity.com/paper/1907.12438/) (2019)
- [Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms](https://mlsanity.com/paper/1910.14389/) (2019)
- [The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis](https://mlsanity.com/paper/2007.08277/) (2020)
- [First Steps Towards a Runtime Comparison of Natural and Artificial Evolution](https://mlsanity.com/paper/1504.06260/) (2015)
- [When Hypermutations and Ageing Enable Artificial Immune Systems to Outperform Evolutionary Algorithms](https://mlsanity.com/paper/1804.01314/) (2018)
- [Fast Artificial Immune Systems](https://mlsanity.com/paper/1806.00299/) (2018)
- [Theory of Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/1806.05392/) (2018)
- [From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm](https://mlsanity.com/paper/2004.07141/) (2020)
- [The Benefits of Population Diversity in Evolutionary Algorithms: A Survey of Rigorous Runtime Analyses](https://mlsanity.com/paper/1801.10087/) (2018)
- [Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property](https://mlsanity.com/paper/2004.12304/) (2020)
- [Working Principles of Binary Differential Evolution](https://mlsanity.com/paper/1812.03513/) (2018)

## Built on by (most cited first, 1 of 1)

- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)

## Abstract (arXiv)

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,1n). However, only two elitist algorithms (1+1)EA and (μ+1)EA are analyzed, and it is unknown whether the non-elitism mechanism could help to escape the local optima existed in OneMax(0,1n). 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+λ)EA and its non-elitist counterpart (1,λ)EA. We prove that with probability 1-o(1) (1+λ)EA will get stuck in the local optima and cannot find the global optimum, but with probability 1, (1,λ)EA can reach the global optimum and its expected runtime is O(n3+clog n) with λ=c log_fracee-1 n for the constant c≥ 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(n3log n). Our computational experiments also verify the efficiency of the two non-elitist algorithms.