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

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.

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

连续型演化算法是工业优化与设计中的重要方法，然而鲜有该方法的计算时间复杂性研究结论。本项目在演化算法的理论基础与优化应用等方面开展了创新性研究工作。在理论基础方面，项目组建立了演化算法的平均增益模型并提出了算法性能对比方法，解决了连续型演化算法计算时间复杂性分析问题；构建了演化算法计算时间复杂性估算的实验方法与异常检测方法，为演化算法的应用提供了坚实可测的科学依据。在优化应用方面，项目组基于该理论基础，指导了随机启发式演化算法的设计，解决了超大规模多目标优化与耦合优化等核心问题，实现了在计算机视觉、软件工程与物流应用效果上的一系列重大突破，取得了显著的产业化应用成效。本项目研究完善了演化算法的计算时间复杂性研究，推动了算法基础理论的发展，架起了算法理论研究与设计的桥梁。.项目组已超额完成研究目标。通过本项目的研究，项目组成员发表国际学术期刊和国际会议论文40篇，其中SCI国际期刊论文22篇，IEEE Trans长文14篇，中文顶级学术期刊9篇；项目负责人以第一完成人授权国家发明专利4项。在本项目支持下，项目负责人成为国家级青年人才项目入选者（2022年）。通过本项目，培养博士后1人、博士4人和硕士17人，出版著作1部，并发布了连续型演化算法计算时间复杂性估算系统。截至2023年1月9日，该系统已有用户100名、算法分析案例1176个，为学术界与工业界提供了实用的计算时间复杂度分析工具。