When non-elitism meets time-linkage problems

Zheng，Weijie1; Zhang，Qiaozhi1; Chen，Huanhuan2; Yao，Xin1

10.1145/3449639.3459347

2021-06-26

2nd Genetic and Evolutionary Computation Conference (GECCO)

GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference

741-749

JUL 10-14, 2021

null,null,ELECTR NETWORK

1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES

ASSOC COMPUTING MACHINERY

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.

Evolutionary algorithms Non-elitism Runtime analysis Theory Time-linkage

第一 ; 通讯

英语

CPCI-S ; EI

Guangdong Basic and Applied Basic Research Foundation[2019A1515110177] ; Guangdong Provincial Key Laboratory[2020B121201001] ; Program for Guangdong Introducing Innovative and Enterpreneurial Teams[2017ZT07X386] ; Shenzhen Science and Technology Program[KQTD2016112514355531]

Computer Science ; Operations Research & Management Science ; Mathematics

Computer Science, Artificial Intelligence ; Computer Science, Theory & Methods ; Operations Research & Management Science ; Mathematics, Applied

WOS:000773791800087

20212910647518

Genetic algorithms

2-s2.0-85110105255

Scopus

1.Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,China
2.School of Computer Science and Technology,University of Science and Technology of China,Hefei,China

Zheng，Weijie,Zhang，Qiaozhi,Chen，Huanhuan,et al. When non-elitism meets time-linkage problems[C]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2021:741-749.