连续型演化算法的计算时间复杂性对比与估算方法研究

连续型演化算法广泛应用于工业优化与设计，然而长期以来鲜有计算时间复杂性的研究结论。因此，其计算时间复杂性的研究被公认是演化计算领域的热点难题。该研究的关键点在于描述算法搜索行为在连续状态空间的随机过程。现有研究主要针对一些算法的简化版本在某些简单问题实例的计算时间复杂性，所涉及的随机过程较为简单；但实用算法求解实际问题实例的随机过程较为复杂，应用现有理论方法的局限性随之凸显。本课题将演化算法视为一种“赌博”型随机过程，并基于鞅论，研究算法状态转移与适应值差逼近的平均增益模型，提出适用于连续型演化算法的计算时间分析理论与性能对比方法。与传统理论研究不同，本研究还将结合数值实验和统计方法，提出适用于实用连续型演化算法的计算时间复杂性估算方法，达到理论指导应用的目的。本研究还将发展演化算法的理论研究，并为其在相关领域的应用奠定数学基础，为连续型演化算法提供计算时间复杂性的“算法名片”。

Although continuous evolutionary algorithm is widely used in industrial optimization and design, research on time complexity is underexplored. Thus, time complexity analysis of continuous evolutionary algorithm is a challenging open problem in the theoretical foundation research of evolutionary computation. The essentials of such studies lie in how to describe the stochastic process of continuous state space in the behavior of algorithm search. The existing research has solved time complexity of the simple problem through construction simple algorithms with properties of simple stochastic process. Given that the stochastic process of solving practical problems in practical algorithm are much more complex, the approach used by prior studies has its limitations. This study adopts a new perspective by considering evolutionary algorithm as a beneficial gambling process. Based on martingale theory, we will study the state transition of algorithm and different fusion on fitness value with average gain model, and propose runtime analysis theory and efficacy comparison method about continuous evolutionary algorithm. Different from the traditional theoretical research, this study will also derive time complexity estimation applicable to continuous evolutionary algorithm to apply theory to practice. The main significance of the research is threefold: developing the runtime theory of evolutionary algorithm, establishing the mathematic foundation for relative field application, and providing new idea for runtime complexity of continuous evolutionary algorithm.