基于遺傳算子采樣的自適應(yīng)代理優(yōu)化算法

宋保維, 王新晶, 王鵬

(西北工業(yè)大學(xué) 航海學(xué)院, 陜西 西安　710072)

?

基于遺傳算子采樣的自適應(yīng)代理優(yōu)化算法

宋保維, 王新晶, 王鵬

(西北工業(yè)大學(xué) 航海學(xué)院, 陜西 西安710072)

摘要：提出一種應(yīng)用于黑盒問題(black-box problem)的優(yōu)化算法，稱為遺傳算子采樣(genetic operator sampling,GOS)自適應(yīng)代理優(yōu)化算法。通過對(duì)當(dāng)前樣本進(jìn)行兩兩交叉，對(duì)當(dāng)前最優(yōu)樣本進(jìn)行高斯變異2種算子獲得候選樣本集。對(duì)候選樣本進(jìn)行適應(yīng)性評(píng)估，評(píng)估標(biāo)準(zhǔn)為候選樣本處的交叉驗(yàn)證誤差和該樣本與父代樣本之間最小距離的乘積，將乘積最大的樣本加入已有樣本集。GOS優(yōu)化算法在一維問題中詳細(xì)闡述，與有效全局優(yōu)化算法(efficient global optimization,EGO)和最大化模型誤差算法(maximum square error,MSE)在3個(gè)典型數(shù)學(xué)算例中進(jìn)行對(duì)比，驗(yàn)證該算法的有效性。

關(guān)鍵詞：代理模型；遺傳算子；采樣準(zhǔn)則；代理優(yōu)化

設(shè)計(jì)優(yōu)化問題通常包含計(jì)算量大的高保真度模型(計(jì)算流體力學(xué)、有限元分析、基于試驗(yàn)的工程計(jì)算等)。由于目標(biāo)函數(shù)與設(shè)計(jì)變量之間沒有顯式函數(shù)表達(dá)，這類問題稱為黑盒問題。傳統(tǒng)基于梯度的優(yōu)化算法(牛頓法)和基于函數(shù)估計(jì)的優(yōu)化算法(遺傳算法)已經(jīng)不適用于此類問題。代理模型作為一種有效的工具，為黑盒問題提供滿足一定精度的合理近似。同時(shí)，在設(shè)計(jì)優(yōu)化過程中，為了減小計(jì)算代價(jià)和過濾高保真度模型噪聲，使用代理模型已經(jīng)成為一種趨勢(shì)。典型的代理模型包括多項(xiàng)式響應(yīng)面(PRS)、克里金模型(KRG)、徑向基函數(shù)(RBF)、支持向量回歸模型(SVR)等。代理模型方法已經(jīng)廣泛應(yīng)用于飛行器設(shè)計(jì)、汽車設(shè)計(jì)等領(lǐng)域。

基于代理模型的優(yōu)化算法是依據(jù)少量初始樣本建立代理模型，基于采樣準(zhǔn)則在設(shè)計(jì)空間增加樣本并對(duì)代理模型進(jìn)行更新，當(dāng)模型精度滿足要求時(shí)，對(duì)代理模型進(jìn)行優(yōu)化獲得最優(yōu)解的算法。代理優(yōu)化算法從Jones等人提出有效全局優(yōu)化算法(EGO)[1]開始，獲得了廣泛關(guān)注，并成功應(yīng)用于相關(guān)工程設(shè)計(jì)優(yōu)化[2-4]。此后，很多EGO改進(jìn)算法[5-6]以及不同的自適應(yīng)采樣代理優(yōu)化算法[7-10]被提出。有些方法在尋優(yōu)過程中逐步提高代理模型整體精度，當(dāng)?shù)螖?shù)達(dá)到最大時(shí)對(duì)代理模型進(jìn)行優(yōu)化；有些方法在尋優(yōu)過程中僅考慮最優(yōu)解附近的局部區(qū)域，當(dāng)確定最優(yōu)解區(qū)域后重點(diǎn)對(duì)該區(qū)域進(jìn)行尋優(yōu)。大部分代理優(yōu)化算法通過優(yōu)化輔助函數(shù)獲得新增樣本。本文提出的優(yōu)化算法的優(yōu)勢(shì)是不需要優(yōu)化輔助函數(shù)，通過遺傳算子獲得候選樣本集，通過采樣準(zhǔn)則獲取新增樣本，提高模型更新效率；同時(shí)該算法適用于各種代理模型，具有廣泛適用性和穩(wěn)定性。GOS算法與EGO、MSE算法進(jìn)行對(duì)比，證明算法的有效性。

1基于GOS的自適應(yīng)代理優(yōu)化算法

1.1自適應(yīng)采樣方法

一種好的采樣準(zhǔn)則可以在全局空間探索和局部空間開發(fā)之間進(jìn)行權(quán)衡。本文提出的采樣準(zhǔn)則的基本過程是建立樣本交叉驗(yàn)證誤差的代理模型；通過對(duì)已有樣本進(jìn)行兩兩交叉、對(duì)當(dāng)前最優(yōu)樣本進(jìn)行變異產(chǎn)生新的候選樣本集，同時(shí)計(jì)算候選樣本集中每個(gè)樣本與已有樣本的最小距離，交叉驗(yàn)證誤差和最小距離的乘積作為評(píng)價(jià)候選樣本適應(yīng)性的準(zhǔn)則，將乘積最高的候選樣本作為新增樣本。采樣準(zhǔn)則的基本思想是：在交叉驗(yàn)證誤差較大處采樣可以很好地提高代理模型的精度，計(jì)算候選樣本與已有樣本的最小距離可以避免樣本聚集，二者的乘積是對(duì)設(shè)計(jì)空間探索和開發(fā)的一種權(quán)衡。

交叉驗(yàn)證(cross validation,CV)誤差通常用來驗(yàn)證代理模型的精度。典型的leave one out cross validation(LOOCV)是取樣本中的一個(gè)作為驗(yàn)證樣本，剩下的樣本用來建立代理模型。代理模型在驗(yàn)證樣本處的預(yù)測值與該樣本對(duì)應(yīng)的真實(shí)值之間的誤差即為該點(diǎn)處的交叉驗(yàn)證誤差。如果樣本較多，可以將樣本分成K份，取K-1份含有的所有樣本建立代理模型，剩下的一份樣本作為驗(yàn)證樣本，在驗(yàn)證樣本處預(yù)測值與真實(shí)值之差即為該部分樣本的交叉驗(yàn)證誤差；重復(fù)執(zhí)行K次即可得到所有樣本的交叉驗(yàn)證誤差。GOS優(yōu)化算法使用交叉算子和變異算子產(chǎn)生候選樣本集。樣本采用十進(jìn)制編碼，避免使用二進(jìn)制編碼帶來的編碼解碼過程。交叉算子采用中間重組算法(intermediate recombination，IR)，這種雜交算法結(jié)合兩父代樣本的信息，在父代樣本周圍隨機(jī)產(chǎn)生2個(gè)子代樣本

(1)

式中,X和Y是父代樣本,Z是子代樣本,α代表[-1,1]之間隨機(jī)選取的權(quán)重因子。每兩個(gè)父代樣本可以產(chǎn)生2個(gè)候選樣本?？紤]到樣本數(shù)量的有限性,交叉操作對(duì)于所有樣本兩兩進(jìn)行,可以進(jìn)行較大范圍的樣本探索。

高斯變異算子,是一種對(duì)重點(diǎn)區(qū)域局部搜索的變異算子。在進(jìn)行變異操作時(shí),用符合均值為m,方差為s2的正態(tài)分布的一個(gè)隨機(jī)數(shù)代替原有的基因值。具體實(shí)現(xiàn)時(shí),均值、方差的取值和變異位按(2)式處理

(2)

式中,xpbs是當(dāng)前過程最優(yōu)樣本,umax和umin為設(shè)計(jì)變量上下限,ri是[0,1]之間的隨機(jī)數(shù),x′為變異后樣本。變異算子只針對(duì)樣本中的最優(yōu)樣本進(jìn)行操作,保證了局部開發(fā)的特性。

候選樣本的適應(yīng)性評(píng)估采用下式進(jìn)行

(3)

(4)

式中,Np代表每一代候選樣本的數(shù)量。

為了防止新增樣本的聚集,每隔5次(d≤3)或10次(d>3)采樣進(jìn)行1次優(yōu)化運(yùn)算。其中d為設(shè)計(jì)變量的數(shù)量。

1.2GOS優(yōu)化算法流程

GOS優(yōu)化算法的具體步驟為:

1) 采用OLHS(optimal latin hypercube sampling)試驗(yàn)設(shè)計(jì)方法在設(shè)計(jì)空間選取初始樣本,并運(yùn)行高保真度模型得到相應(yīng)的響應(yīng)值。

2) 基于樣本及其響應(yīng)值,構(gòu)建代理模型。本文采用KRG方法建立代理模型,但是并不限于KRG模型。

3) 基于LOOCV得到樣本處交叉驗(yàn)證誤差,并用RBF建立交叉驗(yàn)證誤差的代理模型。

4) 對(duì)所有樣本進(jìn)行兩兩交叉運(yùn)算,對(duì)當(dāng)前最好樣本進(jìn)行變異運(yùn)算,得到候選樣本集。

5) 根據(jù)(3)式計(jì)算所有候選樣本適應(yīng)度,將乘積最高的樣本及其響應(yīng)值加入已有樣本空間并更新代理模型。

6) 重復(fù)步驟2)～步驟5)5或10次后進(jìn)行基于代理模型的優(yōu)化得到當(dāng)前最優(yōu)解,將最優(yōu)解及其響應(yīng)值加入樣本空間。

7) 若滿足收斂準(zhǔn)則,優(yōu)化停止;否則執(zhí)行步驟2),進(jìn)行下一輪迭代。本文的收斂準(zhǔn)則為預(yù)先設(shè)定的總的函數(shù)估計(jì)量。

2GOS優(yōu)化算法舉例與驗(yàn)證

采用1-D測試函數(shù)對(duì)GOS優(yōu)化算法進(jìn)行闡述。GOS與MSE和EGO算法在3個(gè)測試函數(shù)中進(jìn)行對(duì)比以驗(yàn)證其有效性。EGO算法是以KRG模型為代理模型的優(yōu)化算法,通過優(yōu)化輔助函數(shù)(excepted improvement,EI)自適應(yīng)采樣求得最優(yōu)解。MSE算法是在以KRG為代理模型的優(yōu)化算法中,在預(yù)測方差最大處進(jìn)行采樣的一種優(yōu)化算法。

2.1測試函數(shù)和試驗(yàn)設(shè)定

1-D函數(shù)、Branin函數(shù)、Hartman3和Hartman6函數(shù)4個(gè)廣泛應(yīng)用的函數(shù)作為測試函數(shù)。它們的數(shù)學(xué)表達(dá)為:

1-D函數(shù)

(5)

Branin函數(shù)

(6)

Hartman3和Hartman6函數(shù)

(7)

式中,a=[1 1.2 3 3.2]。當(dāng)含有3個(gè)變量時(shí),矩陣b和d為

當(dāng)含有6個(gè)變量時(shí),矩陣b和d為

d=

表1　測試函數(shù)的數(shù)值設(shè)定

函數(shù)名稱函數(shù)維數(shù)初始樣本數(shù)量迭代次數(shù)×采樣數(shù)總樣本量最優(yōu)解1-D141×510-6.020Branin2103×5280.398Hartman33184×542-3.863Hartman66569×10155-3.322

表1給出了4個(gè)測試函數(shù)的基本信息，為了避免試驗(yàn)設(shè)計(jì)結(jié)果的偶然性，對(duì)每個(gè)測試函數(shù)進(jìn)行30次優(yōu)化計(jì)算，采用30次計(jì)算結(jié)果的平均值進(jìn)行比較。采用遺傳算法(GA)對(duì)代理模型進(jìn)行優(yōu)化。由于本文設(shè)定的收斂準(zhǔn)則為預(yù)先設(shè)定的函數(shù)估計(jì)量，所以算法優(yōu)劣的判定標(biāo)準(zhǔn)為：在相同函數(shù)估計(jì)量前提下，優(yōu)化結(jié)果更接近最優(yōu)解的算法更好。KRG模型通過Lophaven等人[11]開發(fā)的KRG工具箱獲得，交叉驗(yàn)證、EGO算法通過Viana等人[12]開發(fā)的SURROGATESToolbox工具箱獲得。

2.2GOS算法在1-D函數(shù)的優(yōu)化過程

圖1給出了GOS算法在1-D函數(shù)的優(yōu)化過程。

圖1　GOS算法在1-D函數(shù)的優(yōu)化過程

圖中虛線表示真實(shí)函數(shù)，實(shí)線表示使用已有樣本(方形)建立的代理模型，圓形表示本次迭代過程獲取的新增樣本。初始樣本為[0,0.333,0.666,1]，5次迭代過程加入樣本分別是[0.213,0.810,0.568,0.902,0.089]。從圖中可以看出在5次采樣之后，代理模型與實(shí)際模型已經(jīng)相當(dāng)吻合，使用GA優(yōu)化算法在圖1e)中找到的最優(yōu)解為0.759，響應(yīng)值為-6.019，與實(shí)際結(jié)果符合。

2.3GOS與MSE、EGO、OLHS算法的比較

圖2給出了GOS、MSE、EGO、OLHS 4種優(yōu)化算法對(duì)Branin函數(shù)優(yōu)化時(shí)樣本分布情況。其中前3種都是自適應(yīng)采樣優(yōu)化算法，第4種是基于OLHS方法一步采樣然后對(duì)代理模型進(jìn)行優(yōu)化。Branin函數(shù)含有3個(gè)全局最優(yōu)，算法找到一個(gè)即認(rèn)為找到最優(yōu)解。圓點(diǎn)表示樣本，星號(hào)表示算法得到的最優(yōu)解。從計(jì)算結(jié)果來看，4種算法獲得最優(yōu)解需要的函數(shù)估計(jì)次數(shù)只有22、22、23和28，都比設(shè)定的28次要少。GOS算法的樣本分布均勻，沒有在非最優(yōu)解的區(qū)域(左下、右上)進(jìn)行采樣；MSE算法注重在邊界處進(jìn)行采樣，在邊界精度滿足要求的情況下，開始向內(nèi)部采樣(從左下角開始)并逐步找到最優(yōu)解。EGO算法注重于EI的提升，樣本在最優(yōu)解附近聚集，此時(shí)收斂到最優(yōu)解處需要較多迭代數(shù)；OLHS算法屬于一步采樣算法，樣本數(shù)量預(yù)先設(shè)定，其空間填充特性最好，但是優(yōu)化精度卻不是最高?？傮w來說，4種算法都以較少的樣本找到最優(yōu)解。與一步采樣算法(OLHS)相比，3種自適應(yīng)采樣算法效果更好。

圖2　GOS、MSE、EGO和OLHS算法對(duì)Branin函數(shù)優(yōu)化時(shí)的樣本分布情況

圖3給出GOS、MSE和EGO 3種算法對(duì)Branin、Hartman3和Hartman6函數(shù)的優(yōu)化過程。每一迭代處的最優(yōu)解是30次計(jì)算的平均值。從Branin函數(shù)看，MSE算法表現(xiàn)最好，擁有較快的優(yōu)化效率；GOS算法表現(xiàn)與MSE算法幾乎相同，EGO算法在較少的迭代過程中不能迅速地收斂到最優(yōu)值，優(yōu)化結(jié)果與圖2結(jié)果吻合。在Hartman3函數(shù)優(yōu)化過程中，GOS算法表現(xiàn)最好，在設(shè)定的最大樣本量處得到最好的結(jié)果；EGO算法在優(yōu)化初期效果比較明顯，在優(yōu)化后期尋優(yōu)速度減慢，優(yōu)化結(jié)果與MSE算法相近。在Hartman6函數(shù)的優(yōu)化過程中，EGO算法優(yōu)勢(shì)比較明顯，不僅在采樣初期找到最優(yōu)解，而且尋優(yōu)速度最快；MSE算法效果最差；GOS算法介于兩者之間，但是當(dāng)樣本數(shù)量達(dá)到設(shè)定值時(shí)，其優(yōu)化結(jié)果與EGO結(jié)果相差不大。

圖3　GOS、MSE和EGO算法對(duì)3個(gè)測試函數(shù)的優(yōu)化過程

圖4給出GOS、MSE、EGO、OLHS 4種算法對(duì)3個(gè)測試函數(shù)優(yōu)化結(jié)果的箱體圖。箱體圖得出的結(jié)論與圖3相似。GOS算法對(duì)Hartman3函數(shù)優(yōu)化結(jié)果最好，MSE算法對(duì)Branin函數(shù)優(yōu)化結(jié)果最好，EGO算法對(duì)Hartman6函數(shù)優(yōu)化結(jié)果最好。從圖中還可以看出，除了低維函數(shù)(Branin) 中OLHS算法結(jié)果比較好外，在高維函數(shù)中其優(yōu)化結(jié)果都是最差的，這也說明自適應(yīng)采樣代理優(yōu)化算法要好于一步代理優(yōu)化算法。另外，GOS算法在3種測試函數(shù)中即使不是最好的，也是第2好的；而且從箱體圖厚度可以看出，GOS算法的結(jié)果也是比較穩(wěn)定的，對(duì)初始樣本分布的依賴較小。

圖4　GOS、MSE、EGO和OLHS算法得到測試函數(shù)最優(yōu)結(jié)果的箱體圖

3結(jié)論

本文提出一種優(yōu)化算法，稱為遺傳算子采樣(GOS)的自適應(yīng)代理優(yōu)化算法。該算法通過對(duì)所有樣本進(jìn)行交叉運(yùn)算，對(duì)最優(yōu)解進(jìn)行變異2種算子產(chǎn)生候選樣本集?；谔岢龅牟蓸釉u(píng)估標(biāo)準(zhǔn)，對(duì)候選樣本適應(yīng)性進(jìn)行評(píng)估，該評(píng)估標(biāo)準(zhǔn)能夠很好地在減小模型誤差和避免樣本聚集2個(gè)問題中權(quán)衡。新增樣本的獲得不需要通過對(duì)輔助函數(shù)優(yōu)化，提高了優(yōu)化效率。GOS算法在1-D函數(shù)中進(jìn)行了闡述，在3個(gè)測試函數(shù)中與MSE、EGO、OLHS算法進(jìn)行對(duì)比。結(jié)果顯示：

①自適應(yīng)采樣代理優(yōu)化算法比一步采樣代理優(yōu)化算法更好，因?yàn)樽赃m應(yīng)采樣算法考慮了模型的信息，可以更有針對(duì)性地更新代理模型；

②GOS算法能夠在有限的函數(shù)估計(jì)下獲得較好的優(yōu)化結(jié)果；在測試函數(shù)中它即使不是最好的算法，也是第2好的算法；

③由于避免采用優(yōu)化的方法獲得新增樣本，GOS算法大大提高了代理模型的更新效率；

④GOS算法比較穩(wěn)定，對(duì)初始樣本分布情況依賴較小。

參考文獻(xiàn)：

[1]Jones D R, Schonlau M, Welch W J. Efficient Global Optimization of Expensive Black-Box Functions[J]. Journal of Global Optimization, 1998, 13(4): 455-492

[2]趙敏, 操安喜, 茍鵬, 等. 高效優(yōu)化算法在船舶力學(xué)中的應(yīng)用研究[J]. 船舶力學(xué), 2008, 12(3): 473-482

Zhao Min, Cao Anxi, Gou Peng, et al. Application of Efficient Global Optimization in Ship Mechanics[J]. Journal of Ship Mechanics, 2008, 12(3): 473-482 (in Chinese)

[3]Lei G. Sequential Optimization Method for the Design of Electromagnetic Device[J]. IEEE Trans on Magnetics, 2008, 44(11): 3217-3220

[4]鄧楓, 覃寧, 伍貽兆. EGO方法的訓(xùn)練算法及應(yīng)用[J]. 計(jì)算物理, 2012, 29(3): 326-332

Deng Feng, Qin Ning, Wu Yizhao. Training Algorithms for EGO Method and Applications[J]. Chinese Journal of Computational Physics, 2012, 29(3): 326-332 (in Chinese)

[5]鄒林君, 吳義忠, 毛虎平. Kriging模型的增量構(gòu)造及其在全局優(yōu)化中的應(yīng)用[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2011, 23(4): 649-655

Zou Linjun, Wu Yizhong, Mao Huping. Incremental Kriging Model Rebuilding Method and Its Application in Efficient Global Optimization[J]. Journal of Computer-Aided Design and Computer Graphics, 2011, 23(4): 649-655 (in Chinese)

[6]馮敏, 張建同. 基于改進(jìn)Kriging模型的EGO算法的EI函數(shù)研究[C]∥第十屆中國不確定系統(tǒng)年會(huì), 2012

Feng Min, Zhang Jiantong. Expected Improvement in Efficient Global Optimization based on Bootstrapped Kriging[C]∥The tenth China Annual Conference on Uncertainty, 2012 (in Chinese)

[7]Huang D, Allen T T, Notz W I, et al. Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models[J]. Journal of Global Optimization, 2006, 34(3): 441-466

[8]Mehmani A. Surrogate-Based Design Optimization with Adaptive Sequential Sampling[C]∥53rd AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference, 2012

[9]高月華, 王希誠. 基于Kriging代理模型的多點(diǎn)加點(diǎn)序列優(yōu)化方法[J]. 工程力學(xué), 2012, 29(4): 90-95

Gao Yuehua, Wang Xicheng. A Sequential Optimization Method with Multi-Point Sampling Criterion Based on Kriging Surrogate Model[J]. Engineering Mechanics, 2012, 29(4): 90-95 (in Chinese)

[10] Viana F A, Haftka R T, Watson L T. Efficient Global Optimization Algorithm Assisted by Multiple Surrogate Techniques[J]. Journal of Global Optimization, 2013, 56(2): 669-689

[11] Lophaven S N, Nielsen H B, S?ndergaard J. DACE-A Matlab Kriging Toolbox[EB/OL]. (2002-8-1)[2015-10-22].http:∥www2.imm.dtu.dk/～hbn/dace/.

[12] Viana F A C. SURROGATES Toolbox User′s Guide[EB/OL]. [2015-10-22].http:∥sites.google.com/site/felipeacviana/surrogatestoolbox.

An Adaptive Surrogate-Based Optimization Algorithm Assisted by Genetic Operators Sampling

Song Baowei, Wang Xinjing, Wang Peng

(School of Marine Science and Technology, Northwestern Polytechnical University, Xi′an 710072, China)

Abstract:This paper proposes an optimization algorithm that is applied to Black-box Problem, called Genetic Operator Sampling (GOS) adaptive surrogate-based optimization algorithm. Genetic operators produce candidate sample set. Cross-over operator is executed between any two of samples and mutation operator is executed only on present best sample. Then an assessment criterion, which is the product of the cross validation error of the candidate sample and the minimum distance between it and existing samples, is used to judge the adaptation of each sample. The candidate sample with largest product will be added to existing samples. GOS is illustrated on 1-D function in detail and is compared to EGO and MSE algorithm on three typical functions, the results validated the effectiveness of GOS algorithm.

Keywords:surrogate model; genetic operators; sampling criterion; surrogate-based optimization

收稿日期：2015-10-22

基金項(xiàng)目：國家自然科學(xué)基金(51375389)資助

作者簡介：宋保維(1963—),西北工業(yè)大學(xué)教授、博士生導(dǎo)師，主要從事水下航行器設(shè)計(jì)及多學(xué)科設(shè)計(jì)優(yōu)化等研究。

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)志碼：A

文章編號(hào):1000-2758(2016)04-0614-07