近日，智能算法研究中心发布了EATimeComplexity系统（简称EATC系统，网址：net），用于辅助研究人员与工程师高效方便地剖析实际应用中进化算法的时间复杂度，搭建理论基础和实际应用的沟通桥梁。自此，进化算法时间复杂度的剖析对象不再局限于简化版的算法特例，这种剖析工作也不再是曲高和寡的复杂物理推论。该系统将大大减低实际应用中进化算法时间复杂度剖析工作的难度，有望成为研究人员与工程师从事算法研究的必备利器。
#1:a:8:c:0:7:a:b:5:5:6:f:b:3:8:4:3:5:a:d:4:8:7:1:9:5:2:2:3:8:8:2#
时间复杂度剖析是进化估算领域公认的非常重要的基础问题。但是，目前的理论结果大多针对简化后的算法原型，实际应用的前沿进化算法的剖析结果较少。针对以上问题，智能算法研究中心提出了一种新型的基于平均增益模型的时间复杂度计算方式[1]。在平均增益模型的基础上，此方式基于格里工科定律模拟增益的分布，以描画进化算法在优化过程中取得的进展。计算方式借助数据拟合技术获得拟合函数解析式，并将之用于估算时间的计算。为了增加应用门槛，为部份非软件专业人士解决编程困难，智能算法研究中心以基于平均增益模型的时间复杂度计算方式为蓝本，进一步开发了EATC系统。
研究中心将使用EATC系统得到的结果与理论推论的结果进行了比较。一方面，在文献[3]的案例剖析中，使用(1,λ)进化策略求解球状问题的估算时间下界时可以得到如下推论：
#9:6:2:2:3:e:9:e:b:f:e:7:7:5:f:6:0:0:e:c:d:f:6:b:5:4:c:0:4:a:6:7#
而使用EATC系统针对（1，λ）进化策略求解球状问题的首达时间下界的计算结果如右图所示：
#a:c:2:9:9:f:c:a:8:8:c:4:6:6:9:4:6:7:4:1:1:b:a:d:6:d:7:a:0:f:0:a#
图1(1,λ)进化策略求解球状函数
其中，图1(a)展示了在问题维度的不同取值下搜集到的平均增益与问题维度及适应值之间的关系。在图1(a)中，每位白色空心点代表一个样本点。图9(b)展示了平增益数据图的拟合图象。
#f:2:a:b:f:9:6:e:4:c:8:8:2:5:8:4:9:8:2:4:7:3:8:f:7:8:d:c:c:8:9:0#
另一方面，以Sphere函数的时间复杂度求解为例，其系统计算结果和实际估算时间的比较如右图所示：
#d:8:9:f:2:1:b:4:b:e:f:d:f:2:f:e:7:8:b:2:2:9:d:b:5:a:0:c:f:8:d:f#
图2系统计算时间复杂度下界与进化策略算法实际结果对比图
其中，金色折线表示系统计算的时间复杂度下界，白色折线表示进化策略算法的实际平均估算时间。通过上述对比可以看出，EATC系统的计算结果与理论推论结果基本一致，证明系统的计算是可靠的。
#7:4:d:e:e:c:a:c:6:f:9:0:6:2:9:9:1:3:2:6:5:6:e:7:6:c:8:a:e:9:b:f#
EATC系统是一个简约且强悍的时间复杂度计算软件，它能为用户提供以下主要功能：
1.在线使用功能。研究人员与工程师无需提供源代码或可执行文件，只须要填写算法名称以及须要优化的问题，之后上传平均增益的取样数据文件，系统将会手动完成曲面拟合及时间复杂度推论，输出算法的时间复杂度计算结果。
2．离线使用功能。不便上传数据的研究人员可以选择下载相关的数据取样代码（下载网址：），直接在本地完成对连续型进化算法时间复杂度的计算。
#f:1:4:7:b:2:a:e:8:d:c:8:6:a:4:c:d:a:7:b:5:b:5:9:3:1:8:5:1:5:1:c#
图3离线使用功能示意图
3．委托计算功能。研究人员也可以在线填写委托计算申请表（网址：
），根据指定要求上传代码和程序，委托智能算法研究中心对时间复杂度进行计算。研究中心将承诺帮助计算并做好代码保密工作，完成计算后以电邮方式返回计算结果。整个过程将不缴纳任何费用。（联系邮箱已更新，以网页显示为准）
#4:4:8:9:f:0:3:0:c:d:e:4:0:1:0:6:0:d:0:5:3:0:a:c:d:b:9:7:8:a:d:0#
图4委托计算功能示意图
EATC系统不但功能强悍，但是十分适于使用。EATC系统的具体使用步骤如下：
#c:d:7:c:0:4:d:8:3:0:3:e:e:f:b:4:0:8:2:5:c:4:5:8:5:f:3:e:7:4:b:a#
图5EATC系统使用流程图
第1步：点击创建按键，创建任务；
第2步：选择算法所须要的取样数据文件（注意：系统接收的上传文件需为Excel文件（.xlsx），其中数据共三列：对应问题经度、适应值差、平均增益）；
第3步：填写算法名称以及须要优化的问题；
#6:8:5:e:b:9:5:b:2:c:e:0:9:3:0:f:d:a:d:8:7:1:3:f:3:f:6:c:0:f:9:2#
图6EATC系统具体使用步骤图
第4步：点击运行按键，运行算法；
第5步：查看算法时间复杂度的计算结果；
第6步：点击导入按键，下载时间复杂度下界公式、平均增益数据点图及其曲面拟合图象。
#f:4:7:6:9:0:7:d:6:b:d:c:7:f:3:1:8:7:f:6:3:f:e:b:a:8:4:c:a:8:b:2#
图7EATC系统运行结果展示图
#9:3:d:a:d:7:a:8:0:8:3:2:b:d:7:8:1:c:1:e:a:b:0:7:3:d:b:c:f:a:2:0#
目前，EATC系统早已有了不少成功使用的案例，如表1所示。
#1:1:b:6:5:8:6:f:9:6:8:9:e:4:1:2:d:6:4:1:d:9:a:a:6:8:b:f:b:f:1:2#
表1EATC系统使用案例表
以下3个反例进一步展示了EATC系统在具体应用中获得的计算结果：
例1：使用自适应协残差矩阵进化策略(CovarianceMatrixAdaptationEvolutionStrategy,CMA-ES)[5]求解Schwefel函数
#c:d:b:0:5:9:b:2:c:6:2:5:5:9:b:f:e:7:0:3:1:2:4:3:1:c:d:b:4:f:6:1#
图8CMA-ES求解Schwefel函数
例2：使用差分进化算法(DifferentialEvolution,DE)[6]求解ShiftedSphere函数
#3:1:b:7:9:3:f:0:4:b:4:8:a:1:c:0:c:5:9:d:b:c:e:0:8:f:0:2:a:2:1:6#
图9DE求解ShiftedSphere函数
例3：使用脑子风暴优化算法(BrainStormOptimizationAlgorithm,BSO)[7]求解Sphere函数
#9:5:a:e:9:b:0:2:d:6:a:c:1:1:8:9:7:1:c:3:e:f:8:0:4:b:5:d:f:8:3:5#
图10BSO求解Sphere函数
值得一提的是，我们的计算系统所计算的大部份算法和函数的时间复杂度都是目前文献没有提到的，其时间复杂度剖析属于研究领域的空白。据悉，好多函数都是在理论研究中未能剖析的，甚至可以说其剖析难度是地狱级的。通常文献研究Sphere函数的早已算是王者了，而我们系统几乎哪些函数都可以剖析，呵呵……
#4:e:8:7:f:c:7:2:e:f:f:4:b:c:d:2:a:7:b:f:f:a:4:7:9:3:0:d:3:6:d:e#
EATC系统为进化算法的时间复杂度剖析提供了一种新的出路，适用于实际应用中的各种进化算法。最后，诚恳欢迎诸位研究人员与工程师使用我们的系统，期盼您们的反馈与建议！
#6:6:5:a:d:4:b:1:6:9:d:a:1:a:6:7:5:b:1:5:0:9:b:6:2:4:f:4:3:c:2:1#
参考文献
[1]HanHuang,JunpengSu,YushanZhang,ZhifengHao.AnExperimentalMethodtoEstimateRunningTimeofEvolutionaryAlgorithmsforContinuousOptimization.IEEETransactionsonEvolutionaryComputation,2020,24(2):275-289.
[2]黄翰,徐威迪,张宇山,林智勇,郝志峰.基于平均增益模型的连续型(1+1)进化算法估算时间复杂性剖析.中国科学:信息科学,2014,44(6):811-824.
[3]张宇山,黄翰,郝志峰,杨晓伟.连续型演变算法首达时间剖析的平均增益模型.计算机学报,2019,042(003):624-635.
[4]冯夫健,黄翰,张宇山,郝志峰.基于等同关系模型的演进算法期望首达时间对比剖析.计算机学报,2019,042(010):2297-2308.
[5]HansenandOstermeier.CompletelyDerandomizedSelf-AdaptationinEvolutionStrategies.EvolutionaryComputation,2001,9(2):159-195.
[6]StornR,PriceK.DifferentialEvolution—ASimpleandEfficientHeuristicforGlobalOptimizationoverContinuousSpaces.JournalofGlobalOptinization,1997,11(4):341-359.
[7]YuhuiShi.AnOptimizationAlgorithmBasedonBrain-stormingProcess.InternationalJournalofSwarmIntelligenceResearch(IJSIR),2011,2(4):35-62.
总编：黄翰
