近期，智能算法研究中心发布了进化算法时间复杂度估算系统EATimeComplexity系统（简称EATC系统，网址：www.eatimecomplexity. net），用于辅助研究人员与工程师高效便捷地分析实际应用中进化算法的时间复杂度，实现搭建理论基础和实际应用的沟通桥梁。从此，进化算法时间复杂度的分析对象不再局限于对简化版的算法特例，此类分析工作也不再是曲高和寡的复杂数学推导。该系统将大大降低实际应用中进化算法时间复杂度分析工作的难度，有望成为研究人员与工程师从事算法研究的必备神器。

时间复杂度分析是进化计算领域公认的极其重要的基础问题。然而，目前的理论结果大多针对简化后的算法原型，实际应用的前沿进化算法的分析结果较少。针对以上问题，智能算法研究中心提出了一种新型的基于平均增益模型的时间复杂度估算方法[1]。在平均增益模型的基础上，此方法基于格里文科定理模拟增益的分布，以刻画进化算法在优化过程中取得的进展。估算方法利用数据拟合技术获得拟合函数解析式，并将之用于计算时间的估算。为了降低应用门槛，解决为部分非软件专业人士的解决编程困难，智能算法研究中心以基于平均增益模型的时间复杂度估算方法为蓝本，进一步开发了EATC系统进化算法时间复杂度估算系统。

研究中心将使用EATC系统得到的结果与理论推导的结果进行了比较。一方面，在文献[3]的案例分析中，使用(1, λ)进化策略求解球形问题的计算时间上界时可以得到如下结论：

定理 假设时刻的解为，令，且，当,时，对于首达时间有：

其中，表示子代种群的规模，表示终止阈值，表示初始解的适应值差，表示进化策略在迭代过程中时的步长。

而使用EATC系统针对（1，λ）进化策略求解球形问题的首达时间上界的估算结果如下图所示：

图1 进化策略求解球形函数

其中，图1(a) 展示了在问题维度的不同取值下收集到的平均增益与问题维度及适应值之间的关系。在图1(a)中，每个红色空心点代表一个样本点。图9(b)展示了平增益数据图的拟合图像。

比较上述理论推导结果与EATC系统估算结果可得，进化策略求解球形函数的计算时间与估算结果的形式相同，证明了估算方法的有效性。

另一方面，以Sphere函数的时间复杂度求解为例，其系统估算结果和实际计算时间的比较如下图所示：

图2 系统估算时间复杂度上界与进化策略算法实际结果对比图

其中，蓝色折线表示系统估算的时间复杂度上界，红色折线表示进化策略算法的实际平均计算时间。通过上述对比可以看出，EATC系统的估算结果与理论推导结果基本一致，证明系统的估算是可靠的。

EATC系统进化算法时间复杂度估算系统是一个简洁且强大的时间复杂度估算软件，它能为用户提供以下主要功能：

1. 在线使用功能。研究人员与工程师无需提供源代码或可执行文件，只需要填写算法名称以及需要优化的问题，然后上传平均增益的采样数据文件，系统将会自动完成曲面拟合及时间复杂度推导，输出算法的时间复杂度估算结果。

2．离线使用功能。不便上传数据的研究人员可以选择下载相关的数据采样代码（下载网址：http://eatimecomplexity.autosem.net/more/analysis），直接在本地完成对连续型进化算法时间复杂度的估算。

图1 3 离线使用功能示意图

3．委托估算功能。研究人员也可以在线填写委托估算申请表（网址：

http://eatimecomplexity.autosem.net/more/analysis），按照指定要求上传代码和程序，委托智能算法研究中心对时间复杂度进行估算。研究中心将承诺帮助估算并保密代码做好代码保密工作，并完成估算后以邮件形式返回估算结果。整个过程将不收取任何费用。（联系邮箱已更新，以网页显示为准）

图2 4 委托估算功能示意图

EATC系统进化算法时间复杂度估算系统不但功能强大，而且非常易于使用。EATC系统该估算系统的具体使用步骤如下：

图3 5 EATC系统进化算法时间复杂度估算系统使用流程图

第1步：点击创建按钮，创建任务；

第2步：选择算法所需要的采样数据文件（注意：系统接收的上传文件需为Excel文件（.xlsx），其中数据共三列：对应问题纬度、适应值差、平均增益）；

第3步：填写算法名称以及需要优化的问题；

图64 EATC系统进化算法时间复杂度估算系统具体使用步骤图

第4步：点击运行按钮，运行算法；

第5步：查看算法时间复杂度的估算结果；

第6步：点击导出按钮，下载时间复杂度上界公式、平均增益数据点图及其曲面拟合图像。

图75 EATC系统进化算法时间复杂度估算系统运行结果展示图

目前，EATC系统该进化算法时间复杂度估算系统已经有了不少成功使用的案例，如表1所示。

表1  EATC系统进化算法时间复杂度估算系统使用案例表

以下两3个例子进一步展示了EATC系统进化算法时间复杂度估算系统在具体应用中获得的估算结果：

例1：使用自适应协方差矩阵进化策略(Covariance Matrix Adaptation Evolution Strategy, CMA-ES)[5]CMA-ES求解Schwefel函数

图86 CMA-ES求解Schwefel函数

例2：使用差分进化算法(Differential Evolution, DE)[6]求解Shifted Sphere函数

图9 DE求解Shifted Sphere函数

例32：使用头脑风暴优化算法(Brain Storm Optimization Algorithm, BSO)[7]BSO求解Sphere函数

图107 BSO求解Sphere函数

值得一提的是，我们的估算系统所估算的大部分算法和函数的时间复杂度都是目前文献没有提及的，其时间复杂度分析属于研究领域的空白。此外，很多函数都是在理论研究中难以分析的，甚至可以说其分析难度是地狱级的。一般文献研究Sphere函数的已经算是王者了，而我们系统几乎什么函数都可以分析，在时间复杂度分析领域可以算得上是统领一方的“帝皇”了。呵呵……

此外，我们还将使用进化算法时间复杂度估算系统得到的结果与理论推导的结果进行了比较。一方面，文献[3]中的定理三被用于验证估算得到的(1,λ)进化策略的计算时间。根据上下文信息，可将文献[3]的定理三转述如文献[1]的定理二。

定理二  假设时刻的解为，令，且，当,时，对于首达时间有：

其中，表示子代种群的规模，表示终止阈值，表示初始解的适应值差，表示进化策略在迭代过程中时的步长。

图8 进化策略求解球形函数的平均增益

图8(a) 展示了在问题维度的不同取值下收集到的平均增益与问题维度及适应值之间的关系。在图8(a)中，每个红色空心点代表一个样本点。拟合图像如图8(b)所示。进一步推导可得，进化策略的首达时间上界估算结果为：

定理二表明，进化策略求解球形函数的计算时间与估算结果的形式相同，证明了估算方法的有效性。

另一方面，以Sphere函数的时间复杂度求解为例，其系统估算结果和实际计算时间的比较如下图所示：

图9 系统估算时间复杂度上界与进化策略算法实际结果对比图

其中，蓝色折线表示系统估算的时间复杂度上界，红色折线表示进化策略算法的实际平均计算时间。通过上述对比可以看出，我们的进化算法时间复杂度估算系统的估算结果与理论推导结果基本一致，证明系统的估算是可靠的。

EATC系统EATimeComplexity系统为进化算法的时间复杂度分析提供了一种新的出路，适用于实际应用中的各类进化算法。最后，衷心欢迎各位研究人员与工程师使用我们的系统，期待您们的反馈与建议！

参考文献

[1]Han Huang, Junpeng Su*, Yushan Zhang, Zhifeng Hao. An Experimental Method to Estimate Running Time of Evolutionary Algorithms for Continuous Optimization. IEEE Transactions on Evolutionary Computation.[1] Han Huang, Junpeng Su, Yushan Zhang, Zhifeng Hao. An Experimental Method to Estimate Running Time of Evolutionary Algorithms for Continuous Optimization. IEEE Transactions on Evolutionary Computation, 2020, 24(2): 275-289.

[2]黄翰, 徐威迪, 张宇山, ,林智勇, 郝志峰等. 基于平均增益模型的连续型(1+1)进化算法计算时间复杂性分析[J]. 中国科学: 信息科学, 2014, 44(6): 811-824.

[3]张宇山, 黄翰, 郝志峰, 杨晓伟等. 连续型演化算法首达时间分析的平均增益模型[J]. 计算机学报, 2019, 042(003): 624-635.

[4]冯夫健, 黄翰, 张宇山, 郝志峰冯夫健, 黄翰, 张宇山, 等. 基于等同关系模型的演化算法期望首达时间对比分析[J]. 计算机学报, 2019, 042(010): 2297-2308.

[5] Hansen and Ostermeier. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation, 2001, 9(2): 159-195.

[6] Storn R, Price K. Differential Evolution—A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optinization, 1997, 11(4): 341-359.

[7] Yuhui Shi. An Optimization Algorithm Based on Brain-storming Process. International Journal of Swarm Intelligence Research (IJSIR), 2011, 2(4): 35-62.

总编：黄翰

责任编辑：袁中锦

文字：邓淇

图片：邓淇、袁中锦

校稿：何莉怡

时间：2021年9月28日