一种基于局部lipschitz下界估计支撑面的差分进化算法-周晓根.pdf

《一种基于局部lipschitz下界估计支撑面的差分进化算法-周晓根.pdf》由会员分享，可在线阅读，更多相关《一种基于局部lipschitz下界估计支撑面的差分进化算法-周晓根.pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第39卷第12期 计 算 机 学 报 V0139 No122016年12月 CHINESE JOURNAL OF COMPUTERS Dee2016一种基于局部Lipschitz下界估计支撑面的差分进化算法周晓根 张贵军 郝小虎(浙江工业大学信息工程学院杭州俞310023)立摘要为了减少智能优化算法求解复杂问题时所需的目标函数评价次数，降低算法计算代价，在差分进化算法框架下，结合Lipsehitz估计理论，提出一种基于局部Lipschitz下界估计支撑面的差分进化算法首先，对新个体的N邻近个体构建Lipsehitz下界估计支撑面，进而通过支撑面获取新个体的下界估计值；然后，根据下界估计值设计L

2、ipsehitz估计选择策略来指导种群更新；其次，利用下界估计区域的极值信息排除部分无效区域，逐步缩小搜索区域；最后，根据N邻近个体下降方向和主导支撑面下降方向设计广义下降方向做局部增强数值实验结果表明，所提算法与文中给出的主流算法相比，能够以较少的目标函数评价次数获得高质量的最优解关键词差分进化；智能优化算法；Lipschitz下界估计；全局优化；支撑面中图法分类号TPl8 DOI号1011897SPJ1016201602631Differential Evolution Algorithm Based on LocalSupporting HyperplanesLipschitz Unde

3、restimateZHOU XiaoGan ZHANG GuiJun HA0 XiaoHU YU Li(College of Information Engineering，Zhoiang University of Technology，Hangzhou 310023)Abstract To reduce the number of function evaluations required to find optimal solutions ofcomputationally expensive problems for intelligent optimization algorithm

4、s，a new algorithmwhich introduces the Lipsehitz underestimate theory into basic differential evolution algorithm isproposed，referred to as differential evolution algorithm based on local Lipschitz underestimatesupporting hyperplanes Firstly，the Lipschitz underestimate supporting hyperplanes areconst

5、ructed for the N neighboring individuals of the trial individual to obtain the underestimate valueof the trial individualSecondly，the Lipschitz underestimate selection strategy that designedaccording to the underestimate value of the trial individual is used to guide the population updatingprocessTh

6、irdly，by excluding the invalid regions where the global optimum solution cannot befound according to the extremum information of the underestimate region，the search domainnarrows graduallyFinally，the generalized descent direction based on the descent directions ofthe N neighboring individuals and th

7、e dominant supporting hyperplane is designed for localenhancementExperiments results show that the proposed algorithm can obtain better qualityoptimal solutions with less number of function evaluations compare with the main-stream algorithmsgiven in this paperKeywords differential evolution；intellig

8、ent optimization algorithms；Lipschitz underestimate；global optimization；supporting hyperplanes收稿日期：20150528；在线出版日期：201511一05本课题得到国家自然科学基金(61075062，61573317)、浙江省自然科学基金(LYl3F030008)、浙江省科技厅公益项目(2014C33088)、浙江省重中之重学科开放基金资助项目(20151008，20151015)资助周晓根，男，1987年生，博士研究生，中国计算机学会(CCF)学生会员，主要研究方向为智能信息处理、优化理论及算法设计

9、E-mail：zxgzjuteduell张责军(通信作者)，男，1974年生，博士，教授，博士生导师，中国计算机学会(CCF)会员，主要研究领域为智能信息处理、优化理论及算法设计、生物信息学Email：zgjzjuteducn郝小虎，男，1990年生，硕士研究生，主要研究方向为智能信息处理、生物信息学俞立，男，1961年生，博士，教授，博士生导师，主要研究领域为智能控制、分布式控制和网络控制系统万方数据计 算 机 学 报1 引 言近年来，智能优化算法被广泛用于各种实际应用问题的求解典型的智能优化算法包括遗传算法(Genetic Algorithm，GA)1、差分进化算法(Differentia

10、l Evolution，DE)L2、粒子群算法(Particle SwarmOptimization，PSO)31以及蚁群算法(Ant ColonyOptimization，ACO)F4，这些算法不仅鲁棒性强，而且实用性强，被成功应用于电力、化工、通信以及网络等领域5。然而，绝大多数智能优化算法面临的一个主要问题就是求解时需要大量的目标函数评价次数，从而导致计算代价极高尤其对于一些实际优化问题，由于仿真模型运行时间的限制，在求解过程中，对新产生的候选解进行目标函数评价极其费时例如，对于一个二维粗水动力仿真模型，运行一次可能耗时一分钟左右，对于一个完整的三维水动力模型运行一次可能耗时几分钟，甚至

11、达到几小时8又如蛋白质结构预测问题中，对能量函数评价时有时需要调用第三方能量包，从而导致评价一次需要几秒，甚至达到几分钟因此，对于这些目标函数计算复杂的实际优化问题，如何减少求解过程中所需的目标函数评价次数，降低算法计算代价是一个极其重要的问题，也是计算机科学领域面临的一个亟需解决的问题针对上述问题，国内外学者相继提出了各种解决方法，其中代理模型(Surrogate Model)9和愚一近邻预测(五一Nearest Neighbor Predictor)81为两种最常用的方法代理模型方法利用代理模型来代替计算代价昂贵的目标函数评价基于此方法，Liu等人10提出了一种基于高斯代理模型的进化算法(

12、Gaussian Process Surrogate Model AssistedEvolutionary Algorithm for Medium-scale Computa-tionally Expensive Optimization Problems，GPEM哐)，利用一种降维技术将原优化模型映射到一个低维空间，并通过一种代理意识模型搜索机制使得算法集中搜索希望较大的子区域Zhou等人11提出了一种基于多代理的文化基因算法，在进化过程中，通过精确插值代理模型来提高算法的局部搜索能力，以降低算法的计算代价Lim等人12提出了一种广义代理进化算法，利用各种不同代理模型预测值的加权和来指导种

13、群进化，并通过各代理模型的不确定性预测来自适应调整加权值上述算法最大的优点就是代理模型的计算复杂度远低于原目标问题，因此可以有效地降低计算代价然而，没有一个通用的代理模型可以适用于所有问题，代理模型的选择直接影响着算法的性能9惫一近邻预测方法利用与个体最近的训练样本来预测目标函数值基于此方法，Liu等人81提出了一种基于愚一近邻预测的差分进化算法(DifferentialEvolution using矗一Nearest Neighbour PredictorDEkNN)，在进化前期，将所有个体作为训练样本进行目标函数评价，而在进化后期，利用忌一近邻预测个体的目标函数值，同时从新种群中选取部分较

14、优个体更新训练样本Park等人13提出了一种基于加速k一近邻预测的差分进化算法(DifferentialEvolution using Speedup忌一Nearest NeighbourEstimator，DEEkNN)，该算法与Liu等人8提出的算法最大的区别就是通过训练样本的加权平均值来预测个体的目标函数值，并有选择性的保存样本Pham1“提出了一种基于近邻比较的差分进化算法，在进化过程中，根据新个体的近邻预测值与目标个体的函数值比较来判断是否需要对新个体评价上述算法的最大优点就是结构简单，但是其面临的主要问题就是需要内存来保存大量的训练样本，随着问题维数的增大，所需内存也急剧上升，因此

15、，惫一近邻预测算法并不适用于高维问题1“Lipchistz估计方法151作为一种确定性方法，不需要进行模型选择和样本训练，而是利用一系列支撑函数建立原目标函数的下界估计，并通过不断增加支撑函数的数量使得下界估计不断逼近原目标函数，从而使得支撑函数的全局最优解不断向原目标函数的全局最优解收敛因此，可以通过高效枚举下界估计的局部最优解得到原目标函数的全局最优解Lipchistz估计方法现已被应用于各种问题，如分子结构预测16、拟凸规划17和半无限规划181等然而，为了得到更加精确的最优解，Lipchistz估计方法需要使用大量的支撑函数来逼近原目标函数，从而导致极高的空间复杂度，因此，Lipchi

16、stz估计方法仅适用于维数小于10的问题1 92 0|为了减少智能优化算法的函数评价次数，论文作者在群体算法框架下，结合抽象凸理论2卜2 2|，提出了一种基于抽象凸下界估计的群体全局优化算法(Abstract Convex Underestimate Population-basedAlgorithm，ACUP)c2 3|，该算法首先对整个初始种群构建抽象凸下界支撑面，然后利用不断收紧的下界信息来指导种群更新，最后根据进化信息更新下界支撑面然而，对于一些复杂的高维优化问题，空间复杂度问题需要改进因此，在此基础上，进一步引入局部抽象凸估计策略，提出了一种基于抽象凸万方数据12期 周晓根等：一种基

17、于局部Lipschitz下界估计支撑面的差分进化算法 2633下界估计选择策略的差分进化算法(DifferentialEvolution Algorithm Based on。Abstract ConvexUnderestimate Selection Strategy，DEUS)2引，该算法通过提取新个体的邻近个体建立局部抽象凸下界松弛模型，进而利用下界松弛模型估计目标函数值来指导种群更新，并根据下界极值信息排除部分无效区域，同时借助支撑面的下降方向实现局部增强实验结果表明，ACUP和DEUS算法能够有效地降低算法计算代价，提高算法性能然而，在使用ACUP和DEUS算法求解时，需要将原目标函

18、数转化到单位单纯形约束条件下，并且需要对原目标函数加上常数C转化为正齐次递增函数(IncreasingPositively Homogeneous Function of Degree One，IPH)L2 5|，由于目标函数曲面的粗糙复杂，不同的区域需要的常数C不同，所以C的值有时需要设置得异常的大，导致算法获得的下界估计值与实际目标函数值的误差较大，从而影响算法的性能本文在DE算法框架下，结合Lipschitz估计理论，对种群中的局部个体(新个体的N邻近个体)构建Lipschitz下界估计支撑面，进而通过支撑面获取目标函数的下界估计信息来指导种群进化，从而提出一种基于局部Lipschitz

19、下界估计支撑面的差分进化算法(Differential Evolution Algorithm Based onLocal Lipschitz Underestimate Supporting H yperplanes，DELLU)本文工作与文献24的主要区别在于：(I)采用的Lipschitz估计支撑函数不需要通过模型转换将原目标函数转化为单位单纯形约束条件下的IPH函数，因此能够获得更加精确的下界估计值；(2)设计了一种局部Lipschitz估计选择策略，在种群更新环节，根据新个体的下界估计值分3种情形来判断是否需要对新个体进行函数评价，有效地减少不必要的函数评价次数；(3)根据邻近个体下

20、降方向和主导支撑面下降方向提出了一种局部增强广义下降方向，利用此方向对新个体作局部增强，从而加快算法的收敛速度2预备知识21基本定义考虑如下全局优化问题minf(x)，zD (1)其中，X一(z，X。，z。)为72维优化变量，D为可行域空间，(z)为定义在可行域D上的目标函数，在可行域空间D中可能存在着多个全局最优解和大量的局部最优解定义1 若函数f：zR对于任意的z1，z2D都满足f(x1)-f(x2)IM Il z1一z2|J (2)则称函数厂关于可行域D Lipschitz连续，其中，M称为Lipschitz常数定义2 若存在函数族UH，使得函数，满足，(z)一suph(z)：hcU)，

21、YxD (3)其中，H为定义在可行域D上的函数族，则称函数厂是关于函数族H的抽象凸函数(H-convex)定义3 设H为定义在可行域D上的函数族，函数厂为Hconvex函数，则称aH，(z)一hH：(了)，(y)，(z)一(z)，VyD (4)为函数厂在点z处的H一次微分(H-subgradient)定义4 考虑一个由r一九+1个半空间相交形成的有限凸多边形Pnz：(z，h，1)，其中J=1hl一(一1，0，0，)h2一(O，一1，0，)： ，h。一(O，0，一1)h。+l一(1，1，1)则称dv(z1，z2)=maxmax(一一z；)，(z；一砖) 一1121(5)为点z1和z2之间关于凸多

22、边形P的单纯形距离22 DEUS算法定义5 设种群P=zl，X2，zNP)，工。rIII为新生成个体，则称与x涮之间欧氏距离最近的N个种群个体为z。血。的N邻近个体，其中NP为种群规模，欧氏距离为厂i一d(x。，Xtrial)-(Xiq-Xtrial,j)2 (6)假设式(1)的目标函数，(z)满足定义1，为了建立，(z)的抽象凸下界估计松弛模型，首先需要根据线性变换式(7)将原目标函数，(z)转化到单位单ntl纯形空间S(S=-x7R?1，z；o，z：一1)中i7一-(五一口i)(6i一口i)f=1：+。三卜z：其中，ai和6。分别为zi的下界和上界通过上述线性变换，原目标函数被转换为万方数

23、据2634 计 算 机 学 报 2016正min f(z7)，zScR?1 (8)然后，进一步对式(8)的目标函数加上常数C(C2M，M为Lipshitz常数)将其转化为IPH函数，即喜一f+C经过上述模型转换过程，当新个体x眺。产生后，根据式(6)提取新个体的N邻近个体(z“，季(z“)，忌一1，2，N可以建立式(9)所示的局部抽象凸下界估计松弛模型HN(z7)一max min z知： (9)第k个支撑函数为hk(z，)_i：唑十。z知；一岳(z“)min晕，筹) t=Jn十l I工1 工。上1(10)其中卜(等，等，警)，为点(z“，季(z“)的抽象凸下界估计支撑向量建立了局部抽象凸下界估

24、计松弛模型以后，可以获取目标函数的下界信息来指导种群进化如图1所示，假设A为新个体，B为目标个体，C和D为A的N邻近个体，根据式(11)对个体C和D建立抽象凸下界支撑面，从而可以根据式(9)计算出新个体A的下界估计值歹A，通过歹A与目标个体B的函数值比较来判断是否需要对新个体A进行目标函数评价，有效减少目标函数评价次数；其次，通过比较下界估计区域的极值d面。与当前种群的最优值来判断下界估计区域所对应的优化区域i即C和D之间的区域)是否为无效区域；最后，根据抽象凸下界估计支撑面的下降方向获取下界估计区域的极值解作局部增强，即判断下界估计区域的极值解在目标函数上对应的点E是否优于新个体A图1 DE

25、US算法的局部抽象凸估计选择策略示意图3 DELLU算法在DE算法中，为了判断产生的新个体是否优于目标个体，算法需要对每次迭代产生的新个体进行目标函数评价，然而，对于一些实际优化问题，由于其仿真模型的复杂性，导致其目标函数评价极其费时为了减少DE算法的函数评价次数，降低算法计算代价，同时提高算法性能，本文结合Lipschitz估计理论，通过对新个体的N邻近个体构建Lipschitz下界估计支撑面来指导种群进化31局部Lipsehitz估计选择策略假设式(1)的目标函数，(z)满足定义1，则根据Lipschitz估计理论可知161，函数，是关于以下支撑函数的Hconvex函数h(z)一f(x)一

26、M|z一| (12)其中，M为Lipschitz常数由于任一Lipschitz函数的H-次微分不为空2 0|，则式(12)的支撑函数可进一步转化为h(z)一fix)一j眦P(z，X) (13)其中，d，(z，X)为点X和X之间的单纯形距离通过引入松弛变量z。+。一1一乃，并令j=1，2，咒+l，可将单纯形距离d，(z，)简化为dv(z，)-m川ax(z；一刁)(14)则式(13)的支撑函数可简化为hix)一minif(x)一M(z；一z，)|IminM(；+z) 115)JJ其中归(等叫，等前“，等喃)(16)称为点处的Lipschitz下界估计支撑向量经过变异、交叉操作生成新个体x油一后，提

27、取x的N邻近个体zt。b(z一1，N)建立Lipschitz下界估计支撑向量Z：。(一l，N)，则根据N邻近个体的支撑向量可以计算出x。血。的下界估计值歹。rial，即歹。血lHN(x。i。I)一maxhix。i。1)一max minM(Zk，+X训，) 117)其中，z=fix止)Mz定理1 设z：b(=1，N)为新个体工。血l的N邻近个体，则工油。的下界估计值歹响-满足歹油lfixt血1)，根据式(2)有厂(z：b)-fix。riaI)M|z：b一工。i。l|I=fix；。)一M Il z：。一x油-Ijfix。蒯) (19)由式(12)可知万方数据12期 周晓根等：一种基于局部Lipsc

28、hitz下界估计支撑面的差分进化算法 2635h(x。i。1)一-，zt。b)一M|zkx。i。l|If(x。rjaI)(20)根据式(13)和式(14)，式(20)可简化为h(x。血1)一min(f(xtnb)一M(zkJz。rial，j)f(x。fial)1(21)则由式(17)有歹。血Imaxh(z。蒯)f(x。划) (22)fS_N(2)若f(xnb)歹。血。，则f(x响-)夕油-，(z；)因此，无需对新个体x。湖进行目标函数评价(即计算厂(x涮)，即可判定新个体X吨。比目标个体z；差，而保持z；不变情形(2)如图2(b)所示，A为目标个体277，B为新个体X。血。，E为当前种群中的最

29、优个体z量同样根据B的邻近个体C和D的下界估计支撑面可以计算出x。血。的下界估计值夕。瑚，由于根据歹油-小于目标个体的函数值f(x；)无法判断新个体工曲一是否优于目标个体z；，则进一步将夕响，与当前种群中最优个体z。的目标函数值，(z是。)进行比较，由于歹。l，(z乞。)，则根据定理1可知f(x油-)歹。蒯，(z毛。)因此，也无需对新个体工油-进行目标函数评价，即可判定抛弃x曲一，而保持目标个体z；不变情形(3)除了情形(1)和情形(2)以外的情形，则需要对新个体x涮进行目标函数评价，通过比较f(x油。)和目标个体的函数值，(z；)来判断新个体X。蒯是否能够替换目标个体z；根据上述3种情形，局

30、部Lipschitz估计选择策略可进一步概括为fz?， 若歹。ria-厂(z；)或多。a-，(z：。)z；+1一垮；(4)Vr硭忌1，k。+1)，jiJ：Liiz三三li。证明 设R(z)一kl，N)：HN(z)一h(z)(27)Q(z)一iI：h(z)=M(z：+Xi) (28)则由文献-26可知，对于V“U(zi。，D)一lR“+1：3aoo：z。i。+auED，V口(o，口o)，存在惫R(x。i。)使得()7(z。i。，“)=min MMi0 (29)iq(z设mj，对于Vim存在Aio，使得Ai一1，考虑向量Hf1，计一，显然口U(z袖，D)因此存在志R(z曲)，使得()7(z mi。

31、，H)0如果Q(z商。)m)，则()7(z“。，H)一 min Mu肌，(zmin)一M(z?h咖J)一HK(zIni。)，i歹 (37)由式(37)有M(1：!j+zmin,i)M(z?+zmin，)z?+zIBi。；z?+zmi。， (38)又因为z曲i一面drainz：t，zmi。，一眚一z；，因此，当i歹时z?+智一z：tz?+眚一z?jz?一跨o净z?蘑 (39(4)由式(17)有HN(zmIn)一maxminM(：+zrain,i)iI (30) 因此，2翟Nx曙i InM(露+鲁IV一z：)2“(40) 、 ，11h什什；什ZZZ磋磋；分瑶茸；夺一翱Z若若万方数据12期 周晓根等

32、：一种基于局部Lipsehitz下界估计支撑面的差分进化算法 2637maxminM(：一跨)一。净maxmin(：一砖)一oN i1 N1(41)设Vr硭志。，忌。，忌。十。)，贝0mmLfr一ih)0 (42)因此，Vr足l”，矗。+。)，jiI：跨z；r 证毕在选择过程中，当新个体的下界估计值Y。由。大于目标个体z；的目标函数值，(z；)，或大于当前种群中最优个体的目标函数值f(xgk。)时，即歹。血。厂(z；)或歹。血-，(z：。)时，继续根据定理2的性质(1)计算出下界估计区域的极小值d血如图3所示，由于d。i。f(x。)，即可判断此下界估计区域对应的搜索子区域(即A和B之间的区域)

33、中不可能包含全局最优解，从而可将此区域看作无效区域，并建立数组豫记录其对应的支撑矩阵与DEUS算法相比，由于DELLU算法能够求得更加精确的下界估计值，而无效区域的排除与d。i。的精确度有很大关系，因此DELLU算法能够找出更多的无效区域一mm zk。 。图3无效区域排除过程定理3 设x。血-为新个体，L“为某一无效区域对应的支撑矩阵，若X。蒯不在此无效区域中，则了i，歹工，i：fij：z?一Xtml,jz? (44)将式(16)代人上式有掣一Xtrial,，等一考，矿一j而一一叫掣等_，jrz圳夕百一zf L4b由式(45)有M(x：j-X。蒯J)f(xki)一f(xt血1)M(z?-Ztr

34、ial)(46)证毕当新个体x。血。生成后，若无效区域存在，即豫不为空时，根据定理3即可判断出新个体是否被包含在无效区域中，如果X油-在无效区域中，则保持目标个体z；不变，并直接进入下一次迭代由此可以看出，通过无效区域排除策略可以有效排除部分无效区域(即在此区域中不可能包含全局最优解)，逐步缩小搜索区域，使得算法集中搜索希望较大的子区域，不仅能够提高算法的搜索效率，降低算法的计算代价，而且在一定程度上能够防止算法陷入局部最优，提高算法的可靠性33广义下降方向局部增强策略传统DE算法全局搜索能力较强，但是局部搜索能力较弱，尤其在进化后期收敛速度较慢，因此后期需要进行大量的目标函数评价针对此问题，

35、DEUS算法通过直接获取抽象凸估计区域的极小解在目标函数曲面上对应的点与目标个体进行比较，以获得更优个体而在本文中则结合N邻近个体的下降方向和主导支撑面的下降方向提出一种局部增强广义下降方向，利用此方向引导个体作局部增强，提高算法的局部搜索能力，从而加快算法的收敛速度，进一步减少函数评价次数定义7 若新个体x喃。的下界估计值歹ti&IH。N(工trial)一max min M(tnb，+z。蒯f)f玉N J一1，n+1一-ylkhnb，i+z。i。l，)，k1，N) (47)即下界估计值歹涮可以根据邻近个体z：“的支撑面z：。求出，则称支撑面z：。为主导支撑面，且称支撑面z：-的下降方向dd。

36、一(dd。1，dd。+1)=(zlni。1一z：b1，X。i。十lz：b，。+1)(48)为主导支撑面下降方向，其中X。i。为下界估计区域的极小解定义8 设z：b(一1，N)为新个体X而I的N邻近个体，则称方向d。b一(d。b1，d。b。十1)一(XBnb，l-Xwnb，l，zBnb。十1一XWnb，。十1)(49)为N邻近个体下降方向，其中，z鼬和Xw。分别为N邻近个体中的最优个体和最差个体定义9 设da衄和d曲分别为新个体工诚。的主导支撑面下降方向和N邻近个体下降方向，则称方向ddd。+d。b (50)为工。蒯的广义下降方向如图4所示，设B为新个体工。捌，个体C和D为B的邻近个体，图中给出

37、了B的主导支撑面下降方向、N邻近个体下降方向和广义下降方向，则当新个体x。血优于目标个体z；时，为了进一步加快收万方数据2638 计 算 机 学 报敛速度，根据x的广义下降方向作局部增强，即z。一x岫J+F孑 (51)其中参数F与变异策略中的步长因子相同，如果X。优于x油t，则。替换目标个体z；图4广义下降方向34算法设计DELLU算法的主要思想是：在基本DE算法框架下，提取新个体的N邻近个体构建基于Lipschitz估计理论的下界支撑面，通过支撑面获取新个体的下界估计信息指导种群更新，并根据下界估计区域的极值信息排除部分无效区域，同时根据基于N邻近个体下降方向和主导支撑面下降方向的广义下降方

38、向作局部增强，从而有效提高算法的性能，减少进化过程中所需的目标函数评价次数，降低算法的计算代价以极小化问题为例，算法整体流程如下：1初始化设置种群规模NP，交叉概率CR，增益常数F，N邻近个体数目N，并随机生成初始种群P一(z-，zz，X。，初始化无效区域侬为空，进化代数go2对每个目标个体z；P执行变异、交叉过程生成新个体工备小3对每个目标个体z；及其对应的新个体z进行如下操作：31设置i一1；32如果豫不为空，则根据式(43)判断z是否在无效区域豫中，如果不在，则转至步骤33，否则z：”=z：，并转至步骤317；33根据式(6)找出z的N邻近个体z。tb；34根据式(16)计算z：h的下界

39、估计支撑向量f：b，并建立支撑矩阵L；35根据式(17)计算z的下界估计值歹。蒯，并根据式(47)记录主导支撑面；36如果歹响，(z：)，则zf“一z：，并转至步骤39，否则转至步骤37；37计算当前种群的最优值f(x2。)；38如果y-tfial，忱gh)，则z；“一z：，并转至步骤39，否则转至步骤311；39根据式定理2的性质(2)计算下界估计区域L的极小值d。；310如果d一，(zk)，则将L加入限，并转至步骤317；311如果，(z)，(z；)，则转至步骤312，否则z；“一z；，并转至步骤317；312根据式(48)计算主导支撑面下降方向孑如m；313根据式(49)计算N邻近个体下

40、降方向j。；314根据式(50)fl-算zi涮的广义下降方向j；315根据式(51)计算局部增强个体“316如果f(x。)，(z：ria-)，则z；“一z。，否则z；+1一zo；317 ii+1，并删除所有支撑向量f：b；318如果iXNP，转至步骤324gg+15如果不满足终止条件，则转至步骤26输出结果，退出注：步骤2中的变异交叉过程参见文献I-2；步骤317在每次迭代结束后删除所有支撑向量，只保留无效区域的支撑向量35复杂度分析根据34节的算法步骤分析DELLU算法相对于传统DE算法所增加的时间复杂度步骤32中判断新个体是否在无效区域中时，只需判断新个体是否满足式(43)，因为本文通过树

41、的形式保存无效区域，因此时间复杂度为O(咒+1)logT)，其中T为无效区域的数目；步骤33中找出新个体的N邻近个体时需要计算各个体与新个体的距离，时间复杂度为O(nNP)，根据距离找出N个邻近个体的时间复杂度为O(NNP)；步骤34中计算支撑向量的时间复杂度为O(N(n+1)；步骤35中计算下界估计值的时间复杂度为O(N(n+1)；步骤36的判断下界估计值是否大于目标个体的函数值的时间复杂度为o(1)；步骤37中计算当前种群的最优值的时间复杂度为O(NP)；步骤38、步骤39和步骤310的时间复杂度均为O(1)；步骤311中判断新个体是否优于目标个体的时间复杂度为O(2)；步骤312中计算主

42、导支撑面下降方向的时间复杂度为O(n+1)；步骤313中计算N邻近个体下降方向时需要找出N邻近个体中的最优个体和最差个体，则时间复杂度为O(2N+1)；步骤314中计算广义下降方向的时间复杂度为O(行+1)；步骤315中计算局部增强个体的时间复杂度也为O(靠+1)；步骤316中判断局部增强个体是否优于万方数据12期 周晓根等：一种基于局部Lipschitz下界估计支撑面的差分进化算法 2639新个体时，需要计算局部增强个体的目标函数值，若增强个体优于新个体，则增强个体替换新个体，则时间复杂度为O(n+1)；步骤317中删除所有支撑向量的时间复杂度为0(1)上述步骤中，某些步骤在满足条件的情况下

43、才会执行，当上述步骤都执行时，最大时间复杂度为0(2N以+行NP+NNP+NP+7logT+logT+4n+4N+12)，忽略常量、低次幂和最高次幂的系数，则最终时间复杂度为O(maxNn，以NP，NNP)如果只对新个体附近的两个个体建立支撑向量(即N一2)，则当问题维数大于2时，算法的时间复杂度为O(72NP)，由此可以看出，DELLU算法没有显著增加DE算法的时间复杂度，且DELLU算法主要针对目标函数计算复杂的优化问题，因此，建立下界估计所增加的计算代价小于实际目标函数评价所需的计算代价4数值实验41测试函数及算法参数设置应用20个典型的标准测试函数来验证所提算法的性能，表1给出了各测试

44、函数基本参数和数学表达式其他特性见文献1-27一z83表1 20个标准测试函数函数名 数学表达式 维数 搜索范围 最优值SphereTabletSehwefel 222Sehwefel 12StepZakharovRosenbroekGfiewankSchaffer 2AckleySchwefel 226，1(z)一z；，3(z)一 置I+I毛，7(z)一(100(x+lz)2+(毛一1)2)i=1，s cz，=+志耋z；一鱼cos(砉)，9(z)一(z：+z2十。)o25(sin2(50(x；+z2十1)+1)。(z)=一20exp(一02f。，(z)一一墨sin(胡i-)i鲁lHimmel

45、blau f12(z)=“30 (一100。lOO) o30 (一100，100)030 (一10，10)030 (一100，lOO)030 (一lOO，100)030 (一5，lO)030 (一Z。2) O30 (一600，600) O30 (一100。lOO) o30 (一30。30)030 (一500，500) 一12 5694830 (一i00，too) 一783323一1Levy andM。ntalv。1 f13(x)=n(10sinz(兀y1)n+f=l(Yl-1)2(1+10sin2(兀y+1)+ 30 (一10，10) 0(儿一1)2，Y。一1+O25(x。+1)Levy an

46、d Montalvo 2RastriginCosine MixtureKowalik(z。一1)2(1+sin2(2nx。)fls(z)一10n+(z；一10cos(2nx。)i=1 ，。(z)一o1cos(5cx。)一z；i=1 i=1(z1(6；+6。上2)(6；十6iz 3+z)2Six-humpCamebback fls(z)24x：一21x：+x)3-t-xlz24x；+4x；30 O30 (一5，5) 0O4(一5，5)00003075(一5，5) 一1031 6285Branin ，19(z)=(z251x；4n-f-Sxll7-6)2+10(118n)cosxl+10 2 (一

47、5，10)039789Goldstein-Priee 厶b净1釜：1：+鬟19二142l+3蠢；4也：却2芝登，z(-2,2)302x 3x 18 32x 12x 48x 36x 27 s+( 1 2)2( 一 1+ ：+ ，一 ，z，+ zi)” 。工。+z舻一z(疋、，弓。H，L。一)b列O+b。一曲(、，z豇O。，L+、，工瓢O。，L+2l工。一)工(P十02+、I，)z耳2“oC。一n，pXe一、l，z5+z6一z。+)+z虻3(一S+l(2)lz(H+)犯3(一S(1O一)Z(口(。=)工(厂万方数据计 算 机 学 报20个标准测试函数中包含了7个高维单模函数()、8个高维多模函数(f。)和5个低维多模函数(，。)，其中，高维多模函数局部最优解的数量随着维数的增大呈现指数增加上述所有测试函数均满足Lipschitz条件DELLU算法参数设置：用于建立Lipschitz下界估计支撑面的新个体的邻近个体数目N一2，种群规模NP一50其次，为了公