连续型进化算法首达时间分析的更新理论模型

连续型进化算法首达时间上界研究中需要较强的前提假设且较少关注其下界.文中引入鞅论和更新过程,结合瓦尔德不等式以及更新定理,提出基于增长率的更新理论模型,用于估计进化策略(Evolution Strategies,ES)平均首达时间的上界和下界.更新理论模型依赖算法的初始种群以及增长率概率密度函数,这为进化策略的首达时间分析提供估计优势.为了验证文中更新理论模型,首先计算带均匀变异(1,λ)ES在二维倾斜平面问题上的平均首达时间,得到(1,λ)ES种群规模与时间上下界之间的关系闭合表达式,并且验证平均首达时间与种群规模之间并非负相关.再计算带均匀变异(1,λ)ES在五维超平面问题上的平均首达时间,得到理论计算的上下界闭合表达式.数值实验表明,理论计算的上界和下界与实际运行平均首达时间一致,这为分析进化策略的首达时间提供一种理论工具.