带隐藏约束昂贵黑箱问题的自适应代理优化方法.pdf

2024年3 月Mar.,2024DOI:10.15960/ki.issn.1007-6093.2024.01.007这筹学学报（中英文Operations Research Transactions第2 8 卷第1 期Vol.28No.1带隐藏约束昂贵黑箱问题的自适应代理优化方法白富生1兰秘2摘要针对带隐藏约束的昂贵黑箱全局优化问题，提出采用自适应转换搜索策略的代理优化方法。在转换搜索子步中采用与已估值点个数相关的标准差在当前最优点附近通过随机扰动生成候选点，以更好地平衡局部搜索和全局搜索。为更好地近似真实黑箱目标函数，采用了自适应组合目标代理模型。在50 个测试问题上进行了数值实验，计算结果说明了所提算法的有效性。关键词昂贵黑箱问题，全局优化，隐藏约束，代理优化中图分类号0 2 2 1.22010数学分类号 90 C26,90C56,90C59An adaptive surrogate optimization method forexpensive black-box problems with hidden constraints*Abstract A surrogate optimization method with adaptive transition search strate-gy is proposed for expensive black-box problems with hidden constraints.In the sub-stepsof the transition search,a variance related to the number of evaluated points is used forthe generation of trial points by random perturbation to better balance the local andglobal searches.In order to better approximate the real black box objective function,an adaptively combined objective surrogate model is adopted.The effectiveness of theproposed algorithm is demonstrated by the results of the numerical experiments carriedout on 50 test problems.Keywords expensive black-box problems,global optimization,hidden constraints,surrogate optimizationChinese Library Classification O221.22010 Mathematics Subject Classification 90C26,90C56,90C59黑箱函数指输入的自变量与输出的函数值之间没有明确表达式的函数。若从黑箱函数的一个输入得到输出需花费的代价很高，例如需要做一个耗时的化学实验，实施一次工程作业，或运行长时间的计算仿真系统，则称之为昂贵的黑箱函数。考虑如下形式的昂贵收稿日期：2 0 2 1-1 0-1 1*基金项目：国家自然科学基金（Nos.11991024，1 1 8 7 1 1 2 8)，重庆市技术创新与应用发展专项重点项目（No.cstc2021jscx-jbgsX0001)，重庆市教委科学技术研究计划重点项目（No.KJZD-K202114801)1.重庆师范大学重庆国家应用数学中心，重庆40 1 3 3 1；NationalCenter forAppliedMathematics inChongqing,Chongqing Normal University,Chongqing 401331,China2.重庆师范大学数学科学学院，重庆 40 1 3 3 1；School of Mathematical Sciences，Ch o n g q i n g No r ma lUniversity,Chongqing 401331,China+通信作者E-mail:BAI Fushengl,fLAN Mi290黑箱函数优化问题：这里li和u满足li0exp(-r),0dePel 入Fe=。b2入2入二1,0,n91f(aet)f(ce2)C=，Fe=bda如果aEPe,如果aEQu,(6)92以拟合数据对【(a1,g(c1),，(a n,g 9(a n),其参数同样可通过求解相应的线性方程组得到。取0 1,则集合(alsg(a)8)包含了估值成功点集合e，并且在一定程度上可以作为集合B的近似。因此通过求解问题min se(a)s.t.liaui,i=l,.,d,sg(a)0,可以得到原问题（1）的近似解。白富生，兰秘28卷(7)2SHEBO 算法在SHEBO算法中，首先通过拉丁超立方采样得到初始采样点，并构造目标函数代理模型 se(）和约束函数代理模型 sg()，然后进入由局部搜索（local search)、转换搜索(transition search)、全局搜索（global search）组成的优化搜索阶段得到新采样点anew。在此阶段只依次执行一种搜索。取代，n为当前采样点的个数，no 是初始采样点的个数，nmax是允许的最大真实函数估值次数。显然，tn关于n递增。在转换搜索步中，按照预先给定的权重模式向量W，依次轮流选取分量Wi，因此要连续进行WI个搜索子步，这里II表示W所含分量个数。在每个子步中，对当前最优点amin进行局部随机扰动产生50 0 d个候选点，以及从集合2 内均匀随机选取50 0 d个候选点，最后得到1 0 0 0 d个候选点，然后从这些候选点中挑出使得 sg(）的函数值大于等于tn的那些点，得到集合三=1,n。计算代理目标函数值 se(3),j=1,，n e 及进行归一化，得到代理模型分值VR(E),j=1,ne。计算1,，Em。和已估值点集合（包括已知的所有估值成功的点和所有估值失败的点）之间的距离，并进行归一化，得到距离分值 V(5),j=1,ne。计算每个点的总体分值W;Vr(E)+(1-Wi)Vp(),j=,ne,将具有最小总体分值的点；作为新采样点anew。在全局搜索步中，求解问题maxA(c,p),其中(ar,)=min lla-aill,aES得到中到已估值点集合距离最大的点，作为新采样点new。在新采样点anew处对真实目标函数进行估值，并更新已估值点集合。若估值成功，则比较fnew=f（a n e w）与当前最优值fmin=f(amin）的大小，若fnewfmin，则更新amin和fmin。此时采用MADS算法，以真实黑箱函数为目标函数，在min 附近进行局部搜索，并且允许进行4d次真实黑箱函数估值。之后更新已估值点集合和相应的目标函数值集合，若找到更好的解点，则更新amin和fmin。之后返回优化搜索阶段。代理模型se(c）和sg(a）的更新在局部搜索步完成。当真实目标函数估值次数超过预设的值时，算法终止。算法具体细节参见文献4。C1E41期3自适应代理优化算法SHEBO算法转换搜索的每个子步都在2 集合中均匀随机采点，而且还有单独的全局搜索步，导致算法在保证搜索具有全局性方面花费过多资源，降低了算法效率。例如，当算法在真实黑箱函数的全局最优点附近所采样本点个数比较多以后，局部搜索步得到的新采样点很可能位于真实的全局最优点附近，这种情况下运行含有在2 集合中进行均匀随机采点的转换搜索子步得到的new很可能对刻画真实目标函数的全局最优解附近的轮廓不起作用，因此对计算资源造成浪费。本文基于 SHEBO算法框架，采用了能更好平衡局部搜索和全局搜索的自适应转换搜索步。在算法迭代早期的转换搜索步中，在当前最优点附近以较大的标准差进行随机扰动生成候选点以加强对远离当前最优点的区域的搜索力度。随着迭代的进行，代理模型对真实函数的逼近程度逐渐变好，因此当前最优点位于真实最优点附近的可能性变大,从而逐渐需要对当前最优点附近区域进行充分搜索，于是在算法的转换搜索步中随机生成候选点所采用的标准差随迭代步数的增加而逐步减小。由于三次径向基插值函数和薄板样条径向基插值函数具有形式简单，没有超参数且对原函数有优良的拟合效果的特点，这两种径向基插值函数是目前径向基代理模型方法相关文献中采用最多的。为了进一步提升代理模型的拟合能力，本文采用这两种径向基插值函数的凸组合作为目标函数的代理模型，并根据这两种径向基插值函数模型在新采样点处的误差大小自适应地配置其组合系数1 1 ，从而进一步提升算法的数值效果。与文献4 一致，文中采用线性径向基插值函数作为约束函数的代理模型。本文提出的带有隐藏约束及昂贵黑箱目标函数问题的自适应代理优化（Adaptive Sur-rogate optimization of problems with Hidden constraints and Expensive Black-box Objec-tives，A SH EBO）算法步骤如下：算法1 带有隐藏约束及昂贵黑箱目标函数问题的自适应代理优化（ASHEBO）算法输入允许进行的最大真实黑箱函数估值次数nmax；初始采样点个数 no；转换搜索阶段采用的权重向量W=（W i，W p)，最大扰动参数omax，最小扰动参数omin；输出算法停止迭代后得到的最优点amin和对应的最优值fmin。步1（初始化）通过拉丁超立方体采样在中生成no个初始采样点，以表示初始采样点集合，并在每个采样点处对真实黑箱目标函数于进行估值。将已有采样点集分为估值成功点集Pe和估值失败点集Pu。记B=aiEPe:(a,f(a)。步2（找到当前最好的采样点及对应的目标函数值）在集合。中，找到取最小目标函数值的点amin=arg minf(a),并令 fmin=f(amin)。步3 令搜索阶段指示变量fag=1,转换搜索子步指示变量i=1。步4 当不满足迭代终止条件（即nno，根据当前B和g(a)更新s%/el/带隐藏约束昂贵黑箱问题的自适应代理优化方法cESe9394白富生，兰秘28卷eieelPe(分别表示和更新前的表达式解辅助优化问题（5）其中由取代。由t品t）log(n-no+1)取代。记得到的解为new。令 flag=2。转步4(d)。(b）（转换搜索）若flag=2，则通过对amin进行如下随机扰动得到候选点集合三=51,51000d),其中(8)这里nmax-nOn=Omin+(omax-Omin)nmax-(no+1)pER的每个分量由均值为0,标准差为1 的随机变量取值得到，表示按分量相乘。从三中剔除那些使得 sg(）的函数值小于 tn 的点。然后对三中每个元素，计算其代理模型分值和距离分值，并分别采用权重W和1 W,对两个分值进行加权求和，从三中选出使加权求和得到的值最大的候选点，记为anew。若ip,则令i:=i+l；否则，令fag=3,i=1。转步4(d)。(c）（全局搜索）若flag=3，在中找到距离集合最远的点，记为anew，并令flag=1;(d）（新点估值及采样点集更新）在anew处对黑箱函数进行估值，得到fnew=f(anew)。更新 和 g(ac)。如果 fnew E R,令 Pe:=Pe Ucnew),B:=BU(cnew,f(cnew);否则,令 Pu:=PuUanew。令 n:=n+1。(e）（强化的局部搜索）如果fnewu，计算bk=uk-（Sj,u k)）。如果bhlh，用bk取代sj,h；否则用u取代Sj,k。然后把集合三中满足sg(si）t n 的点剔除，即把很可能是估值失败点的候选点剔除，得到集合三=(51,，m。与文献4 一致，计算代理目标函数值se(s,),j=1,nc，并进行归一化，得到每个候选点的代理目标函数分值：令这里 smax=max(se(5):j=1,nel,smin=min(se(3):i=l,ne)。如果州令V（）-）计算和已估值点集合（包括已知的所有估值成功的点和所有估值失败的点）之间的距离，并进行归一化，得到每个候选点的距离分值：令,=minlE,-all:E,j=l,ne,这里 max=max,:j =1,ne,mi n =mi n A,:j =1,n e 。如果 Amax=mi n，则令Vp(E,）=1,j=1,，n c。根据权重向量W的分量W,计算每个候选点的总体分值：V(s;)=WiVr(5i)+(1-W)Vd(Ei),j=1,ne,将具有最小总体分值的侯选点作为新采样点Cnew。在数值实验部分，这里与文献4一致，按照预先给定的权重向量W=1,0.95,0.8 5,0.7 5,0.5,0.3 5,0.2 5,0.1,0)，依次选取分量Wi。在全局搜索步，求解问题max(ac,p),其中(a,)=minll-zll,aE得到中到已估值点集合距离最大的点，作为新采样点Cnew。在新采样点anew处对真实目标函数进行估值，并更新已估值点集合。若估值成功，则比较fnew=（a n e w）与当前最优值fmin=f(amin）的大小，若fnewfmin，则更新amin和fmin，并采用MADS算法，以真实黑箱函数为目标函数，在min 附近进行局部搜索，并且允许进行4d次真实黑箱函数估值。之后更新已估值点集合和相应的目标函数值集合。若找到更好的解点，则更新amin和fmin，并返回步4开始。在步5返回算法找到的最优点和最优值。注意到算法得到的最优解一定为估值成功点。算法ASHEBO的流程见图1。带隐藏约束昂贵黑箱问题的自适应代理优化方法Vr(5)=$j=1,.,nc,smax-smin,VD(.)=AmmE,-Aminj=1,.,nc,2E49596白富生，兰秘开始输人初始化及找到Cmin，Ji mi nflag=1,i=1nnmax是是flag=1flag=2是执行全局搜索得到执行转换搜索得到Tnew,令flag=2Cnew文i0，以及在给定的目标函数估值次数下，由所有S中算法求出的P中某问题p的最小的最优值fL，如果算法s在进行了kASHEBO-v274%ASHEBO*-v166%ASHEBO-*v260%ASHEBO*-v172%ASHEBO*-v266%98测试问题(1,2)8.741010(2,2)7.915 610-2(3,2)2.147 8102(4,2)-1.459.9102(5,2)114.9500102(6,2)8.0685100(7,2)-1.214.9101(8,2)5.309 710-1(9.2)3.802 2100(10,2)9.578 310-7(1,5)6.606 3100(2,5)9.791410-2(3,5)5.369.9102(4,5)1.2147102(5,5)5.730 1102(6,5)7.0573100(7,5)1.1927101(8,5)5.284.210-1(9,5)4.3716100(10,5)3.815410-6(1,10)6.8192100(2,10)8.077 610-2(3,10)-1.0740103(4,10)1.0933102(5,10)2.8623103白富生，兰秘表4SHEBO与ASHEBO算法得到的平均最优值SHEBOASHEBO-v18.4799106.720 610-2-2.148 01021.722710295.39701017.85971001.214.91015.267 010-13.7561109.541 710-76.605 71009.340 210-2-5.369.9102-1.167 5102-5.87421027.052 6100-1.177 41015.017 610-14.22051003.815.910-66.71511008.023 010-2-1.0740103-1.2391102-2.977 210328卷ASHEBO-v2测试问题8.345210(6,10)6.639 410-2(7,10)2.148 0102(8,10)1.7518102(9,10)89.0590101(10,10)7.7926100(1,20)1.2994101(2,20)5.277010-1(3,20)3.5975100(4,20)9.541110-7(5,20)6.4418100(6,20)8.848510-2(7,20)-5.369.9102(8,20)-1.237 8102(9,20)-7.048 3102(10,20)7.2190100(1,30)-1.1623101(2,30)5.039.010-1(3,30)4.4383100(4,30)105.71001023.815710-6(5,30)6.6611100(6,30)5.035 010-2(7,30)1.0740103(8,30)-1.1816x102(9,30)2.877.9103(10,30)SHEBO7.1165100-1.203 81015.823.910-15.040.91008.583 210-68.140.91007.885 210-22.144010390.2360101182.53001023.463.8x1035.34051037.575 51007.268 7100-1.214.9101-1.20741016.451 210-16.128 710-17.7751005.52411001.812010-51.8120 x10-58.84051008.058 8 1007.134010-22.973 410-23.222 01033.222 0103168.440 01023.307.9103-4.00741037.87761007.3350100-1.2150101-1.21961016.593310-16.419 8x10-19.222 81009.58901002.765710-52.765 710-5ASHEBO-v16.51211001.27791015.404 010-14.6674x1008.583310-68.05161006.137 410-2-2.148 0103A.SHEBO-v27.41661001.278 01015.391 210-14.2231108.583 210-68.05531003.291 210-22.148 0 10379.70701016.159.91037.028 8100-1.20691016.092 510-17.442 51001.812010-58.269 71002.100 410-23.221910360.84301014.98631037.40571001.215 010l6.366510-19.219 21002.765 7105次目标函数估值后得到的解元满足f(c)-f(a)(1-n)(f()-fL),则称算法s此时通过了该问题的收敛性测试，其中表示算法s使用的初始点。S中算法s在P中问题上的性能比率定义如下：(11)min(tp,s:sES)其中 tp，s 表示算法在问题p上通过上面定义的收敛性测试时所需的最少目标函数估值次数。因此tp,。越小表示算法s在这个问题上的表现越好。显然rp,s1，并且rp,s=1表示在测试问题p上算法s的表现最好。算法s在测试问题集P上的性能表现函数定义如下：(12)其中1,II表示集合中元素的个数。注意到性能表现函数可以看作是比率rp,s的概率分布。从ps(）的定义可知，算法的性能表现函数图像越高越好。次数表现函数给出了算法s在一定的目标函数估值次数下能够求解的问题的比例，其定义如下：(13)其中 n表示测试问题p的维数。注意到为了体现出问题维度对达到收敛性测试所需要的目标函数估值次数的影响，上述定义中采用np+1作为分母。显然，算法的次数表现函数图像越高越好。(10)tp.Tp,s=KpEP:rp,sal,Ts()EP：np+11期0.550.500.45明（0)S0.400.350.300.251我们采用与生成表4所进行的相同的数值实验的结果绘制算法SHEBO、A SH EBO-v1、A SH EBO-v 2、A SH EBO*-v l、A SH EBO-*v 2、A SH EBO*-v 1、A SH EBO*-v 2 的性能表现曲线和次数表现曲线，见图2。其中在性能表现函数和次数表现函数计算中，式（1 0)的fL取每个算法运行3 0 次，共2 1 0 次运行得到的最好的最优值，n取0.0 5。从图2 中可以看出，采用了自适应转换搜索的6 种算法明显优于原算法SHEBO，同时采用自适应转换搜索和自适应组合代理模型的算法优于只采用自适应转换搜索的算法，采用组合响应面算法优于不采用组合形式的算法。另外，Omax和min 的取值会对算法的数值表现产生影响。算法ASHEBO-v1的数值表现明显优于其他6 种算法。5结语设计能高效求解带隐藏约束的昂贵黑箱优化问题的代理模型算法具有重要实践意义。本文在SHEBO算法的框架下，采用了自适应选取随机扰动标准差的策略对其转换搜索子步的采点方法进行了改进，从而更好地平衡了全局搜索和局部搜索。为了进一步提高目标代理模型对真实黑箱目标函数的逼近程度，采用了自适应调整权重的三次径向基函数和薄板样条径向基函数的凸组合作为代理模型。在50 个测试问题上进行的数值实验表明，采用的自适应转换搜索和自适应组合代理模型可以在很大程度上提升原算法的数值表现。从数值结果可以看出，决定随机扰动标准差的式（9）中max和omin 的取值对算法数值表现具有较大的影响。如何针对问题本身的特点确定max和omin 的大小，是值得进一步研究的问题。参考文献1 Carter R G,Gablonsky J M,Patrick A,et al.Algorithms for noisy problems in gas transmissionpipeline optimization J.Optimization and Engineering,2001,2(2):139-157.2 Ji C,Dames E,Wang Y L,et al.Propagation and extinction of premixed C5-C12 n-alkaneflames J.Combustion Flame,2010,157(2):277-287.3 Booker A J,Dennis J E,Frank P D,et al.A rigorous framework for optimization of expensivefunctions by surrogates J.Structural Optimization,1999,17(1):1-13.带隐藏约束昂贵黑箱问题的自适应代理优化方法SHEBO-ASHEBO-v1-ASHEBO-v2-ASHEBO*-v1ASHEBO*-v2+ASHEBO*-v1+ASHEBO*-v223Q(a)算法性能表现曲线图2 数值实验相关曲线990.60.50.40.30.20.145+SHEBO-ASHEBO-v1ASHEBO-v2-ASHEBO*-v1ASHEBO*-v2+ASHEBO*-v1+ASHEBO*-v2010(b)算法次数表现曲线2030401004 Juliane M,Marcus D.Surrogate optimization of computationally expensive black-box problemswith hidden constraints JJ.INFORMS Journal on Computing,2019,31(4):689-702.5 Myers R H,Montgomery D C.Response Surface Methodology:Process and Product Optimiza-tion Using Designed Ecperiments M.New York:Wiley,1995.6 Digabel S L.Algorithm 909:NOMAD:Nonlinear optimization with the MADS algorithm J.ACM Transactions on Mathematical Software,2011,37(4):1-15.7 Mueller J,Shoemaker C A.Influence of ensemble surrogate models and sampling strategy onthe solution quality of algorithms forcomputationally expensive black-box global optimizationproblems J.Journal of Global Optimization,2014,60(2):123-144.8 Gutmann H M.A radial basis function method for global optimization J.Journal of GlobalOptimization,2001,19(3):201-227.9白富生，冯丹，张柯.求解昂贵黑箱全局优化问题的自适应采样组合响应面方法 运筹学学报，2021,25(2):1-14.10 Powell M J D.The theory of radial basis function approximation in 1990 M/Aduances inNumerical Analysis,Oxford:Oxford University Press,105-210.11 Jie H,Wu Y,Ding J.An adaptive metamodel-based global optimization algorithm for black-box type problems J.Engineering Optimization,2015,47(11):1459-1480.12 Regis R G,Shoemaker C A.Combining radial basis function surrogates dynamic coordinatesearch in high dimensional expensive black-box optimization J.Engineering Optimzation,2013,45(5):529-555.13 Juliane M,Marcus D.Online supplement for Surrogate optimization of computationally ex-pensive black-box problems with hidden constraints J.INFORMS Journal on Computing,2019,31(4):689-702.14 Dolan E D,More J J.Benchmarking optimization software with performance profiles J.Mathematical Programming,2001,91(2):201-213.15 More J J,Wild S M.Benchmarking derivative-free optimization algorithms JJ.SIAM Journalon Optimization,2009,20(1):172-191.白富生，兰秘28卷