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

Weijie ZHENG; Huanhuan CHEN; Xin YAO

doi:10.1109/TEVC.2021.3061442

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

Weijie ZHENG, Huanhuan CHEN, Xin YAO

Research output: Journal Publications › Journal 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.

Original language	English
Article number	9360867
Pages (from-to)	696-709
Number of pages	14
Journal	IEEE Transactions on Evolutionary Computation
Volume	25
Issue number	4
Early online date	23 Feb 2021
DOIs	https://doi.org/10.1109/TEVC.2021.3061442
Publication status	Published - Aug 2021
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 1997-2012 IEEE.

Funding

This work was supported in part by the Guangdong Basic and Applied Basic Research Foundation under Grant 2019A1515110177; in part by the Guangdong Provincial Key Laboratory under Grant 2020B121201001; in part by the Program for Guangdong Introducing Innovative and Enterpreneurial Teams under Grant 2017ZT07X386; in part by the Shenzhen Science and Technology Program under Grant KQTD2016112514355531; in part by the Program for University Key Laboratory of Guangdong Province under Grant 2017KSYS008; in part by the National Natural Science Foundation of China under Grant 61976111; and in part by the Science and Technology Innovation Committee Foundation of Shenzhen under Grant JCYJ20180504165652917.

Keywords

Convergence
evolutionary algorithms (EAs)
running time analysis
time linkage

Access to Document

10.1109/TEVC.2021.3061442

Cite this

@article{67e69a3057db4cfb85795c897e89dc61,

title = "Analysis of Evolutionary Algorithms on Fitness Function with Time-Linkage Property",

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.",

keywords = "Convergence, evolutionary algorithms (EAs), running time analysis, time linkage",

author = "Weijie ZHENG and Huanhuan CHEN and Xin YAO",

note = "Publisher Copyright: {\textcopyright} 1997-2012 IEEE.",

year = "2021",

month = aug,

doi = "10.1109/TEVC.2021.3061442",

language = "English",

volume = "25",

pages = "696--709",

journal = "IEEE Transactions on Evolutionary Computation",

issn = "1089-778X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "4",

}

TY - JOUR

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

AU - ZHENG, Weijie

AU - CHEN, Huanhuan

AU - YAO, Xin

PY - 2021/8

Y1 - 2021/8

N2 - 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.

AB - 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.

KW - Convergence

KW - evolutionary algorithms (EAs)

KW - running time analysis

KW - time linkage

UR - http://www.scopus.com/inward/record.url?scp=85101757585&partnerID=8YFLogxK

U2 - 10.1109/TEVC.2021.3061442

DO - 10.1109/TEVC.2021.3061442

M3 - Journal Article (refereed)

SN - 1089-778X

VL - 25

SP - 696

EP - 709

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

IS - 4

M1 - 9360867

ER -

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

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this