| 基于平均增益模型的连续型(1+1)进化算法计算时间复杂性分析 |
| |
| 作者姓名： | 黄翰 徐威迪 张宇山 林智勇 郝志峰 |
| |
| 作者单位： | [1]华南理工大学软件学院,广州510006 [2]广东财经大学数学与统计学院,广州510320 [3]南京大学计算机软件新技术国家重点实验室,南京210093 [4]广东技术师范学院,计算机科学学院,广州510665 [5]广东工业大学计算机学院,广州510006 |
| |
| 基金项目： | 国家自然科学基金（批准号：61370102,61170193,61202453,61203310）、中央高校基本科研业务费（批准号：2012ZZ0087,2014ZG0043）、广东省自然科学基金项目（批准号：$2011040002890,S2012010010613）和珠江科技新星项目（批准号：2012-J22000071资助项目 |
| |
| 摘 要： | ![]()
连续型进化算法的计算时间复杂性分析是进化计算理论研究的一项公开难题,目前相关研究成果较少.针对连续型(1+1)EA,基于适应值差函数提出了平均增益模型及其分析方法,给出了平均计算时间的计算理论,为算法的计算时间复杂性分析提供了依据.在此基础上,研究还选取了学术界关注的球形函数作为研究对象,分别推导了变异步长满足标准正态分布和均匀分布的连续型(1+1)EA在优化球形函数时的平均增益,并估算出了它们的平均计算时间.理论分析说明:1)两种算法的计算时间复杂性都是指数级的;2)在给定相同精度和初始适应值差的前提下,采用均匀分布变异算子的算法其寻优速度优于采用标准正态分布变异算子的算法.进一步地,通过数值实验对理论分析结果进行了验证,结果表明平均增益模型分析是有效的.
|
| 关 键 词： | 进化算法 进化计算理论基础 计算时间复杂性 平均增益模型 Sphere函数 |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
