結合近鄰傳播聚類的世界生成神經網絡優化器

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

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

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

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

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

1 協同學習神經網絡

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

圖1 結合近鄰傳播聚類的世界生成神經網絡優化器框架

圖2 結合近鄰傳播聚類的世界生成神經網絡優化器流程圖

1.1 世界模型

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

xscale=(xhis-μ)/σ,

(1)

xunscale=xgσ+μ,

(2)

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

(3)

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

1.2 采樣生成器

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

(4)

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

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

2 基于AP的選擇策略

2.1 AP

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

(5)

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

2.2 簇間排序選擇策略

AP將xmix劃分成具有高度多樣性的多個簇。這些簇根據簇中所有解的平均適應度進行排序,作為這個簇的權重。權重較小的簇表示該簇中的解質量較高。每個簇的權重公式為

(6)

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

2.3 簇內排序選擇策略

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

(7)

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

3 數值實驗

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

3.1 優化過程可視化

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

3.2 性能分析

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

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

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

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

表1 不同算法在不同維度黑盒基準函數的平均適應度

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

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

3.3 參數分析

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

4 結語

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

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