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

• 作者: 张宇山 杨晓伟 郝志峰 黄翰
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 连续型演化算法 计算时间分析 首达时间 平均增益模型 鞅 停时理论
• 年，卷（期）: 2019,（3）
• 所属期刊栏目: 人工智能
• 页码范围: 624-635
• 页数: 12页
• 分类号: TP18
• 字数: 9326字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2019.00624

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨晓伟	华南理工大学软件学院	38	588	12.0	24.0
2	黄翰	华南理工大学软件学院	50	526	11.0	21.0
3	郝志峰	佛山科学技术学院数学与大数据学院	30	88	7.0	8.0
4	张宇山	广东财经大学统计与数学学院	3	8	1.0	2.0