樂春宇，馬義中

(南京理工大學(xué) 經(jīng)濟(jì)管理學(xué)院，江蘇 南京 210094)

0 引言

現(xiàn)代工程優(yōu)化設(shè)計中，常采用高精度仿真模型獲取數(shù)據(jù)，如有限元分析和流體動力學(xué)等[1]，如何在優(yōu)化過程中盡可能少地調(diào)用高精度仿真模型，以提高優(yōu)化效率，顯得尤為重要。由于優(yōu)化過程的黑箱特性無法獲取過程的梯度信息，限制了基于梯度信息的高效優(yōu)化算法的使用，使基于非梯度的啟發(fā)式優(yōu)化算法得到快速發(fā)展[2-3]。在已有啟發(fā)式算法中，遺傳算法(Genetic Algorithm, GA)和粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法是解決黑箱問題最常用的算法，然而啟發(fā)式算法的最優(yōu)解需要通過迭代在大量個體中競爭產(chǎn)生，不適用于需要使用昂貴的仿真模型來獲取數(shù)據(jù)的工程優(yōu)化設(shè)計。

代理優(yōu)化(Surrogate-Based Optimization, SBO)可以用少量樣本點構(gòu)建代理模型，并對真實過程進(jìn)行探索，逐步發(fā)現(xiàn)過程的最優(yōu)解，是解決高耗時黑箱工程優(yōu)化的有效方法[4-5]。相對于多項式響應(yīng)曲面、徑向基函數(shù)、支持向量回歸和神經(jīng)網(wǎng)絡(luò)模型等，Kriging模型在給出預(yù)測值的同時還能給出預(yù)測偏差[6]，結(jié)合預(yù)測值和預(yù)測偏差能夠生成多種加點準(zhǔn)則(Infill Sampling Criteria, ISC)，通過優(yōu)化ISC選擇新的樣本點，能夠自適應(yīng)地更新模型并選擇下一個樣本點，因此Kriging模型成為最具代表性的代理模型。在常用的ISC中，JONES等[7]提出高效全局優(yōu)化(Efficient Global Optimization, EGO)算法，其中使用的EI(expected improvement)準(zhǔn)則兼具全局開發(fā)(exploration)和局部探索(exploitation)的特性，是最經(jīng)典的ISC；WATSON等[8]提出的WB2準(zhǔn)則在EI準(zhǔn)則的基礎(chǔ)上增加了預(yù)測均值的負(fù)數(shù)項，更加注重局部開發(fā)，其尋優(yōu)效率和精度更好[9-10]；SCHONLAU等[11]提出的可行性概率(Probability of Feasibility, PoF)能夠計算未知點落在約束內(nèi)的概率，是代理優(yōu)化中最常用的約束處理準(zhǔn)則。在每次迭代過程中，EGO算法只使用EI值最大的一個點更新模型，在計算資源充足和并行仿真技術(shù)越來越完善的情況下，同時仿真多個點的數(shù)據(jù)和仿真一個點的數(shù)據(jù)所花費的時間資源相同。因此，如何同時選取多個點作為新的樣本點更新代理模型，以減少迭代次數(shù)，提高優(yōu)化效率，受到廣泛關(guān)注。

代理優(yōu)化中，在迭代中加入多個樣本點的方法稱為多點填充或并行優(yōu)化，其主要目的是使用并行計算資源，同時獲取多個新樣本點的真實響應(yīng)值，從而壓縮優(yōu)化周期。常用的多點填充策略有3類：

(1)同時使用多個方法產(chǎn)生多個樣本點。HAMZA等[12]為了避免部分優(yōu)化算法求解EI值時陷入局部最優(yōu)解，采用多種優(yōu)化算法優(yōu)化EI值來產(chǎn)生多個樣本點；HUTTER等[13]通過一個代理模型設(shè)置不同參數(shù)來產(chǎn)生多個樣本點；VIANA等[14]、YE等[15]用多個代理模型產(chǎn)生多個點。這類策略操作簡單，但加點數(shù)量受限，不夠靈活。

(2)多次更新同一個準(zhǔn)則產(chǎn)生多個點。GINSBOURGER等[16]提出的KB(Kriging believer)和CL(constant liar)算法采用“假”響應(yīng)值替代真實響應(yīng)值，并不斷更新Kriging模型，能夠一次產(chǎn)生多個樣本點；ZHAN等[17]提出偽裝期望改進(jìn)算法，采用新的樣本點構(gòu)造影響函數(shù)，再用影響函數(shù)更新EI并產(chǎn)生下一個樣本點。這類策略可以加入任意數(shù)量的樣本點，然而如果同時加入的樣本點較多，則需多次更新ISC，會降低其精確度。

(3)結(jié)合多目標(biāo)優(yōu)化算法，同時優(yōu)化多個準(zhǔn)則，產(chǎn)生Pareto解集，再從解集中選取特定數(shù)量的點。對于無約束優(yōu)化，F(xiàn)ENG等[18]將EI準(zhǔn)則的兩部分同時作為優(yōu)化目標(biāo)，產(chǎn)生Pareto解集；LI[19]采用Kriging模型的預(yù)測均值和預(yù)測偏差作為優(yōu)化的兩個目標(biāo)；WANG等[20]綜合考慮新加入點的失敗率和提升率，將改進(jìn)概率(Probability of Improvement，PI)和EI兩個準(zhǔn)則作為多目標(biāo)優(yōu)化的兩個目標(biāo)；對于約束優(yōu)化，PARR等[21]直接將PoF準(zhǔn)則和EI準(zhǔn)則作為兩個目標(biāo)同時優(yōu)化；HABIB等[22]在約束范圍內(nèi)進(jìn)行局部開發(fā)和全局探索，將EI準(zhǔn)則的兩部分同時乘以PoF準(zhǔn)則作為多目標(biāo)優(yōu)化的兩個目標(biāo)；HABIB等[23]考慮加入樣本點的空間填充性，將距離以及EI準(zhǔn)則和PoF準(zhǔn)則的乘積值作為兩個優(yōu)化目標(biāo)。這類多點填充策略研究最為廣泛，其做法是選取多個合理的ISC作為多目標(biāo)優(yōu)化的目標(biāo)。

已有的多點填充算法重復(fù)使用某種策略選取樣本點，直至達(dá)到終止條件，其模式比較單一。每種準(zhǔn)則都有各自優(yōu)勢和不同適用場景，注重全局探索的準(zhǔn)則更適合探索整個區(qū)域，注重局部開發(fā)的準(zhǔn)則更適合在已知最優(yōu)解附近加入樣本點。為了充分利用每種ISC在不同階段的優(yōu)勢，進(jìn)一步提高代理優(yōu)化的效率，本文提出一種基于Kriging模型的自適應(yīng)多階段并行代理優(yōu)化算法(Parallel Surrogate-based optimization algorithm based on Kriging Model using an adaptive multi-phases strategy, PSKM)，該算法是一種針對約束問題的多點填充代理優(yōu)化算法，在全局探索階段采用EI和PoF準(zhǔn)則探索可行域和約束邊界，在局部開發(fā)階段采用WB2和PoF準(zhǔn)則開發(fā)約束問題的最優(yōu)解，同時制定了自適應(yīng)的兩階段切換策略，使算法能夠根據(jù)加點的情況選擇更好的加點策略。兩個階段均采用文獻(xiàn)[21,24-25]的多目標(biāo)優(yōu)化框架應(yīng)對約束并產(chǎn)生備選點集，再選取多個樣本點完成多點填充。最后通過3個數(shù)值案例和一個工程實例，將所提算法與已有的多點填充算法進(jìn)行對比，驗證了所提算法的性能。

1 有關(guān)概念界定

1.1 單目標(biāo)約束優(yōu)化

本文需要解決的單目標(biāo)約束優(yōu)化問題可以用以下數(shù)學(xué)式表達(dá)：

s.t.

gi(x)≤0,i=1,…,m;

x∈∈d。

(1)

式中：x為d維自變量向量，y(x)為其響應(yīng)值；gi(x)為約束函數(shù)，m為約束的個數(shù)。文中假設(shè)y(x)和gi(x)均為復(fù)雜的黑箱過程，需要調(diào)用昂貴的仿真模型來獲取數(shù)據(jù)。

1.2 Kriging模型

假設(shè)X=[x1,x2,…,xn]為n個已知樣本點，其響應(yīng)值Y=[y1,y2,…,yn]。Kriging代理模型需要通過已知的n個點預(yù)測樣本空間中任意位置點的響應(yīng)值，其預(yù)測值為

(2)

式中C=[c1,c2,…,cn]為已知樣本點在預(yù)測點中所占的權(quán)重。Kriging模型將響應(yīng)函數(shù)看作某個正態(tài)隨機(jī)過程的實現(xiàn)，該隨機(jī)過程定義為

Y(x)=u+Z(x)。

(3)

(4)

式中：r為已知點和預(yù)測點之間的相關(guān)系數(shù)向量；R為已知點之間的相關(guān)系數(shù)矩陣；F是長度為n的列向量，F(xiàn)=[1,1,…,1]T。模型具體的推導(dǎo)以及參數(shù)說明，可參考文獻(xiàn)[6,26]。

1.3 加點準(zhǔn)則

ISC是由模型產(chǎn)生、用于指導(dǎo)尋找新樣本點的一種標(biāo)準(zhǔn)，本節(jié)簡單介紹文中需要使用的3個ISC。

(1)EI準(zhǔn)則

該準(zhǔn)則計算未知點給最優(yōu)解帶來改進(jìn)的值為

I(x)=max(ymin-y(x),0)。

(5)

(6)

式中Φ和φ分別為標(biāo)準(zhǔn)正態(tài)分布的累積概率函數(shù)和概率密度函數(shù)。EI準(zhǔn)則相加的兩部分分別體現(xiàn)局部開發(fā)和全局探索的能力。在已知樣本點處的s2(x)=0會導(dǎo)致該點的EI準(zhǔn)則值為0，因此用EI準(zhǔn)則選點能夠保證已知點不會被重復(fù)選中。另外，EI準(zhǔn)則能夠更好地尋找可能存在的最優(yōu)解，具有更好的探索性。

(2)WB2準(zhǔn)則

WB2準(zhǔn)則更加注重局部開發(fā)，是在EI準(zhǔn)則基礎(chǔ)上改良的一種ISC，其表達(dá)式為

(7)

由式(7)可見，WB2準(zhǔn)則是在EI準(zhǔn)則的基礎(chǔ)上加上預(yù)測均值的負(fù)數(shù)項，其兼具局部開發(fā)和全局探索的特性。因為預(yù)測均值負(fù)數(shù)項的加入增加了局部開發(fā)的權(quán)重，所以WB2準(zhǔn)則能夠集中在已知最優(yōu)解處加點，從而提高尋優(yōu)精度。

(3)PoF準(zhǔn)則

PoF準(zhǔn)則能計算樣本點落在可行區(qū)域的概率值，在假設(shè)約束相互獨立的條件下，其表達(dá)式如下：

(8)

1.4 自適應(yīng)代理優(yōu)化框架

EGO算法是最經(jīng)典的自適應(yīng)代理優(yōu)化算法，現(xiàn)有的代理優(yōu)化和EGO類似，均具有相同的優(yōu)化框架，其主要分為兩個階段：①采用適當(dāng)?shù)某闃臃椒ǎ槿∩倭砍跏紭颖军c，建立Kriging模型；②采用Kriging模型生成ISC，優(yōu)化ISC并找到使ISC達(dá)到最大的點，獲取該點響應(yīng)值將其加入樣本點中并更新代理模型，重復(fù)執(zhí)行直到達(dá)到終止條件。ISC通過代理模型產(chǎn)生，優(yōu)化ISC不需要調(diào)用昂貴的仿真模型，可減少仿真次數(shù)，提高優(yōu)化效率。

2 PSKM分析及實現(xiàn)

PSKM內(nèi)容主要包括3方面：①在約束下的全局探索和局部開發(fā)兩個階段，每個階段如何選擇樣本點并完成多點填充；②如何確定兩個階段的切換條件，以保證兩個階段自適應(yīng)切換；③根據(jù)前面兩點的內(nèi)容，將所有子步驟整合成一個完整的并行代理優(yōu)化算法。下面從這3方面對PSKM進(jìn)行分析和說明。

2.1 約束下的全局探索和局部開發(fā)

EI準(zhǔn)則表達(dá)式中，標(biāo)準(zhǔn)正態(tài)分布的累積概率函數(shù)和概率密度函數(shù)可以看作為局部開發(fā)和全局探索的權(quán)重。WB2準(zhǔn)則在EI準(zhǔn)則的基礎(chǔ)上增加了預(yù)測值的負(fù)數(shù)項，相當(dāng)于增加了局部開發(fā)的權(quán)重。EI和WB2均兼具全局探索和局部開發(fā)的特性，其中EI準(zhǔn)則的全局探索性能更好，能更快地在最優(yōu)解附近加點，但是最優(yōu)解的精度不高；WB2的局部開發(fā)性能更好，尋找最優(yōu)解的速度慢，然而精度較高。因此，PSKM在全局探索和局部開發(fā)兩個階段，分別采用EI和WB2準(zhǔn)則。

關(guān)于約束處理問題，兩個階段都采用PoF準(zhǔn)則。EI準(zhǔn)則的數(shù)值會慢慢降低至0，WB2準(zhǔn)則的數(shù)值量級由真實問題決定，而PoF取值在0～1之間。為了避免某一個準(zhǔn)則占據(jù)主導(dǎo)地位，導(dǎo)致探索約束邊界能力不足，兩個階段均使用多目標(biāo)優(yōu)化框架。約束下的全局探索階段將EI和PoF作為兩個目標(biāo)同時優(yōu)化，局部開發(fā)將WB2和PoF作為兩個目標(biāo)同時優(yōu)化，兩種方法的數(shù)學(xué)表達(dá)式如下：

x∈∈d；

(9)

x∈∈d。

(10)

采用NSGA-Ⅱ可以求解出相應(yīng)準(zhǔn)則的折中解，對樣本點進(jìn)行第一層篩選，將備選點從整個取值范圍縮小到Pareto解集上，然后在Pareto上進(jìn)行第二層篩選，挑選出指定數(shù)量的樣本點。假設(shè)每次迭代需要加入q個新的樣本點，可以對Pareto解集進(jìn)行聚類，將其分割成互不相交的q個子集，再用特殊的選點準(zhǔn)則從每個子集中挑選出一個樣本點即可，本文采用K均值聚類算法對解集進(jìn)行分割。根據(jù)指定的多點填充數(shù)量q，將生成的Pareto解集P分割成q個子集P1,P2,…,Pq，q個子集互不相交且和為P，即:

Pi∩Pj=?,i≠j；

P1∪P2∪…∪Pq=P。

(11)

然后用式(12)的選點標(biāo)準(zhǔn)進(jìn)行第二層篩選，在每一個子集中選出一個點組成xnew，同時用仿真模型獲取q個點的響應(yīng)值，將其作為新的樣本點加入已有樣本點中更新模型，從而實現(xiàn)多點填充。

xnew=[xnew1,xnew2,…,xnewq]。

(12)

選點標(biāo)準(zhǔn)使用的是EI準(zhǔn)則值和PoF準(zhǔn)則值的乘積?？梢詮拿總€子集中選出盡可能滿足約束且EI準(zhǔn)則值盡可能大的點。因為EI準(zhǔn)則不會重復(fù)選擇已知樣本點，所以能夠保證算法的收斂性。最后，將以上步驟整合為約束下兩階段并行優(yōu)化的兩個子算法，分別命名為Cglobal和Clocal，算法步驟如表1所示。

表1 Cglobal和Clocal算法步驟表

2.2 兩階段自適應(yīng)切換算法

表2 G2L和L2G算法步驟表

2.3 PSKM流程

3 算例分析

本章用3種不同類型的數(shù)值算例和1個實際工程實例驗證PSKM的性能，并與已有的幾種經(jīng)典代理優(yōu)化算法進(jìn)行對比。單點填充算法采用文獻(xiàn)[11]中經(jīng)典的CEI(constrained expected improvement)算法。對于多點填充算法，第二類多點填充算法選取文獻(xiàn)[16]的KB算法，為使該算法能夠處理約束，本文將其中的EI準(zhǔn)則換成EI準(zhǔn)則值乘以PoF準(zhǔn)則值，將這種算法簡稱為KBMP(Kriging believer multi-points)；第三類多點填充的算法選取文獻(xiàn)[21]中的雙目標(biāo)多點填充算法，簡稱為DOMP(double-objective multi-points)。

3.1 算例介紹

3個經(jīng)典的數(shù)值算例是來自文獻(xiàn)[25]中的CAM(camel)，SAS(sasena)，GOM(gomez)。CAM是一個單約束多極值優(yōu)化問題，該算例在約束邊界的拐角處有多個局部最優(yōu)解和一個全局最優(yōu)解；SAS是一個多約束多極值問題，其有3個約束條件，2個有效約束和1個無效約束；GOM是單約束且可行域不連續(xù)的約束優(yōu)化問題，其可行域的范圍很小，會出現(xiàn)初始樣本點不在可行域中的情況。工程實例來自文獻(xiàn)[27]的拉伸彈簧設(shè)計問題TSD(tension spring design)，設(shè)計變量為線圈的平均直徑、彈簧的線徑和彈簧的有效線圈數(shù)，設(shè)計目標(biāo)為：在線圈偏轉(zhuǎn)度和線圈強度等約束下，使彈簧的重量最低。

3.2 試驗設(shè)置

(1)設(shè)置初始樣本點 所有試驗的初始樣本點均采用最優(yōu)拉丁方設(shè)計抽取，數(shù)量為8d，其中d為自變量的維度。采用最優(yōu)拉丁方設(shè)計時，設(shè)置不同的隨機(jī)種子會得到不同的樣本點。如果初始樣本點中存在離最優(yōu)點比較近的點，則將導(dǎo)致算法更快地找到全局最優(yōu)解。為了屏蔽初始樣本點的影響，采用20個不同的隨機(jī)種子產(chǎn)生初始樣本點，每個算法對每個算例均進(jìn)行20次試驗。

(2)設(shè)置NSGA-Ⅱ 種群數(shù)量設(shè)置為80q，q為多點填充的數(shù)量，最大迭代次數(shù)為100，交叉分布指數(shù)為5，交叉概率為0.7，變異分布指數(shù)為10，變異概率為0.2。

(3)設(shè)置終止條件 對于3種多點填充算法，設(shè)置每次迭代加入3個新的樣本點。所有試驗都以加入點的總數(shù)T作為終止條件，設(shè)CAM，SAS，GOM的終止條件T=30，CEI算法迭代30次，多點填充算法迭代10次；設(shè)TSD的T=45，CEI算法迭代45次，多點填充算法迭代15次。

3.3 比較指標(biāo)

為了更好地對比說明算法性能，本文從以下3個指標(biāo)對試驗結(jié)果進(jìn)行分析：

(1)算法的絕對誤差 對于每個算例，計算每個算法20次試驗中每次迭代產(chǎn)生的最優(yōu)解的均值f(xbest)，并計算其與真實最優(yōu)解f(x*)之間的絕對誤差，以此衡量算法收斂到全局最優(yōu)解的效率。算法的絕對誤差

(13)

(2)算法的最優(yōu)解性能 對于每個算例，統(tǒng)計每種算法20次試驗最優(yōu)解的性能，包括最值、均值和標(biāo)準(zhǔn)差，并通過對20次試驗結(jié)果做t檢驗來衡量每種算法尋找最優(yōu)解的能力，即算法尋優(yōu)的有效性。

(3)算法的穩(wěn)健性 統(tǒng)計20次試驗結(jié)果的數(shù)據(jù)，采用絕對誤差以10為底對數(shù)形式的負(fù)值制箱線圖，通過觀察每種方法的波動情況來衡量算法尋優(yōu)的穩(wěn)健性。

3.4 結(jié)果分析

根據(jù)4.3節(jié)提到的比較標(biāo)準(zhǔn)對試驗數(shù)據(jù)進(jìn)行處理，結(jié)果如下：

(1)算法的收斂圖

由于每個算例結(jié)果的跨度不同，為了更好地觀察結(jié)果，對AE值取以10為底的對數(shù)，并取負(fù)數(shù)形式，繪制4個算例的算法收斂圖，如圖2所示。

圖中橫坐標(biāo)為新加入樣本點的個數(shù)，縱坐標(biāo)為AE以10為底對數(shù)形式的負(fù)值，其值越大表示算法求解的最優(yōu)解和全局最優(yōu)解的差值越小。CEI算法每次迭代只加入一個新的樣本點，因此其收斂的曲線更加密集。由圖可見，PSKM每次迭代可以加入多個樣本點，相比單點填充CEI，相同精度下PSKM的迭代次數(shù)更少，說明了PSKM的多點填充策略在加快代理優(yōu)化算法收斂速度方面的有效性?？紤]總共消耗的計算資源，即加入相同樣本點數(shù)觀察算法的收斂情況，對于算例CAM和SAS，PSKM的收斂曲線均在其他算法的左上方，說明PSKM的收斂速度更快，最終求解的最優(yōu)解更好；對于算例GOM和TSD，PSKM雖然在前期尋優(yōu)速度較慢，但是因為在局部開發(fā)階段采用WB2準(zhǔn)則能找到更精確的最優(yōu)解，所以隨著加點的進(jìn)行，其收斂曲線會超過其他算法。

(2)算法最優(yōu)解性能表

對于每種算例中每種算法的20次試驗，計算20次試驗結(jié)果的最小值、最大值、均值和方差，并對每個算例下算法兩兩之間的試驗結(jié)果進(jìn)行t檢驗，檢驗置信度為95%時其均值是否較小，結(jié)果如表3所示。

表3 算法最優(yōu)解性能表

4個算例中，PSKM的最小值、均值和最大值均優(yōu)于其他3個算法。因為PSKM不但能在局部開發(fā)階段用Clocal充分開發(fā)最優(yōu)解區(qū)域，尋找精度更好的結(jié)果，而且能自動切換狀態(tài)，在充分開發(fā)某一區(qū)域后，用Cglobal算法繼續(xù)探索其他區(qū)域，所以對于擁有局部最優(yōu)解的CAM和SAS，PSKM也能及時跳出局部最優(yōu)，尋找更好的最優(yōu)解。從結(jié)果的標(biāo)準(zhǔn)差來看，對于GOM算例，DOMP算法的所有結(jié)果較大，導(dǎo)致標(biāo)準(zhǔn)差偏小，因此其總體結(jié)果不如PSKM；對于其他3個算例，PSKM算法的標(biāo)準(zhǔn)差更小。綜上所述，從最值、均值、標(biāo)準(zhǔn)差和t檢驗的結(jié)果來看，PSKM的結(jié)果都不比其余3種算法差，說明PSKM求解問題更有效，所求解的精確度更高。

(3)算法最優(yōu)解箱線圖

繪制每個算例中每種算法20次結(jié)果的箱線圖，如圖3所示，圖中縱坐標(biāo)為AE以10為底對數(shù)形式的負(fù)值?？梢?種算例的20次試驗結(jié)果，PSKM的箱線圖更靠近上方，說明PSKM算法屏蔽初始樣本點影響的能力更好，算法的穩(wěn)健性更好。

4 結(jié)束語

在計算資源充足且并行計算技術(shù)越來越成熟的情況下，在更新代理模型過程中一次加入多個樣本點，可以將充足的計算資源轉(zhuǎn)換成橫向的時間資源，從而縮短優(yōu)化周期，提高優(yōu)化效率?，F(xiàn)有的多點填充代理優(yōu)化算法都是重復(fù)使用某種策略加點，模式較單一，為了充分利用每種ISC在不同階段的優(yōu)勢，進(jìn)一步提高代理優(yōu)化的效率，本文提出PSKM，算法內(nèi)部可以自適應(yīng)地選擇全局探索或局部開發(fā)，并在不同階段采用不同子算法尋找新的樣本點。算例的結(jié)果表明，PSKM不但收斂速度快，而且求解的精確性和穩(wěn)健性更好。