代理模型輔助進(jìn)化算法在高維優(yōu)化問(wèn)題中的應(yīng)用

田 杰 ，譚 瑛 ，孫超利 ，曾建潮

（1．太原科技大學(xué) 機(jī)械工程學(xué)院，山西 太原 030024；2．山東女子學(xué)院 數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院，山東 濟(jì)南 250300；3．太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024；4．中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山西 太原 030051）

1 引言

目前，進(jìn)化算法已經(jīng)在復(fù)雜系統(tǒng)的設(shè)計(jì)中得到廣泛應(yīng)用[1]。通常這些問(wèn)題都擁有大量的決策變量，因此被稱(chēng)為高維或大規(guī)模優(yōu)化問(wèn)題。而在這些復(fù)雜優(yōu)化問(wèn)題中，通常面臨計(jì)算耗時(shí)問(wèn)題，由于進(jìn)化算法在每一代進(jìn)化均需要大量的適應(yīng)值計(jì)算，受限于算法對(duì)計(jì)算資源的要求，進(jìn)化算法難以繼續(xù)在復(fù)雜費(fèi)時(shí)優(yōu)化問(wèn)題中發(fā)揮作用。因此，使用計(jì)算廉價(jià)的代理模型代替實(shí)際的計(jì)算費(fèi)時(shí)的目標(biāo)函數(shù)是進(jìn)化算法用于解決復(fù)雜優(yōu)化問(wèn)題的一種有效策略。文獻(xiàn)[2]通過(guò)基于多種近似模型的PSO算法對(duì)汽車(chē)吸能盒結(jié)構(gòu)進(jìn)行了抗撞性?xún)?yōu)化。文獻(xiàn)[3]提出基于信賴(lài)域的采樣空間更新策略，進(jìn)而發(fā)展了一種基于信賴(lài)域的動(dòng)態(tài)徑向基函數(shù)代理模型優(yōu)化策略。目前，常用的代理模型有響應(yīng)面法，文獻(xiàn)[4]，徑向基法（RBF）以及支持向量機(jī)法（SVM）等?；诖砟Ｐ偷倪M(jìn)化算法中仍然存在一些重要的問(wèn)題需要解決，如模型管理[5]，模型保真度的改善，如何利用更合適的加點(diǎn)規(guī)則來(lái)選取哪些解該被實(shí)際計(jì)算等。目前多種加點(diǎn)規(guī)則已用于模型管理，如期望改進(jìn)（EI）、統(tǒng)計(jì)下限最小值準(zhǔn)則（LCB）、改進(jìn)概率最大值準(zhǔn)則（PI）。文獻(xiàn)[6]在20維問(wèn)題上比較了以上三種常用規(guī)則的性能，得出EI及LCB性能略?xún)?yōu)。但由于GP模型給出的解之間的不確定性差異會(huì)隨著維數(shù)的增大而迅速降低，因此也降低了現(xiàn)有加點(diǎn)規(guī)則的有效性。

2 多目標(biāo)加點(diǎn)準(zhǔn)則

從模型管理的角度出發(fā)，提出了一種新的多目標(biāo)加點(diǎn)準(zhǔn)則用于高維問(wèn)題，將加點(diǎn)準(zhǔn)則定義為一個(gè)兩目標(biāo)問(wèn)題，將期望改進(jìn)準(zhǔn)則EI及統(tǒng)計(jì)下限最小值準(zhǔn)則LCB作為兩個(gè)目標(biāo)，選取第一個(gè)Pareto面上的樣本點(diǎn)進(jìn)行實(shí)際計(jì)算，目的是為了可以從不同的加點(diǎn)準(zhǔn)則中受益，提升算法性能，從而使加點(diǎn)規(guī)則能夠適用于高維問(wèn)題。在這里，多目標(biāo)加點(diǎn)準(zhǔn)則被定義為一個(gè)兩目標(biāo)的最小化問(wèn)題，數(shù)學(xué)描述如下：

式中：S—決策空間，且 S：=［xmin，xmax］，xmin和 xmax分別用來(lái)定義決策空間的上下界；EI（x）—期望改進(jìn)函數(shù)如公式所示，因期望改進(jìn)函數(shù)本身是求期望改進(jìn)最大化的函數(shù)，因此，我們將該函數(shù)前加負(fù)號(hào)，作為最小化函數(shù)處理；LCB（x）—統(tǒng)計(jì)下限最小值準(zhǔn)則，如式（4）、式（5）所示：

式中：fmin—當(dāng)前最優(yōu)適應(yīng)值、y?（x）、s（x）—由 GP 模型得出的關(guān)于解x的預(yù)測(cè)值及其不確定性度量值；ω—常數(shù)，在實(shí)驗(yàn)中，該數(shù)值為2。

3 MICGP-SLPSO算法

在所提出的MICGP-SLPSO中，社會(huì)學(xué)習(xí)微粒群算法（SLPSO）作為優(yōu)化器產(chǎn)生候選解，用高斯過(guò)程（GP）模型對(duì)候選解進(jìn)行預(yù)測(cè)，通過(guò)預(yù)測(cè)信息利用提出的多目標(biāo)加點(diǎn)準(zhǔn)則，選取個(gè)別候選解進(jìn)行實(shí)際計(jì)算并更新GP模型。首先，初始種群用拉丁超立方體的方法生成，初始種群的適應(yīng)值用實(shí)際函數(shù)進(jìn)行計(jì)算，將初始個(gè)體的位置及適應(yīng)值存入數(shù)據(jù)庫(kù)，用于構(gòu)建GP模型。下一步用公式和更新種群位置及速度，當(dāng)需要實(shí)際計(jì)算的代數(shù)執(zhí)行過(guò)后，進(jìn)入使用GP代理模型的迭代，用實(shí)際計(jì)算過(guò)的個(gè)體信息構(gòu)建GP模型，然后用GP模型給出種群中所有個(gè)體的適應(yīng)值及其不確定性，然后根據(jù)這兩個(gè)值用公式和計(jì)算每個(gè)個(gè)體的EI及LCB，利用多目標(biāo)加點(diǎn)準(zhǔn)則選擇第一個(gè)Pareto面上的樣本點(diǎn)重新用原函數(shù)進(jìn)行實(shí)際計(jì)算，然后將實(shí)際計(jì)過(guò)的個(gè)體繼續(xù)存入數(shù)據(jù)庫(kù)，當(dāng)數(shù)據(jù)庫(kù)中的樣本大于GP模型的訓(xùn)練樣本個(gè)數(shù)n時(shí)，只從數(shù)據(jù)庫(kù)中選n個(gè)最新的樣本進(jìn)行訓(xùn)練模型。

3.1 社會(huì)微粒群算法

社會(huì)學(xué)習(xí)粒子群優(yōu)化算法（SLPSO）在高維問(wèn)題上表現(xiàn)表現(xiàn)良好[7]，SL-PSO種群中的個(gè)體會(huì)按照它們的適應(yīng)值排序，除了適應(yīng)值最好的個(gè)體外，每個(gè)個(gè)體都將從適應(yīng)值比自己好的個(gè)體中隨機(jī)選擇一個(gè)個(gè)體進(jìn)行學(xué)習(xí)。如種群中第j個(gè)個(gè)體在第t+1代的進(jìn)化公式如下：

式中：1≤j＜m，個(gè)體k是個(gè)體j隨機(jī)選擇的學(xué)習(xí)者，所以j＜k≤m，m是種群數(shù)m=100+D/10；xkd（t）—個(gè)體k的第d維元素（1≤d≤D，D是決策空間的維數(shù)）；—與個(gè)體j的適應(yīng)值成反比的學(xué)習(xí)概率值；pj（t）—個(gè)體 j的隨機(jī)數(shù)；r1，r2、r3—［0，1］區(qū)間內(nèi)的隨機(jī)數(shù)；（t）—當(dāng)前種群在 d 維上的均值；

ε—影響因子。

3.2 構(gòu)建GP模型

盡管GP模型已經(jīng)在用于解決優(yōu)化費(fèi)時(shí)問(wèn)題中得到廣泛應(yīng)用，但在高維費(fèi)時(shí)問(wèn)題的解決上卻遇到了一些瓶頸，除了引言中所提到的GP模型的現(xiàn)有加點(diǎn)規(guī)則不能很好的適用于高維問(wèn)題之外，隨著訓(xùn)練樣本的增加，構(gòu)建GP模型的時(shí)間也會(huì)相對(duì)增加，而在高維問(wèn)題上構(gòu)建GP模型與低維問(wèn)題相比，需要更多的訓(xùn)練樣本，因此，高維問(wèn)題上的GP模型構(gòu)建變得更加耗時(shí)。因此，作者前期在如何構(gòu)建GP模型能夠滿(mǎn)足精度的同時(shí)盡量提高效率上做了一定的研究與嘗試，具體可參考文獻(xiàn)[8]?；谝陨戏治觯珿P模型的具體構(gòu)建方式描述如下：

創(chuàng)建含有 n 個(gè)樣本（xi，yi），i=1，2，k，n 的數(shù)據(jù)庫(kù) DB，對(duì)任一候選解x的適應(yīng)值y在GP模型中被看作為μ+ε（x）式中ε（x）服從分布 N（0，σ2）：

K 為矩陣，其中矩陣元素為 Kij=C（xi，xj），k（x）=［C（x，x1），…，C（x，xn）］T，X＝（x1，…，xn）為樣本點(diǎn)的輸入值，κ（x）=C（x，x）是x自身的協(xié)方差。C（·，·）為協(xié)方差函數(shù)，具體使用Matérn32函數(shù)作為協(xié)方差函數(shù)：

4 測(cè)試算例

為測(cè)試MICGP-SLPSO算法的有效性，選取了3個(gè)常用測(cè)試函數(shù)，具體函數(shù)詳，如表1所示。函數(shù)公式參見(jiàn)文獻(xiàn)[7]。分別針對(duì)這3個(gè)函數(shù)的30、50、100維，與目前性能較優(yōu)的文獻(xiàn)[4]及文獻(xiàn)[9]算法進(jìn)行性能比較，每個(gè)算法獨(dú)立運(yùn)行20次后進(jìn)行結(jié)果統(tǒng)計(jì)。

表1 三個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)Tab.1 Description of Three Benchmark Functions

與GPEME的比較結(jié)果，如表2所示。實(shí)際評(píng)價(jià)次數(shù)設(shè)定為1000次與文獻(xiàn)[4]相同，由表2我們可以看出，提出的MIC-GPSLPSO在F1，F(xiàn)2和F3身上均獲得了明顯優(yōu)于GPEME的結(jié)果，另外值得注意的是，在GPEME中使用的是LCB加點(diǎn)規(guī)則，因此，MIC-GPSLPSO常采用的將EI和LCB作為多目標(biāo)設(shè)計(jì)的加點(diǎn)規(guī)則，要優(yōu)于僅使用LCB的加點(diǎn)規(guī)則。

表2 MICGP-SLPSO與GPEME在30維問(wèn)題上的結(jié)果比較Tab.2 Comparative Results Between GPEME and MICGP-SLPSOon 30D

圖1 50維F1迭代進(jìn)化圖Fig.1 The Convergence Trends for F1 on 50D

圖2 50維F2迭代進(jìn)化圖Fig.2 The Convergence Trends for F2 on 50D

在高維問(wèn)題上，選用性能優(yōu)于GPEME，使用多模型且同時(shí)使用SLPSO和PSO產(chǎn)生候選解的SA-COSO[9]算法，以及GP-EI及GP-LCB這兩個(gè)分別單獨(dú)以EI規(guī)則及LCB規(guī)則來(lái)進(jìn)行加點(diǎn)的算法在50及100維的問(wèn)題上進(jìn)行比較，實(shí)際計(jì)算次數(shù)減少到10D，D為候選解的維數(shù)。由圖1～圖6的比較結(jié)果可得，提出的MICGP-SLPSO無(wú)論在50維函數(shù)還是100維函數(shù)中，均取得了明顯的優(yōu)勢(shì)，且在每一步都明顯優(yōu)于其他算法。

圖3 50維F3迭代進(jìn)化圖Fig.3 The Convergence Trends for F3 on 50D

圖4 100維F1迭代進(jìn)化圖Fig.4 The Convergence Trends for F1 on 100D

圖5 100維F2迭代進(jìn)化圖Fig.5 The Convergence Trends for F2 on 100D

圖6 100維F3迭代進(jìn)化圖Fig.6 The Convergence Trends for F3 on 100D

5 實(shí)例分析

5.1 實(shí)例的基本參數(shù)

選用的工程實(shí)例為一個(gè)d段階梯軸端位移δ的最小化約束問(wèn)題。該優(yōu)化問(wèn)題為一個(gè)30維的約束優(yōu)化問(wèn)題，其中，d=10，在階梯軸的每一段，都需要優(yōu)化三個(gè)參數(shù)：長(zhǎng)（li）寬（bi）高（hi）。該階梯軸的軸端受力為P=5×104N，材料性能參數(shù)為E=2×105N及σallow=350MPa，該問(wèn)題的數(shù)學(xué)描述如下：

其中，σallow為所有階梯軸的彎曲應(yīng)力約束，AR=25為階梯軸各截面的縱橫比約束，Vmax=1.2×109為材料體積約束，Lmin=5為階梯軸的長(zhǎng)度約束。

5.2 實(shí)例結(jié)果比較

方法與優(yōu)化方法在實(shí)例問(wèn)題上的性能比較，如表3所示。針對(duì)該問(wèn)題，在與現(xiàn)有文獻(xiàn)算法GA，MPS結(jié)果（其優(yōu)化結(jié)果來(lái)自文獻(xiàn)[10]）比較的同時(shí)，增加了三個(gè)傳統(tǒng)優(yōu)化算法的結(jié)果比較，分別是內(nèi)點(diǎn)法（IP），有效集法（AS）以及序列二次規(guī)劃法（SQP）。從表3中我們可以看出，這里算法在更少的計(jì)算次數(shù)下取得了更優(yōu)的結(jié)果。

表3 方法與優(yōu)化方法在實(shí)例問(wèn)題上的性能比較Tab.3 Comparative Resultson 30D Cases

6 總結(jié)

設(shè)計(jì)了多目標(biāo)加點(diǎn)規(guī)則，并將其應(yīng)用到代理模型輔助的進(jìn)化算法中，用于工程實(shí)踐的復(fù)雜優(yōu)化問(wèn)題上，無(wú)論從測(cè)試函數(shù)還是實(shí)例問(wèn)題的應(yīng)用中，該方法都取得了較好的效果，且在高維問(wèn)題上的優(yōu)勢(shì)更加明顯。下一步可將所提的多目標(biāo)加點(diǎn)規(guī)則輔助于其他進(jìn)化算法并應(yīng)用于CFD、FEA等其他更多復(fù)雜工程設(shè)計(jì)優(yōu)化實(shí)例中，進(jìn)一步檢驗(yàn)MGP-SLPSO在工程問(wèn)題中的實(shí)用性。