Analysis of evolutionary algorithms on fitness function with time-linkage property (hot-off-the-press track at GECCO 2021)

Weijie ZHENG, Huanhuan CHEN, Xin YAO

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

1 Citation (Scopus)


In real-world applications, many optimization problems have the time-linkage property, that is, the objective function value relies on the current solution as well as the historical solutions. Although the rigorous theoretical analysis on evolutionary algorithms has rapidly developed in the last two decades, it remains an open problem to theoretically understand the behaviors of evolutionary algorithms on time-linkage problems. This paper takes the first step towards the rigorous analyses of evolutionary algorithms for time-linkage functions. Based on the basic OneMax function, we propose a time-linkage function where the first bit value of the last time step is integrated but has a different preference from the current first bit. We prove that with probability 1 - o(1), randomized local search and (1 + 1) EA cannot find the optimum, and with probability 1 - o(1), (+ 1) EA is able to reach the optimum. This paper for the Hot-off-the-Press track at GECCO 2021 summarizes the work "Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property"by W. Zheng, H. Chen, and X. Yao, which has been accepted for publication in the IEEE Transactions on Evolutionary Computation 2021 [19]. © 2021 Owner/Author.
Original languageEnglish
Title of host publicationGECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery, Inc
Number of pages2
ISBN (Print)9781450383516
Publication statusPublished - 7 Jul 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 En-terpreneurial Teams (Grant No. 2017ZT07X386), Shenzhen Science and Technology Program (Grant No. KQTD2016112514355531), the Program for University Key Laboratory of Guangdong Province (Grant No. 2017KSYS008), National Natural Science Foundation of China (Grant No. 61976111), and Science and Technology Innovation Committee Foundation of Shenzhen (Grant No. JCYJ20180504165652917).


  • convergence
  • evolutionary algorithms
  • running time analysis
  • time-linkage


Dive into the research topics of 'Analysis of evolutionary algorithms on fitness function with time-linkage property (hot-off-the-press track at GECCO 2021)'. Together they form a unique fingerprint.

Cite this