演化算法在连续搜索空间上的时间复杂度分析

摘要

自提出以来，演化算法就受到学术界的持续关注，同时在实际工程领域中得到广泛的应用。作为基于种群的随机优化算法，演化算法不仅能够克服传统优化算法的许多缺点，例如依赖于目标函数的梯度或者海森矩阵、在多峰问题上性能不好、对初始点的选取敏感等等，并且在解决实际问题时有着非常好的表现。然而，演化算法运行过程的随机性，也使得对它的时间复杂度的研究变得困难，进而成为限制其进一步发展的瓶颈。 近二十年来，对演化算法的时间复杂度的研究也逐渐成为该领域内的研究热点。从早期的定性分析过渡到现在的定量分析，该领域中涌现出许多优秀的理论成果。然而，现有的工作主要集中在对离散型演化算法的分析。连续优化问题是实际工程中更常见的一类问题，但是针对它的时间复杂性研究仍然十分稀少。因此，将重点分析连续型演化算法的时间复杂度，以弥补当前研究现状的不足。本文的主要贡献可归纳为以下几点: 1.总结了连续型演化算法的理论分析领域的相关工作。根据成果的类型，将现有的理论成果分为局部性态分析和渐进分析。渐进分析的理论成果，按照所分析的算法类型又可以分为基于个体的和基于种群的。 2.提升了使用超球体内均匀分布变异算子的演化算法的下界。变异算子是演化算法中的重要部件之一，它表示算法的搜索方向，并且会直接影响到算法的时间复杂度。在本文中，考虑一种常见的变异算子——均匀分布变异算子，并将其下界从目前最优的下界Ω（n）提升至Ω（ecn），即从多项式时间下界提升至指数级时间下界。 3.分析了1/5规则在超球体内均匀分布变异算子上的效用。1/5规则是连续型演化算法中用来调整变异强度的一个常用的启发式策略。在本文中，证明了使用1/5规则可以将算法的时间复杂度从Ω（ecn）降为O(n)，即从指数级时间降为多项式时间。

目录

声明

摘要

第1章绪论

1．1演化算法简介

1．2演化算法理论分析历史

1．2．1定性分析

1．2．2定量分析

1．3本文组织框架

第2章连续型演化算法

2．1 连续型演化算法简介

2．1．1 连续型演化算法的个体编码方式

2．1．2连续型演化算法的初始化和终止条件

2．1．3连续型演化算法的变异和交叉算子

2．1．4连续型演化算法的参数设置方法

2．2连续型演化算法的理论分析概述

2．2．1 连续型演化算法的理论分析工具

2．2．2连续型演化算法的局部性态分析

2．2．3问题维度为2时的一个案例

2．2．4基于个体的演化算法的渐进分析

2．2．5基于种群的演化算法的渐进分析

2．3本章小结

第3章(1+1)-ES在超球函数上的指数级下界

3．1 超球体内的均匀分布算子

3．1．1准备知识

3．1．2下界定理

3．2高斯分布变异算子

3．3实验部分

3．3．1 变异算子实现方法

3．3．2实验参数设置

3．3．3实验结果和分析

3．4本章小结

第4章1／5规则的效用分析

4．1 1／5规则简介

4．2准备知识

4．3 1／5规则在均匀分布变异算子上的有效性

4．4实验部分

4．4．1算法实现

4．4．2实验参数设置

4．4．3实验结果和分析

4．5本章小结

第5章总结

5．1本文的主要贡献

5．2未来的发展趋势

参考文献

致谢

在读期间发表的学术论文与取得的研究成果