Analysis of Evolutionary Algorithms on Fitness Function with Time-Linkage Property

Weijie ZHENG, Huanhuan CHEN, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

13 Citations (Scopus)

Abstract

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 (EAs) has rapidly developed in recent two decades, it remains an open problem to theoretically understand the behaviors of EAs on time-linkage problems. This article takes the first step to rigorously analyze EAs 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)$ , $(\mu +1)$ EA is able to reach the optimum. © 1997-2012 IEEE.
Original languageEnglish
Article number9360867
Pages (from-to)696-709
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Volume25
Issue number4
Early online date23 Feb 2021
DOIs
Publication statusPublished - Aug 2021
Externally publishedYes

Keywords

  • Convergence
  • evolutionary algorithms (EAs)
  • running time analysis
  • time linkage

Fingerprint

Dive into the research topics of 'Analysis of Evolutionary Algorithms on Fitness Function with Time-Linkage Property'. Together they form a unique fingerprint.

Cite this