Paper Info
Title
How can surrogates influence the convergence of evolutionary algorithms?
Abstract
Surrogate-assisted evolutionary algorithms have been widely utilized in science and engineering fields, while rare theoretical results were reported on how surrogates influence the performances of evolutionary algorithms (EAs). This paper focuses on theoretical analysis of a (1+1) surrogate-assisted evolutionary algorithm ((1+1)SAEA), which consists of one individual and pre-evaluates a newly generated candidate using a first-order polynomial model (FOPM) before it is precisely evaluated at each generation. By performing comparisons between a unimodal problem and a multi-modal problem, we rigorously estimate the variation of exploitation ability and exploration ability introduced via the FOPM. Theoretical results show that the FOPM employed to pre-evaluate the candidates sometimes accelerate the convergence of evolutionary algorithms, while sometimes prevents the individuals from converging to the global optimal solution. Thus, appropriate adaptive strategies of candidate generation and surrogate control are needed to accelerate the convergence of the (1+1)EA. Then, the accelerating effect of FOPM decreases monotonically with p, the probability of performing precise function evaluation when a candidate is pre-evaluated worse than the present individual.
Year
DOI
Venue
2013
10.1016/j.swevo.2013.04.005
Swarm and Evolutionary Computation
Keywords
Field
DocType
Theoretical analysis,Surrogate-assisted evolutionary algorithm,First-order polynomial model,Exploitation ability,Exploration ability
Convergence (routing),Monotonic function,Mathematical optimization,Adaptive strategies,Evolutionary algorithm,Evolutionary programming,Polynomial and rational function modeling,Mathematics
Journal
Volume
Issue
ISSN
12
null
2210-6502
Citations 
PageRank 
References 
3
0.39
16
Authors
3
Name
Order
Citations
PageRank
Yu Chen151749.61
Wei-Cheng Xie29412.05
Xiufen Zou327225.44