连续型演化算法首达时间分析的平均增益模型

摘要：

连续型演化算法(Evolutionary Algorithms,EAs)的计算时间分析(Runtime analysis)是演化计算理论研究中的难点和热点问题,相较于离散型演化算法,有关前者的理论结果相对较少,数学基础较为薄弱.该文引入鞅论和停时理论,建立了平均增益模型,以估算连续型演化算法的平均首达时间(Expected First Hitting Time,EFHT)上界.平均增益模型建立在一个非负随机过程的基础上,不依赖于算法具体的实现形式.论文介绍了如何应用该模型进行连续型演化算法的计算时间分析.作为案例分析,研究分析了:(1)带自适应步长的非精英(1,λ) ES(Evolution Strategy)求解球函数问题的平均首达时间,得到了3维情形下的时间上界的闭合表达式,并讨论了确保算法收敛条件下步长与子代种群规模λ之间的关系;(2)(1+λ)ES求解2维倾斜平面问题的平均首达时间,得到了上界的闭合表达式.数值实验的结果表明实际的平均首达时间与理论计算的上界吻合.理论分析和实验结果表明平均增益模型有助于获得连续型演化算法平均首达时间紧致的上界,为连续型演化算法的计算时间分析提供了一种新的有效方法.

关键词：连续型演化算法、计算时间分析、首达时间、平均增益模型、鞅、停时理论

所属期刊栏目：42

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金61876207;教育部-中国移动科研基金MCM20160206;广东省自然科学杰出青年基金项目2014A030306050;广东省特支计划人才专项课题2014TQ01X664;广州市科学技术局项目201707010227

在线出版日期：2019-06-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：624-635