基于平均增益模型的连续型(1+1)进化算法计算时间复杂性分析

Runtime analysis for continuous(1+1) evolutionary algorithm based on average gain model

连续型进化算法的计算时间复杂性分析是进化计算理论研究的一项公开难题,目前相关研究成果较少.针对连续型(1+1)EA,基于适应值差函数提出了平均增益模型及其分析方法,给出了平均计算时间的计算理论,为算法的计算时间复杂性分析提供了依据.在此基础上,研究还选取了学术界关注的球形函数作为研究对象,分别推导了变异步长满足标准正态分布和均匀分布的连续型(1+1)EA在优化球形函数时的平均增益,并估算出了它们的平均计算时间.理论分析说明:1)两种算法的计算时间复杂性都是指数级的;2)在给定相同精度和初始适应值差的前提下,采用均匀分布变异算子的算法其寻优速度优于采用标准正态分布变异算子的算法.进一步地,通过数值实验对理论分析结果进行了验证,结果表明平均增益模型分析是有效的.

Runtime analysis of continuous evolutionary algorithm （EA） is an open problem in theoretical foun- dation of evolutionary computation. There are fewer results about it than the runtime studies of discrete EA. For an example of （1＋1）EA, an average gain model and its calculating method were proposed to produce a theory of runtime analysis as an index of computational time complexity. The average gain was computed to estimate the average runtime of two （1＋1）EAs based on the mutation of standard normal distribution and uniform distribution, for Sphere function which is focused on by many researchers. The analysis result indicates that computational time complexity of the （1＋1）EAs is exponential order. Furthermore, the solution speed of uniform-distribution mutation is faster than standard normal distribution with the same error accuracy and initial distance. Numerical results also verify the correctness of the proposed theory and the usefulness of the average gain model.