When non-elitism meets time-linkage problems

Weijie ZHENG, Qiaozhi ZHANG, Huanhuan CHEN, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

6 Citations (Scopus)


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+c log n) with [EQUATION] 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(n3 log n). Our computational experiments also verify the efficiency of the two non-elitist algorithms. © 2021 ACM.
Original languageEnglish
Title of host publicationGECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery, Inc
Number of pages9
ISBN (Print)9781450383509
Publication statusPublished - 26 Jun 2021
Externally publishedYes

Bibliographical note

This work was supported by Guangdong Basic and Applied Basic Research Foundation (Grant No. 2019A1515110177), Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the Program for Guangdong Introducing Innovative and Enterpreneurial Teams (Grant No. 2017ZT07X386), Shenzhen Science and Technology Program (Grant No. KQTD2016112514355531).


  • Evolutionary algorithms
  • Non-elitism
  • Runtime analysis
  • Theory
  • Time-linkage


Dive into the research topics of 'When non-elitism meets time-linkage problems'. Together they form a unique fingerprint.

Cite this