Outcomes

How can surrogates influence the convergence of evolutionary algorithms?

期刊名称: Swarm and Evolutionary Computation
全部作者: Yu Chen*, Weicheng Xie, Xiufen Zou
出版年份: 2013
卷       号: 12
期       号:
页       码:
查看全本:      
Surrogate-assisted evolutionary algorithms have been widely utilized in science and engineering fields, while  rare  theoretical  results  were  reported  on  how  surrogates  in fl uence  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 fi rst-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.