第38卷第6期2021年6月控制理论与应用
Control Theory&Applications
V ol.38No.6
Jun.2021
林成龙，马义中†，肖甜丽
(南京理工大学经济管理学院，江苏南京210094)
摘要：针对具有黑箱特性的昂贵约束优化问题及工程中计算资源利用率不高问题，提出了新的基于均值改进控制策略的并行代理优化算法.该算法为了减少仿真建模计算负担，选取Kriging近似模型对目标函数和约束函数进行近似估计.在Kriging模型基础上，利用均值改进与新增试验样本间的不等关系构建具有距离特性的控制函数.算法的均值改进控制策略通过控制函数调整最大改进值，实现样本设计空间的多点填充.算法适用范围:1)计算成本主要来自于仿真估计而非优化;2)复杂的工程或商业软件内部无法修改的昂贵仿真问题.数值算例和仿真案例表明：该算法可有效获取近似最优解，减少仿真试验次数的同时弱化均值改进准则 的贪婪特性.相比于其他多点填充策略，均值改进控制策略可有效提升算法计算效率.此外，算法获取优化问题近似最优解的稳定性和精度均具有一定优势.
关键词:Kriging模型；昂贵约束优化问题；均值改进控制策略；并行计算；可行性概率
引用格式：林成龙，马义中，肖甜丽.基于均值改进控制策略的昂贵约束并行代理优化算法.控制理论与应用, 2021,38(6):707–718
DOI:10.7641/CTA.2020.00581
Expensive constraints parallel surrogate-based optimization algorithm
based on mean improvement control strategy
LIN Cheng-long,MA Yi-zhong†,XIAO Tian-li
(School of Economics and Management,Nanjing University of Science and Technology,Nanjing Jiangsu210094,China) Abstract:Considering the expensive black box constrained optimization problem and the low utilization of comput-ing resources in engineering,a new parallel surrogate-based optimization algorithm based on mean improvement control strategy is proposed.In order to reduce the
computational burden of simulation modeling,Kriging model is employed to approximate the objective function and constraint function.On the basis of Kriging approximation model,the control func-tion with distance characteristic is constructed by using the inequality relationship between mean improvement and new test sample.The mean improvement control strategy of the algorithm adjusts the maximum improved value through the control function to realize the multi-pointfilling in the sample design space.The algorithm is suitable for:1)the computational cost mainly comes from simulation estimation rather than optimization;2)complex engineering or commercial software can not be modified for expensive simulation problems.Numerical examples and simulation cases show that the algorithm can effectively obtain approximate optimal solution,Compared with other multi-pointfilling strategies,the mean improve-ment control strategy can effectively improve the computational efficiency of the algorithm.In addition,the stability and accuracy of the approximate optimization solution obtained by the algorithm have certain advantages.
Key words:Kriging model;expensive constraint optimization problem;mean improvement control strategy;parallel computing;probability of feasibility
Citation:LIN Chenglong,MA Yizhong,XIAO Tianli.Expensive constraints parallel surrogate-based optimization algorithm based on mean improvement control strategy.Control Theory&Applications,2021,
38(6):707–718
收稿日期:2020−09−01；录用日期:2020−12−30.
†通信作者.E-mail:*****************;Tel.:+8625-84303268.
本文责任编委：刘淑君.
国家自然科学基金项目(71931006,71871119,71771121)，江苏省研究生科研与实践创新计划项目(KYCX200284)资助.
Supported by the National Natural Science Foundation of China(71931006,71871119,71771121)and the Postgraduate Research&Practice Innova-tion Program of Jiangsu Province(KYCX200284).
708控制理论与应用第38卷
1引言
随着计算机仿真建模软件中的有限元分析，计算流体力学等技术在航空航天、产品优化设计及可靠性工程等领域的广泛应用，高精度仿真建模方法减少实物试验成本的同时有效提升了产品质量特性[1–2].但
随着市场对产品更新速度和产品质量要求的不断提高，完全依靠仿真建模技术进行设计和验证往往需要耗费大量时间成本.例如，福特汽车进行一次碰撞仿真试验需要36∼120h，那么进行100次就至少需要5个月的时间[3].尽管计算机计算能力大幅度提升，但如果碰撞试验在10种方案下进行，那么重复100次试验需要4年多的时间，这对企业而言是难以承受的昂贵时间.对于实际中的工程优化和产品设计优化，仅依靠有限试验数据近似建模难以保证代理模型预测精度.所以采用高效空间填充策略增加新增试验点，实现代理模型重构对提升模型精度及优化效率至关重要.此外，大量封装的商用仿真软件无法修改且难以获得设计变量和质量目标之间的内在关系，这种黑箱特性给优化和分析带来了极大困难[4].综上，为了减少昂贵仿真的计算次数和仿真试验成本，采用有限试验数据建立初始代理模型，选取高效的填充策略实现工程问题的并行代理优化(parallel surrogate-based optimization,PSBO)研究成为热点[1,5–6].
并行代理优化算法是基于真实试验数据或有限仿真数据建立近似代理模型，选取高效的多点填充策略对未试验区域进行选点，然后利用计算机的并行计算能力引导新试验点快速收敛到优化问题的全局最优解的办法.因此，代理模型的选择和空间探索多点填充准则是并行代理优化算法实现的关键，常用的代理模型有径向基函数方法、多项式响应曲面法、支持向量机模型及Kriging模型等[1,5–6].其中,Jones等利用Kriging模型对未试验点的不确定性度量能力，选择满足最大期望改进(expected improvement,EI)值的点作为新样本点，实现串行序贯填充的有效全局优化(efficient global optimization,EGO)算法获得了极大发展[1,5,7–8].该方法有效减少了昂贵仿真的时间成本和实物试验的物料成本，被广泛地应用于航空航天、机械工程和工业工程等诸多领域[1–2,5].
现有的代理优化算法多采用串行序贯加点策略，即在每次优化过程只选取一个新样本点进行试验或仿真，待上一次试验结束后再进行下一次试验.例如, Jones等将优化搜索和代理模型空间填充相结合，提出了最大化EI准则辅助下的标准EGO算法，但EI准则的贪婪性导致收敛速度缓慢[7];Schonlau等针对EI准则收敛缓慢问题，提出了广义参数调整的期望改进准则及包含约束处理的约束期望改进(constraint expected improvement,CEI)准则[8];Ulmer等采用最大化概率改进(probability of improvement,PoI)策略，选取Krig-ing代理模型解决昂贵成本的工程优化问题[9]; Alexandrov和Dennis等通过选取参数阈值，提出了模型预测值的较低置信下界(lower confidence boundary, LCB)框架并将其用于近似优化问题[10].上述策略均是基于改进增量进行优化设计的单点串行序贯填充准则，优化算法中Kriging模型的刷新和下一个样本点的选取必须等待上一次试验的结束，难以有效利用工程问题中丰富的计算资源[11–12].
随着仿真对象日益复杂，采用多台计算机或多核心计算机同时执行仿真或计算任务的并行计算有效减少了设计周期，已成为缩短产品研发时间，提高设计优化效率的常规方法.Ginbingour等的理论分析与实际验证结果表明Kriging模型在并行优化领域具有独特优势，基于Kriging代理模型开发适应于并行计算的多点填充策略逐渐成为解决计算瓶颈，提升设计效率的研究热点[12–13].现阶段基于Kriging模型多点填充策略的研究主要集中于多次优化同一加点策略进行空间填充.例如,Ginsbourger等基于严格推动提出的q–EI多点填充策略及为解决变量较多时q–EI策略计算困难问题，发展的Kriging Believer和Constant Liar填充策略.Kriging Believer和Constant Liar策略分别选取预测均值和初始样本集最小值作为响应的伪值来近
似q–EI策略，近似效果较好.但随着单次填充样本点个数q增大，并行优化效率提升不明显[13]; Zhan基于影响力函数的距离特性构造了伪期望改进(pseudo expected improvement,PEI)填充策略，该策略有效提升了优化效率但未对其进行具体的理论分析与证明[14]；此外，张建侠等发展了兼具局部开放和全局探索功能结合Pareto解集挑选的多目标MS&CA策略并将其应用于压力容器优化设计，但当单次新增样本数q大于3时，收敛效率提升不明显[15]；此外,Viana 等采用多种代理模型分别建模，利用不同模型预测能力进行试验点选取实现多点填充并将其应用于稳健优化设计[16];Hamza等提出多种策略分别选取试验点的方法进行多点填充设计并将其应用于车体碰撞优化设计[17]；陈志旺等提出了融合多属性决策的双层种筛选策略求解高斯模型参数并将其应用于多目标优化问题中[18].更多关于多点填充设计方案请参见综述性文献[12,19].
在实际工程优化中，昂贵约束并行优化问题的挑战来源于缺乏合适的多点填充策略和设计空间中可行解的获取.因此，如何进行有效的多点填充设计和可行解获取成为并行优化算法的关键.针对上述问题，文章的主要思想及框架为：首先，依据贝叶斯先验假设，后验分析及Kriging近似模型的插值特性，经过理论推导与分析给出了均值改进，未试验样本点及新增样本点三者之间的不等关系.其次，基于理论推导结果定义控制函数，结合Kriging模型最大改进特性构
第6期林成龙等：基于均值改进控制策略的昂贵约束并行代理优化算法709
造具有空间调整距离特性的均值改进控制(mean im-provement control,MIC)策略及拓展的期望改进控制(expected improvement control,EIC)策略实现多点样本填充设计，选取经典的可行性概率(probability of feasibility,PoF)策略作为MIC 或EIC 策略权重兼顾可行解的可行区域探索.然后，针对具有黑箱特性昂贵约束优化问题，综合启发式搜索算法中的差分进化优化算法,Kriging 模型及约束均值改进控制(constraint mean improvement control,CMIC)填充策略和基于最大改进期望拓展的约束期望改进控制(constraint expected improvement control,CEIC)多点填充策略，提出了适用于多核计算机或多台计算机并行计算环境，基于约束均值改进控制策略的并行代理优化算法.最后，选取经典测试函数及航空减速器优化设计案例进行验证分析.文章的主要创新点及贡献:1)给出改进控制函数(control function,CF)的定义及其理论证明;2)提出了基于均值改进控制的CMIC 多点填充策略及拓展的CEIC 多点填充策略;3)对于Zhan 等人提出的PEI 策略给出了理论分析与解释[14].
2Kriging 模型
假定试验数据为n 次试验获取结果，记初始观测矩阵为X =[x 1x 2···x n ]T ,x ∈R d 及对应的响应矩阵y =[y 1y 2···y n ]T y ∈R ，初始样本集记为Ω=
[X ,y ].Kriging 模型将黑箱函数y (x )看作包含回归项
的随机过程Y (x )的一次实现.即任意设计点x 对应的响应值Y (x )表示随机过程的可能取值之一:
y (x )=Y (x )=µ+z (x ),
(1)
其中:µ为全局趋势项，反映近似目标函数在设计空间
的总体分布趋势;z (x )是均值为零、方差为σ2
z 的平稳高斯过程，表示对近似模型的校正.
z (x )对Kriging 模型的近似能力起决定性作用，其空间分布数据的协方差满足如下关系:
Cov(z (x i ),z (x j ))=σ2
z R (x i ,x j |θ),
其中:R (x i ,x j |θ)为Kriging 核函数;θ为核函数的关键参数，具备自适应调节设计点之间相关性能力.本文选取满足如下关系的高斯核函数:
R (x i ,x j |θ)=exp(−d ∑k =1
θi |x k i −x k j |2
),
其中:d 为样本点x 的空间维度;x k i 表示第i 个样本点在第k 个维度的值.
Kriging 插值近似模型可表示为ˆy =c T y 且满足最优线性无偏估计E (y −ˆy )=0，经计算得Kriging 模型
的预测均值µˆy 和预测方差s 2
ˆy 为
µˆy =ˆµ
+r T R −1(y −1ˆµ),σ2ˆy =ˆσ2z [1−r T R −1
r +(1−1T R −1r )21T R −11
]，其中:r =[R (x ,x 1)R (x ,x 2)···R (x ,x n )]T 为任
意试验点x 的相关矢量;ˆµ=1T R −1y
1T R −11
为趋势项µ的
估计值;ˆσ2z =(y −1ˆµ)T R −1(y −1ˆµ)n
为方差σ2
z 的
估计值;R 为相关系数矩阵，可表示如下:
R = R (x 1,x 1)R (x 1,x 2)···R (x 1,x n )R (x 2,x 1)R (x 2,x 2)...R (x 2,x n ).........R (x n ,x 1)R (x n ,x 1)...R (x n ,x n )
.基于上述信息,Kriging 近似模型可由式(1)改写为如下形式:
ˆy =ˆµ+r T (x )R −1(y −1ˆµ).
(2)
3基于改进控制的均值改进控制策略
3.1
最大均值改进策略
样本集Ω中已知响应的最小值记为y min ，设计空
间中Kriging 模型可获得未知试验点的预测响应值Y (x )，则y min 相较于Y (x )的最大改进表示如下:
I(x )=max(0,y min −Y (x )).(3)
Kriging 模型在未知试验点的响应值Y (x )的最大预测改进的均值MI(x )=M [I(x )]=y min −ˆy .整理可得均值改进(mean improvement,MI)策略如下:
MI(x )=
{
y min −ˆy ,y min >ˆy ,
0，其他.
3.2最大期望改进策略
假设任意未试验点x 对应的预测响应值Y (x )是满
足正态分布Y (x )∼N (ˆy ,s 2ˆy )的随机变量，且Y (x )的最大改进为I(x )=max(0,y min −Y (x )).Jones 等对I(x )取期望E[I(x )]实现对未试验空间的高效探索，经过理论推导得到单点填充EI 策略的解析形式[7–8].当s ˆy =0时,EI =0；当s ˆy >0时,EI 单点填充策略可表示如下:
EI(x )=(y min −ˆy )Φ(
y min −ˆ
y s ˆ
y )+s ˆy ϕ(
y min −ˆy s ˆy )，其中Φ(·)和ϕ(·)分别表示标准正态分布累计概率密度
函数和概率密度函数.
定理1Kriging 初始模型条件下，假定MI 均值
改进策略或EI 期望改进策略获取的第1个新增试验点为x m ，依据贝叶斯假设可知：已知最小值y min 与新增试验点x m 对应的预测响应值ˆy (x m )满足不等关系ˆy (x m )<y min ，记ˆy (x m ):=y min ，在改进策略下单次新增q 个样本点.模型校正y min −ˆµ及未试验点x ，样
710控制理论与应用第38卷
本点x m 和均值改进y min −ˆy 存在如下不等式关系:
y min −ˆy (y min −ˆµ)n +q −1∏m =n +1
[1−R (x ,x m |ˆθ
)].证根据Kriging 模型的插值特性，将式(2)进行展
开，近似模型可重写为如下形式:
ˆy =ˆµ+n ∑i =1
c i R (x ,x i |ˆθ).(4)
由改进假设知ˆy (x m )<y min ，记ˆy (x m ):=y min .
将均值改进策略填充的样本点x m 代入式(3)，得
y min =ˆµ+c m +n ∑i =1,i =m
c i R (x m ,x i |ˆθ
).(5)挑选任意未知试验点x 与已知新增试验点x m 的相
关函数R (x ,x m |ˆθ
)，并与式(5)左右两侧同时做积，记R (x ,x m |ˆθ
)=R (x ,x m )，整理得(y min −ˆµ)R (x ,x m )=
c m R (x ,x m )+n ∑
i =1,i =m
c i R (x m ,x i )R (x ,x m ).
(6)
易知，设计空间中样本点x ，新增样本点x m 及任意已知样本点x i 存在如下关系:
c m +n ∑i =1,i =m
c i R (x m ,x i |ˆθ
) n +1∑i =1
c i R (x ,x i ).依据不等式性质，可将式(6)改写为如下近似不等式形式:
(y min −ˆµ)R (x ,x m |ˆθ) ˆy −ˆµ.(7)
式(7)两侧同时加上最小值y min ，整理变形后得到
y min −ˆy (y min −ˆµ)(1−R (x ,x m |ˆθ
)).(8)
假设单次循环中一次增加q 个点，重复上述步骤,
可得如下关系:
y min −ˆy (y min −ˆµ)n +q −1∏m =n +1
(1−R (x ,x m |ˆθ
)
).(9)证毕.
3.3均值改进控制函数
由定理1知，模型校正y min −ˆµ，点x ,x m 及均值改
进y min −ˆy 的不等式关系.在贝叶斯后验条件下,Krig-ing 模型未试验点的回归项ˆµ为常数.故Kriging 模型的均值改进函数MI(x )=y min −ˆy (x )主要受未试验点x ,x m 的空间距离核函数控制.因此，基于空间距离核函数对均值改进的控制特性，定义控制函数:
CF(x )=1−d ∏k =1
exp(−ˆθk |x k −x k m |2),
其中x k m 为已知填充策略新增试验点x m 在第k 个维度处的值.
令dis =d (x ,x m )表示点x 与新增试验点x m 之间
的距离关系，点x 与点x m 满足关系:
lim dis →0
CF(x )=0,
lim dis →∞
CF(x )=1.
3.4均值改进控制策略
由定理1可得,I(x )的改进范围受到预测均值ˆy 与
控制函数CF 的双重作用.由定理1不等式关系知：控制函数主要依据选择填充策略增加的样本点x m 与未试验点x 间的距离关系对改进增量进行约束控制且取值满足0 CF(x ) 1；因此，将CF(x )作为I(x )的权重得到IC(x )=I(x )·CF(x ).易知IC(x ) I(x )，故可以实现对I(x )改进的逐步减少.综上，基于控制函数构建均值改进控制策略:
MIC(x )=MI(x )·CF(x ),(10)
由式(10)及第3.3节解控制函数的定义可知：在初
始Kriging 模型超参数ˆθ,ˆµ一定时，当未试验点x 与x m
越近，控制函数越接近于1，倾向于在x m 附近进行加点,y min −ˆy 的值减小幅度较小，注重局部搜索能力；当未试验点x 与x m 越远，控制函数越接近于0，倾向于远离x m 处进行加点,y min −ˆy 的值减小幅度较大，注重全局探索能力.
同理，可得基于均值改进控制的期望控制策略:
EIC(x )=EI(x )·CF(x ).(11)
由式(11)可知，在超参数ˆθ,ˆµ一定条件下，未试验
点x 与x m 越近,CF 越接近于1，倾向于在x m 附近进行加点，期望改进值EI 波动幅度很小，注重局部搜索能力；当未试验点x 与x m 越远,CF 接近于0，倾向于远离x m 处进行加点，期望改进值EI 减小幅度较大，注重全局探索能力.
Zhan 等提出的PEI 策略认为Kriging 模型某一点x 目标值受附近点影响较大，但距离较远的点对x 影响较小.PEI 策略有效减少了昂贵仿真成本，但未给出理论证明[14].MIC 策略与EIC 策略的理论分析表明，采用控制函数CF(CF ∈[0,1])作用于最大改进I(x )来逐步减少MI 或EI 填充策略的贪婪特性.对于PEI 填充策略而言，作用机理与EIC 策略等价.因此，本文的理论分析结果可用于PEI 策略的解释分析.
假设单次循环过程MIC 和EIC 填充一次增加q 个点，可得两种均值改进控制策略表达式:
MIC(x )=MI(x )n +q −1∏
m =n +1
CF(x ,x m )(12)
及
EIC(x )=EI(x )
n +q −1∏m =n +1
CF(x ,x m ),(13)
其中:x n +1为最大化MI 或EI 策略获取的第1个新增试
验点;x n +q −1为第q 个新增试验点.易知CF ∈[0,1]，故EIC EI ,MIC MI ，依据Bull 关于EGO 算法收
第6期林成龙等：基于均值改进控制策略的昂贵约束并行代理优化算法711敛率问题的证明及分析，可知均值改进控制策略具有
较好的收敛性，具体理论分析结果参见文献[20].
4基于均值改进控制策略的并行代理优化
算法
4.1可行性概率
实际工程中，基于专家经验及结构限制等因素，优
化问题往往存在众多的约束条件.假设昂贵约束优化
问题存在r个约束条件g i(x) 0(i=1,2,···,r)，各
约束条件间彼此相互独立，空间内任意点x对应的约
束响应g i(x)是满足正态分布g i(x)∼N(µˆg
i ,s2
ˆg i
)的
随机变量，令G=(g i)r i=1表示约束Kriging模型的联合后验分布，则试验点x落入可行域的可行性概率可表示为如下形式:
PoF(x)=P(G(x) 0)=
r∏
i=1Φ(−
µˆg
i
sˆg
i
).
其中P(G(x) 0)表示满足所有r个约束条件的约束概率.
4.2约束均值改进控制策略
Schonlau等假设优化目标函数与约束条件函数的随机过程相互独立，提出了适应于单目标约束优化问题的约束期望改进CEI填充策略[8].在Schonlau等假设条件下，将满足约束的概率和目标函数的改善概率结合，得到兼顾当前最佳设计点改进和满足约束的概率P[I(x)∩G(x)]=P[I(x)]·P[G(x)]；计算均值改进和约束同时满足条件下I(x)∩G i(x)的期望，得到CEI(x)=E[I(x)∩G i(x)]=EI(x)·PoF(x).因此，将PoF作为MIC多点填充策略的权重，得到两种约束均值改进控制策略
CMIC(x)=MIC(x)·PoF(x)(14)
及
CEIC(x)=EIC(x)·PoF(x).(15)
在多点约束均值改进控制策略填充过程中，依据有限样本建立的Kriging模型预测均值及预测方差不变.CMIC及CEIC多点填充策略假定目标与约束条件相互独立，当寻满足最大化CMIC或CEIC策略的新试验点时,PoF可行性概率在任意试验点x的概率性质不变.因此，可实现控制函数对均值改进的调整及可行性概率的再平衡.同时,CMIC策略通过逐步减少均值改进，减少单点填充时新试验点在均值改进最大处填充的贪婪特性.
4.3算法复杂度分析
实际优化问题中，大多数问题数据集均呈现离散化特性，因此有必要进行算法复杂度分析.代理优化算法是典型的两阶段优化过程：基于试验设计的代理模型建立(刷新)和基于空间填充设计的新试验点获取.因此,CMIC–PSBO及CEIC–PSBO算法复杂度主要来源于两部分：第1部分是代理模型的建立，单目标约束优化问题最终近似优化解数目为1，故其时间复杂度为O[tq(1+r)],r和t分别是约束条件个数和算法最大循环迭代次数；第2部分则来源于CMIC策略及CEIC策略的多点填充寻优，时间复杂度为O[tq].综上,CMIC–PSBO和CEIC–PSBO算法的整体复杂度均为O[tq(1+r)].
CMIC–PSBO和CEIC–PSBO算法二者的区别主要来自于第2部分关于MI值和EI值的计算.在预测均值和预测方差已知情况下,MI只需进行1次减法运算, EI则需要进行9次运算.故相比较CMIC–PSBO算法运算效率高于CEIC–PSBO算法.
4.4算法实现步骤
综合运用Kriging模型，均值改进控制策略及差分进化算法，基于均值改进控制的昂贵约束并行优化算法实现步骤如下:
步骤1算法初始化(试验参数设定).算法终止条件选取；仿真案例选取；初始观测样本数量5d；填充策略单次增加新试验点个数q;
步骤2初始试验设计.拉丁超立方抽取5d个初始观测样本X=[x1x2···x n]T,n=5d，并仿真获得对应的估计值矩阵y=[y1y2···y n]T;
步骤3判断优化结果是否迭代达到终止条件.若是，算法终止；若否，重复步骤4–5–3;
步骤4判断样本集Ω=[X,y]中是否存在可行解G(x) 0.若否，选取PoF策略作为填充设计方案；若是，选取均值控制策略作为填充设计方案;
步骤5算法迭代.依据样本集Ω=[X,y]建立初始Kriging模型，利用差分进化算法获取满足最大化均值改进控制策略的q个新增样本点，并刷新观测矩阵X=X∪x n+1∪x n+2∪···∪x n+q；仿真试验计算q个新增样本点所对应的响应估计值，并刷新响应矩阵y=y∪y n+1∪y n+2∪···∪y n+q及Kriging模型;
步骤6算法终止.输出近似最优解.
5仿真测试及结果分析
为保证所提算法的有效性，选取2个数学算例及航空减速器优化实例[21]进行仿真测试.其中，选取的Toy 问题[15,22]和Kit问题[15,23]算例均为较难求解的约束优化问题，二者局部和全局最优解均位于可行域边界上且非凸.
当q=1时,CEIC策略变为经典的CEI策略.因此，针对单点填充，选取q=1的CEI策略,MS&CA策略[15]，验证所提CMIC策略单点填充的有效性及解的质量特性.当q>1进行多点填充策略比较时，选取具
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议