一種求解帶有昂貴約束的黑箱優(yōu)化問題的算法研究

馮丹

（重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院 重慶市 401331）

在實踐中，工程設(shè)計中的許多約束條件也是在計算上代價昂貴的模型。這種具有昂貴約束條件下的黑箱問題可以被描述為：

由于這類問題的梯度信息不可用，不能使用傳統(tǒng)的基于梯度的優(yōu)化方法求解問題(P)。由于對函數(shù)估值次數(shù)的限制，不依賴于梯度信息的直接搜索方法和元啟發(fā)式方法。響應(yīng)面方法[1]通過已有的采樣點及其對應(yīng)的函數(shù)值建立響應(yīng)面模型(也稱為元模型)來近似原有的目標(biāo)函數(shù)，并通過優(yōu)化響應(yīng)面或基于響應(yīng)面的輔助函數(shù)得到下一個新的采樣點以更新采樣點集合，從而更新響應(yīng)面模型，并找到下一個采樣點；重復(fù)上述過程，直到滿足終止準(zhǔn)則。通常采用達(dá)到給定的目標(biāo)函數(shù)值估值次數(shù)作為響應(yīng)面方法的終止準(zhǔn)則。各種響應(yīng)面方法之間的區(qū)別主要在于響應(yīng)面模型的選擇和新的采樣點的選取方式。響應(yīng)面方法通常采用克里金(Kriging)模型[2]，徑向基函數(shù)(Radial basis function，RBF)插值模型[3][4][5]，多變量回歸樣條[6]等。

2018年，Wu 等人[7]提出了一種基于元模型的約束優(yōu)化方法，稱為基于徑向基函數(shù)的約束全局優(yōu)化(RCGO)，用于求解涉及計算昂貴的目標(biāo)函數(shù)和不等式約束的優(yōu)化問題。RCGO 算法首先通過一種序貫抽樣方法以獲得建立徑向基函數(shù)(RBF)逼近所有計算昂貴函數(shù)的初始點，找到一個可行的解。然后，構(gòu)造一個受近似約束的輔助目標(biāo)函數(shù)，確定下一個迭代點，并進(jìn)一步改進(jìn)可行點。

1 預(yù)備知識

由于模型構(gòu)造的簡易性以及在全局逼近上的可靠性，徑向基函數(shù)插值模型將被用來作為算法中的響應(yīng)面模型。設(shè)是n個兩兩不同的點，每個點對應(yīng)的函數(shù)值已知。我們尋求如下形式的帶多項式尾的徑向基插值函數(shù)：

這里||·||表示Rd上的歐幾里得范數(shù)，為表1 中給出的徑向基函數(shù)形式中的一種，表示由次數(shù)小于等于m 的多項式組成的線性空間。

表1 給出了常用的5 種徑向基函數(shù)。

2 算法框架

接下來提出了一個基于響應(yīng)面模型的求解帶有昂貴約束的黑箱問題的方法。受RCGO 算法[7]的啟發(fā)，在RCGO 算法的基礎(chǔ)上，加上了自適應(yīng)采樣策略及響應(yīng)面模型組合策略來求解此類問題。

表1：徑向基函數(shù)的常見形式（表示相應(yīng)多項式p(x)的最低次數(shù)）

表1：徑向基函數(shù)的常見形式（表示相應(yīng)多項式p(x)的最低次數(shù)）

RBF 函數(shù) 三次函數(shù)(Cubic) r3 1 bTx+a 薄板樣條(Thin plate spline) r2 logr 1 bTx+a 線性函數(shù)(Linear) r 0 a 二次函數(shù)(Multiquadric)0 a高斯函數(shù)(Gaussian)-1 {0}

表2：測試問題的基本信息

在第一階段，與RCGO 算法保持一致。通過求解以下子問題來尋找可行點：

其中，n 為當(dāng)前迭代次數(shù)；如（3）式所示，dmax是任何兩個采樣點之間的最大距離，是從常數(shù)數(shù)組得到的距離系數(shù)，根據(jù)（4）式計算迭代次數(shù)。

在得到可行點后，算法進(jìn)入第二階段，本章在算法的第二階段，采用三次徑向基函數(shù)和薄板樣條徑向基函數(shù)的凸組合生成目標(biāo)函數(shù)響應(yīng)面模型，當(dāng)n=n0，即第一次迭代時，組合方式如下：

接下來在AMGO 算法[8]構(gòu)造的輔助優(yōu)化問題（6）及依次循環(huán)選取指數(shù)參數(shù)以平衡局部搜索與全局搜索的策略基礎(chǔ)上，在算法完成了初始迭代之后，增加了根據(jù)前后兩次響應(yīng)面全局極小點之間的距離選擇搜索類型的準(zhǔn)則。如果此距離小于事先給定的閾值，則采用當(dāng)前響應(yīng)面的全局極小點作為新采樣點，并在下一次迭代中選取適當(dāng)?shù)闹笖?shù)參數(shù)，從而達(dá)到自適應(yīng)采樣的目的。

距離指示函數(shù)Ln(x)的定義如下：

算法1輸入：（1）初識采樣點的個數(shù)n0；（2）最大估值次數(shù)Nmax；（3）兩種核函數(shù)的類型；（4） ；（5）第一階段的距離系數(shù)數(shù)組 其中(0 ≤ξ1 ≤ξ2 ≤ξp ≤1)；（6）第二階段距離指數(shù)數(shù)組 ，其中(0≤t1≤t2≤tp≤1)；輸出：算法搜索到的最佳可行點。步1（初始化）.使用拉丁超立方體采樣生成n0 個初始采樣點，計算每個點的目標(biāo)函數(shù)值和所有約束函數(shù)的值，得到初始樣本數(shù)據(jù)集 ；步2.從初始數(shù)據(jù)集初始化最佳點xbest，并令n=n0, flag=0；步3. 如果初始數(shù)據(jù)集中沒有可行點，則轉(zhuǎn)到步4；否則轉(zhuǎn)到步5；（第一階段）步4.執(zhí)行以下子步驟，直到找到可行點或滿足終止條件（即n＜Nmax）；步4.1（擬合或更新響應(yīng)面模型）使用數(shù)據(jù)集構(gòu)建約束函數(shù)的響應(yīng)面模型，其中約束函數(shù)的近似模型為 ；

步4.2.計算當(dāng)前采樣點之間的最大距離dmax，并根據(jù)迭代次數(shù)從 獲得；步4.3. 解優(yōu)化問題（2），選擇解作為xn+1；步4.4. 計算xn+1 處的函數(shù)值，并將該點加入點集S，令n=n+1；若點xn+1 比點xbest 好，則令xbest=xn+1；步4.5.如果xbest 不是一個可行點，轉(zhuǎn)步4.1；否則，轉(zhuǎn)步5。（第二階段）步5. 繼續(xù)執(zhí)行以下子步驟，直到滿足終止條件（即n＜Nmax）；步5.1.利用已有采樣點數(shù)據(jù)構(gòu)造元模型sc n(x)、st n(x)；并計算模型參數(shù)wc n、wt n；步5.1.根據(jù)（5）式構(gòu)造元模型 以及約束函數(shù)的近似模型；當(dāng)images/BZ_148_1692_882_1709_898.png時，使用全局優(yōu)化算法找到響應(yīng)面模型的全局極小點 ；步5.2 如果images/BZ_148_1623_982_1640_998.png計算，否則令k=k+1，轉(zhuǎn)步5.2c；步5.2a 如果且flag=0，令采樣點xn+1= z*n，flag=1，轉(zhuǎn)步3.3；否則，步5.b 如果flag=1，令k=l-1；如果flag=0，令k=k+1；步5.2c. 根據(jù)迭代次數(shù)由 得到參數(shù)t，用全局優(yōu)化方法求解問題（6），得到的解作為下一個迭代點xn+1；步5.3.計算f(xn+1)以及g1(xn+1),g2(xn+1),...,gm(xn+1)；步5.4.更新數(shù)據(jù)集S；步6.返回最優(yōu)點xbest 以及最優(yōu)值f(xbest).

在第一階段，提出的與RCGO 算法保持一致。首先在使用拉丁超立方體采樣生成n0個初始采樣點，計算每個點的目標(biāo)函數(shù)值和所有約束函數(shù)的值，得到初始樣本數(shù)據(jù)集從初始數(shù)據(jù)集初始化最佳點xbest。如果初始數(shù)據(jù)集中沒有可行點，則轉(zhuǎn)到步4 進(jìn)入第一階段尋找可行點，通過數(shù)據(jù)集構(gòu)建約束函數(shù)的響應(yīng)面模型，這里采用三次徑向基函數(shù)來構(gòu)建約束函數(shù)的近似模型為計算當(dāng)前采樣點之間的最大距離dmax，并根據(jù)迭代次數(shù)從 獲得；解優(yōu)化問題（2），選擇解作為xn+1；計算xn+1處的函數(shù)值，若點xn+1比點xbest好，則令xbest=xn+1；如果xbest不是一個可行點，轉(zhuǎn)重復(fù)步4.1 到步4.5。算法得到可行點后，進(jìn)入第二階段，本章在算法的第二階段，采用三次徑向基函數(shù)和薄板樣條徑向基函數(shù)的凸組合生成目標(biāo)函數(shù)響應(yīng)面模型，組合方式如（5）式所示；約束函數(shù)的響應(yīng)面模型依然采用三次響應(yīng)面模型。并且本章在AMGO 算法構(gòu)造的輔助優(yōu)化問題及依次循環(huán)選取指數(shù)參數(shù)以平衡局部搜索與全局搜索的策略基礎(chǔ)上，在算法完成了初始迭代之后，增加了根據(jù)前后兩次響應(yīng)面全局極小點之間的距離選擇搜索類型的準(zhǔn)則。如果此距離小于事先給定的閾值，則采用當(dāng)前響應(yīng)面的全局極小點作為新采樣點，并在下一次迭代中選取適當(dāng)?shù)闹笖?shù)參數(shù)，從而達(dá)到自適應(yīng)采樣的目的。算法中參數(shù)選取如下：

3 數(shù)值實驗

為了驗證該方法的性能，在一些著名的基準(zhǔn)函數(shù)上進(jìn)行了一系列的實驗和比較。在測試過程中，測試問題的所有目標(biāo)函數(shù)和約束函數(shù)都被視為代價高昂的函數(shù)。使用Windows 環(huán)境下MatlabR2018a 對算法進(jìn)行編程實現(xiàn)代價較高的目標(biāo)函數(shù)和約束函數(shù)分別用元模型逼近。如表2 所示。

本節(jié)主要將新算法的計算結(jié)果與COBRA 算法[9]和RCGO算法[7]的計算結(jié)果進(jìn)行比較。我們總共找了10 個測試函數(shù)，維數(shù)從2 到13 維，包括了7 個Michalwicz 和Schoenauer 測試函數(shù)(G1,G2,G4,G6,G7,G8,G9)以及工程設(shè)計問題PVD4、SR 和Hesse 測試問題。

表3：算法在測試問題上的表現(xiàn)

因為算法具有隨機性因素，為了更公平地進(jìn)行比較，每種算法求解每個問題的實驗的運行次數(shù)都為20,每次運行所允許的最大目標(biāo)函數(shù)估值次數(shù)為200 次。從表3 可以看出，自適應(yīng)組合響應(yīng)面算法在以下測試問題上的數(shù)值實驗結(jié)果大多數(shù)要優(yōu)與COBRA 算法以及RCGO 算法。

4 結(jié)語

在求解帶有昂貴約束的黑箱優(yōu)化問題時，由于約束函數(shù)的具體表達(dá)式也是未知的，所以可以用響應(yīng)面模型來進(jìn)行擬合；同時，為了提高響應(yīng)面模型的擬合精度，將響應(yīng)面模型組合策略能應(yīng)用到擬合目標(biāo)函數(shù)的部分，并在迭代過程中自適應(yīng)的選取新的采樣點，較好的平衡了全局搜索和局部搜索。從數(shù)值實驗來，在求解帶昂貴約束的黑箱優(yōu)化問題時，取得了較好的結(jié)果。