陸敏芳, 宗 偉, 陳美涵, 楊 波, 王 琳, 張 波

(濟南大學 信息科學與工程學院, 山東 濟南 250022)

在真實世界的問題中,隨著問題特征日益復雜,大多數(shù)工程問題逐步演變?yōu)橐环N黑盒問題,即問題內(nèi)部的具體解析式或工作方式未知,只能夠利用問題的輸入值和輸出值進行求解,因此,黑盒優(yōu)化算法的發(fā)展對于優(yōu)化屬于黑盒范疇的真實問題變得尤為重要。

黑盒問題的自身性質(zhì)決定了設(shè)計高質(zhì)量解的黑盒優(yōu)化算法十分困難。早期多用數(shù)學推理的零階方法[1]來解決黑盒問題,如單純形法和擬牛頓法;但是,這些算法極度依賴問題數(shù)學性質(zhì),因此難以解決日益復雜的黑盒問題。適用范圍更加廣泛的群智能啟發(fā)式算法,如遺傳算法(GA)[2]、粒子群優(yōu)化算法(PSO)[3]等逐漸成為研究熱點,然而這些算法需要對復雜的真實問題進行多次評估,代價昂貴。分布估計算法[4]采用基于搜索空間的進化算法,具有較強的全局搜索能力;然而,該算法容易對解空間分布產(chǎn)生過擬合現(xiàn)象,限制解的多樣性以及算法的搜索能力,因此,設(shè)計一種所需評估次數(shù)更少同時種群多樣性更高的算法對有效解決黑盒問題具有重要意義。

本文中提出一種新的黑盒優(yōu)化算法, 即結(jié)合近鄰傳播聚類的世界生成神經(jīng)網(wǎng)絡(luò)優(yōu)化器(AP-WGNN)。 AP-WGNN由2個神經(jīng)網(wǎng)絡(luò)(世界模型、 采樣生成器)和近鄰傳播聚類(affinity propagation clustering, AP)[5]的選擇策略組成, 通過對問題景觀結(jié)構(gòu)進行建模并增加種群多樣性, 使得該算法能夠以更少的評估次數(shù)發(fā)現(xiàn)最優(yōu)解所在的最優(yōu)分布。 AP-WGNN首先通過2個神經(jīng)網(wǎng)絡(luò)的協(xié)同優(yōu)化驅(qū)動生成候選解, 增強了對問題景觀的學習, 即使用世界模型轉(zhuǎn)換樣本, 并基于當前的世界模型通過采樣生成器生成解決方案, 減少對真實問題的評估。 然后通過將聚類間排序和聚類內(nèi)排序相結(jié)合的AP的選擇算法提高了種群多樣性, 提高AP-WGNN找到最優(yōu)解所在最優(yōu)分布的概率。 為了驗證AP-WGNN的優(yōu)化性能, 本文中分別在多個維度上對比AP-WGNN和其他5種基線算法的優(yōu)化結(jié)果, 從不同角度驗證AP-WGNN的精度和穩(wěn)定性。

1 協(xié)同學習神經(jīng)網(wǎng)絡(luò)

AP-WGNN由世界模型、 采樣生成器和基于AP的選擇策略組成。 歷史解集由均勻分布隨機初始化。 在每次迭代中, 世界模型通過歷史解集及其適應(yīng)度的不斷訓練來逼近真實問題景觀。 本文中適應(yīng)度表示解的質(zhì)量優(yōu)劣。 適應(yīng)度越低, 質(zhì)量越好。 與此同時, 根據(jù)當前的世界模型, 對采樣生成器進行訓練, 以產(chǎn)生更好的解。 通過AP、 簇間排序、 簇內(nèi)排序的共同合作, 得到更好的解, 組成新的歷史解集。 AP-WGNN的框架和流程如圖1、 2所示。

圖1 結(jié)合近鄰傳播聚類的世界生成神經(jīng)網(wǎng)絡(luò)優(yōu)化器框架

圖2 結(jié)合近鄰傳播聚類的世界生成神經(jīng)網(wǎng)絡(luò)優(yōu)化器流程圖

1.1 世界模型

由于黑盒問題的評估代價是昂貴的,因此在不了解問題景觀的情況下進行優(yōu)化會顯著增加評估成本。為了解決這個問題,世界模型被設(shè)計為一個動態(tài)代理模型[6],通過持續(xù)訓練使其近似真實的黑盒問題景觀。同時,世界模型通過減少真實適應(yīng)度和代理適應(yīng)度之間的誤差,使生成的解更接近真實解。為了使訓練過程穩(wěn)定,加快訓練速度,AP-WGNN采用Z分值(Z-score)歸一化方法[7]將解的不同維度都縮放至標準化區(qū)域。Z-score公式為

xscale=(xhis-μ)/σ,

(1)

xunscale=xgσ+μ,

(2)

式中:xscale為歷史解集的標準化形式;xhis為歷史解集;μ和σ分別為xhis的均值和標準差;xunscale為采樣生成器G的輸出xg的逆標準化。在對xhis進行Z-score歸一化后,xscale被用作世界模型的輸入。經(jīng)過多次訓練迭代后,可以獲得近似真實的黑盒問題景觀的代理模型。世界模型W損失函數(shù)表達式為

(3)

式中:K為歷史解集的規(guī)模;fhis,i為歷史最優(yōu)解集fhis中的第i個元素,表示xhis,i的適應(yīng)度;W(xscale,i)表示歸一化后的最優(yōu)解集xscale,i通過世界模型W擬合的適應(yīng)度。 當世界模型進行訓練時, 神經(jīng)網(wǎng)絡(luò)的損失函數(shù)逐漸趨于0, 意味著世界模型逐漸學會了該黑盒問題, 輸出的擬合適應(yīng)度逐漸接近真實的適應(yīng)度。

1.2 采樣生成器

世界模型可以學習由xhis表示的問題的局部結(jié)構(gòu),以近似地描述問題的情況。采樣生成器G通過世界模型生成新的適應(yīng)度更好的解xg。采樣生成器G的損失函數(shù)表達式為

(4)

式中:m為生成解集的規(guī)模;η為正態(tài)分布,代表輸入到采樣生成器G的隨機噪聲,產(chǎn)生xg。隨著采樣生成器G的訓練,損失函數(shù)的值逐漸趨于0,意味著采樣生成器的適應(yīng)度逐漸趨于0,因此,采樣生成器將生成具有更好適應(yīng)度的解。

AP-WGNN通過世界模型增強了對問題的先驗知識的獲取,并通過采樣生成器提高了算法的挖掘能力,使其能夠在世界模型學習到的問題景觀中找到更好的解。

2 基于AP的選擇策略

2.1 AP

AP可以在不指定聚類數(shù)量的情況下自動將解集分為多個簇,增加了搜索的多樣性,避免增加額外的超參數(shù),因此,AP-WGNN可以避免過早地陷入局部最優(yōu),并且所選方案具有低相似度,可以使AP-WGNN以更高的概率找到全局最優(yōu)。AP通過歐氏距離計算相似度矩陣,從而更新責任矩陣和可用性矩陣。經(jīng)過AP,歷史解和生成解的混合解集xmix被分為p個簇,每個簇中的解的數(shù)量為q,p和q在優(yōu)化過程中由AP產(chǎn)生并自適應(yīng)變化,表達式為

(5)

式中:xcdata,i是第i個簇中的解;xcenter,i是xcenter的第i個元素,代表簇的中心樣本。

2.2 簇間排序選擇策略

AP將xmix劃分成具有高度多樣性的多個簇。這些簇根據(jù)簇中所有解的平均適應(yīng)度進行排序,作為這個簇的權(quán)重。權(quán)重較小的簇表示該簇中的解質(zhì)量較高。每個簇的權(quán)重公式為

(6)

式中:Vcenter,i為第i個簇的平均適應(yīng)度;fcdata, j為第i個簇中第j個解的適應(yīng)度。通過簇間的排序選擇,選出平均適應(yīng)度較高的簇,幫助AP-WGNN篩選出質(zhì)量更優(yōu)且多樣化的解。

2.3 簇內(nèi)排序選擇策略

簇間排序選擇后,對同一簇中的解分別按其適應(yīng)度進行排序。AP-WGNN通過從每個簇中選擇前t個解,形成一個新的歷史解決方案集xhis。選擇方法表達式為

(7)

式中t=[(K/p)],i=1,2,…,p。如果被選擇的解的總數(shù)少于K,AP-WGNN將從剩余未被選擇過的解中選擇,直到新的歷史解集中解的數(shù)量等于K。

3 數(shù)值實驗

對AP-WGNN進行數(shù)值分析,所有實驗使用的測試問題從比較連續(xù)優(yōu)化器平臺(platform for comparing continuous optimizers, COCO)平臺[8]選擇,包括Sphere、 Ellipsoidal、 DifferentPower等12個黑盒基準問題(具體如圖3所示)。

3.1 優(yōu)化過程可視化

圖3所示為12個COCO平臺上的基準黑盒問題的三維景觀和在二維等高線圖上AP-WGNN的最優(yōu)點的尋優(yōu)軌跡。從圖中可以看出,如果問題是單峰的,如Sphere和Different Powers,AP-WGNN會逐漸找到全局最優(yōu);當問題為多峰時,如Buche-Rastrigin,AP-WGNN將首先通過挖掘能力找到局部最優(yōu)區(qū)域,然后,通過探索能力跳出局部最優(yōu),找到全局最優(yōu)區(qū)域。由此可以看出,AP-WGNN通過神經(jīng)網(wǎng)絡(luò)和AP選擇策略,不僅提高了挖掘能力,也提高了探索能力。

3.2 性能分析

以下采用5種啟發(fā)式優(yōu)化器作為對比算法驗證AP-WGNN的優(yōu)化性能。在基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化算法中,將顯示梯度估計算法(EGL)[9]作為對比算法。在傳統(tǒng)啟發(fā)式優(yōu)化算法中,分別選擇Nelder-Mead(NM)[10]、 BFGS[11]、 PSO[12]和GA[13]4種具有代表性的算法。在實驗中,從COCO平臺中選取上述12個包含不同屬性的具有挑戰(zhàn)性的黑盒基準函數(shù)。所有基準函數(shù)在2、 3、 5維上運行15次。在所有維度中,函數(shù)評估次數(shù)的最大值設(shè)置為50 000。對于實驗中使用的基準函數(shù),適應(yīng)度越小表明方法的性能越好。

圖4所示為AP-WGNN、 GA、 PSO、 EGL、 NM和BFGS算法在不同2維黑盒基準函數(shù)的收斂曲線。 可以看出, AP-WGNN在所有基準函數(shù)的測試上都具有良好的性能, 在Sphere、 Linear Slope、 Different Powers等單峰問題上,AP-WGNN的優(yōu)化效果與其他算法的相當,性能基本相近。

當算法具有較強的挖掘能力時,對于單峰問題可以很容易地找到較好的解,然而,當面對多峰病態(tài)、全局趨勢不明顯的問題時,如Rastrigin、 non-separable Rastrigin,算法不僅需要具備挖掘能力,還需要有足夠的探索能力,才能從多個局部最優(yōu)區(qū)域中找到最好的解。AP-WGNN在這2個基準函數(shù)測試上的性能最好,說明它具有比其他算法更好的探索能力,原因是AP-WGNN對問題的景觀有足夠的了解,從而強化了挖掘能力,同時使用AP選擇策略選擇多樣性的解可以提高算法的探索能力。

特別是針對Gallagher’s Gaussian 21-hi 和Gallagher’s Gaussian 101-me問題, 要尋找由許多位置和高度不相關(guān)的最優(yōu)解組成的局部最優(yōu)區(qū)域?qū)λ惴ǜ芯咛魬?zhàn)性, 更能判斷算法的全局探索能力的強弱。 無論是EGL, 還是傳統(tǒng)的啟發(fā)式算法, 即使給出充分的求解次數(shù), 在這2個問題上都只能找到局部最優(yōu)。 AP-WGNN得益于神經(jīng)網(wǎng)絡(luò)的擬合能力及AP選擇策略的探索能力, 其優(yōu)化性能遠優(yōu)于其他算法, 且需要的評估次數(shù)更少。 為了全面分析在有限的函數(shù)評估次數(shù)下可以達到的最優(yōu)精度, 表1給出了6種算法在2、 3、 5維黑盒基準函數(shù)不同精度下的平均適應(yīng)度。 從表中可以看出, 隨著維數(shù)的增加, AP-WGNN的平均適應(yīng)度的排名有所下降, 但下降幅度明顯小于其他算法, AP-WGNN仍然排名第一。 無論在哪個維度上, BFGS和NM的排名始終較低。 同時, 精度要求越高, 所有算法的排名會降低, 但AP-WGNN的排名下降幅度遠遠小于其他5種算法的, 表明AP-WGNN在不同精度要求時的表現(xiàn)都是最好的。

表1 不同算法在不同維度黑盒基準函數(shù)的平均適應(yīng)度

表2給出了不同算法在2、 3、 5維的12個黑盒基準函數(shù)上的t檢驗結(jié)果。 顯著性水平設(shè)置為0.05。 結(jié)果表明, AP-WGNN在多個維度上總體性能都要優(yōu)于其他算法。 當維數(shù)為2時, PSO的性能優(yōu)于AP-WGNN的, 但隨著維數(shù)的增加, PSO的性能迅速下降, 說明AP-WGNN在維數(shù)為3、 5時具有更好的適應(yīng)性。

表2 不同算法在不同維度黑盒基準上的t檢驗結(jié)果

3.3 參數(shù)分析

圖5所示為AP-WGNN的世界模型的訓練迭代次數(shù)Nw和采樣生成器的訓練迭代次數(shù)Ng的超參數(shù)分析。Nw影響世界模型W的訓練頻率,Ng則影響采樣生成器G的訓練頻率。 AP-WGNN在2個5維基準函數(shù)上重復運行15次, 最大函數(shù)評估次數(shù)為10 000。 從圖中可以看出: 當Nw和Ng設(shè)置為相似值時, AP-WGNN的性能更好; 當Nw較小時, 無論Ng多大, AP-WGNN的性能都很差, 說明G的訓練只有在W被充分建模時才有效, 因為G是根據(jù)當前W生成樣本的; 當Ng和Nw較小時, AP-WGNN在2個基準函數(shù)的性能差異較大, 說明在此設(shè)置下AP-WGNN的性能是不穩(wěn)定的, 因此, 建議將Nw和Ng設(shè)置為[50,100]。

4 結(jié)語

本文中提出了一種新的協(xié)同學習神經(jīng)網(wǎng)絡(luò)黑盒優(yōu)化器AP-WGNN,用以解決復雜的黑盒優(yōu)化問題。在AP-WGNN中,世界模型和生成神經(jīng)網(wǎng)絡(luò)被協(xié)同訓練以產(chǎn)生真實的、更好的解;然后,AP將歷史解集和生成解集的混合集劃分為多個簇,同時,根據(jù)簇的權(quán)重對不同的簇進行排序, 并對同一簇中的解按適

應(yīng)度大小進行排序,被選擇的解將組成新的歷史解集;最后,通過綜合實驗驗證了所提方法的有效性。為了進一步提高該方法的效率,今后將采取更好的啟動策略,如改進初始化策略,比較不同建模方法對算法的影響。此外,未來還將繼續(xù)研究該方法在高維問題上的實際應(yīng)用。