基于平均增益模型的连续(1 + 1)进化算法的运行时分析

连续进化算法(EA)的运行时分析是进化计算的理论基础中的一个悬而未决的问题。 与离散EA的运行时研究相比,关于它的结果更少。 以(1 + 1)EA为例,提出了一种平均增益模型及其计算方法,以产生一种运行时分析理论,作为计算时间复杂度的指标。 基于标准正态分布和均匀分布的突变,计算了平均增益以估计两个(1 + 1)EA的平均运行时间,这是许多研究人员关注的Sphere函数。 分析结果表明,(1 + 1)EAs的计算时间复杂度是指数级的。 此外,在具有相同的误差精度和初始距离的情况下,均匀分布突变的求解速度要快于标准正态分布。 数值结果也验证了所提出理论的正确性和平均增益模型的有效性。