全局與局部模型交替輔助的差分進化算法

于成龍，付國霞，孫超利，張國晨

（太原科技大學計算機科學與技術(shù)學院，太原 030024）

0 概述

隨著科學技術(shù)的快速發(fā)展，工農(nóng)業(yè)生產(chǎn)、國防建設(shè)、醫(yī)療衛(wèi)生、人民生活等各個領(lǐng)域?qū)こ坍a(chǎn)品性能的要求不斷提高，工程優(yōu)化問題也變得越來越復雜。元啟發(fā)式優(yōu)化算法（包括進化算法和群智能優(yōu)化算法）相比于傳統(tǒng)的單點迭代算法對目標函數(shù)無連續(xù)可微的要求，具有更大的概率找到全局最優(yōu)解，且不一定需要有顯式的目標函數(shù)公式，在大型電力系統(tǒng)［1-2］、天線設(shè)計［3-4］、航空航天及汽車設(shè)計［5-6］等科學研究和工程優(yōu)化中具有廣泛應用。然而，元啟發(fā)式優(yōu)化算法在獲得最優(yōu)解之前通常需要進行多次目標函數(shù)評價。因此，在目標函數(shù)計算費時的情況下，很難應用元啟發(fā)式優(yōu)化算法來搜索問題的最優(yōu)設(shè)計方案［7］?；跉v史數(shù)據(jù)建立代理模型用來輔助元啟發(fā)式優(yōu)化算法，在評價次數(shù)有限的情況下搜索全局最優(yōu)解是目前常用的求解計算費時問題的優(yōu)化方法［8-9］。相比于計算費時的原優(yōu)化問題的目標函數(shù)評價，訓練代理模型所需計算時間成本是低廉的，主要包括多項式回 歸（Polynomial Regression，PR）［10］、徑向基函數(shù)（Radical Basis Function，RBF）［11］、高斯過程（Gaussian Process，GP）［12］、人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network，ANN）［13-14］和支持向量回歸（Support Vector Regression，SVR）［15］等常見的代理模型。

元啟發(fā)式優(yōu)化算法中根據(jù)模型的用途可以將代理模型分為全局代理模型和局部代理模型。在通常情況下，全局代理模型用于平滑原問題的局部最優(yōu)解，并引導搜索算法快速定位到最優(yōu)解附近。LIU等［16］提出一個求解中等規(guī)模費時優(yōu)化問題的高斯過程輔助的進化算法。SCHNEIDER 等［17］采用高斯過程模型的貝葉斯優(yōu)化以改進具有許多自由度的光學結(jié)構(gòu)。TIAN 等［12］提出一個高斯過程輔助的進化算法（MGP-SLPSO），采用多目標填充準則的方式選擇真實評價的個體。YU 等［18］提出一種最優(yōu)重啟策略代理輔助的社會學習粒子群優(yōu)化算法（GORSSSLPSO），集成了重啟策略和全局RBF 代理模型以提供功能強大的優(yōu)化器來解決計算耗時的問題。局部代理模型則用于較好地擬合原問題在某一個區(qū)域中的函數(shù)形狀，從而輔助算法在該區(qū)域中進行搜索，從而提高最優(yōu)解精度。LIM 等［7］使用集成和平滑的局部代理模型同時進行局部搜索，共同生成可靠的適應值預測和搜索改進策略。適應值繼承是一種特殊的局部代理模型，SUN 等［19-20］基于同一代兄弟個體和父代個體提出一種新的適應值估計策略。全局和局部混合代理模型相比于使用單全局代理模型或者單局部代理模型在輔助優(yōu)化算法搜索最優(yōu)解時具有較好的搜索性能。WANG 等［21］提出基于主動學習的代理模型輔助的粒子群優(yōu)化算法（CAL-SAPSO），結(jié)合全局和局部代理模型管理策略進行優(yōu)化。SUN等［11］提出代理模型輔助的協(xié)同優(yōu)化算法，利用RBF全局代理模型輔助社會學習微粒群算法進行全局最優(yōu)解的探索，同時利用適應值估計策略輔助的微粒群算法進行局部開采，從而實現(xiàn)對高維計算費時優(yōu)化問題的求解。YU 等［22］提出代理模型輔助的分層粒子群優(yōu)化算法（SHPSO），與代理模型輔助的協(xié)同優(yōu)化算法不同，在SHPSO 中，社會學習粒子群優(yōu)化用于進行局部空間的開采，而粒子群優(yōu)化用于在全局空間中進行探索，從而提高全局最優(yōu)解的尋找性能。LI 等［23］提出一種求解高維費時問題的代理輔助的多種群優(yōu)化算法（SAMSO），全局和局部代理模型分別輔助兩個種群進化，同時兩個種群通過相互學習來提高算法的搜索性能。LIAO 等［24］利用所有歷史樣本訓練全局代理模型，采用最優(yōu)的若干樣本訓練局部代理模型，并通過多任務優(yōu)化方法搜索兩個模型的最優(yōu)解。

混合代理模型輔助的元啟發(fā)式優(yōu)化算法能夠利用不同模型的優(yōu)勢，相比于單代理模型能夠更好地輔助優(yōu)化算法在評價次數(shù)或者計算資源有限的情況下找到較優(yōu)解。本文基于已有的歷史數(shù)據(jù)，通過不同的樣本選擇策略建立全局代理模型和局部代理模型。對全局代理模型和局部代理模型進行最優(yōu)解的交互搜索，通過對全局代理模型的搜索實現(xiàn)對原問題最優(yōu)解的探索，模型最優(yōu)解根據(jù)真實計算用于更新局部代理模型，使其能夠更好地擬合目前最優(yōu)解附近的局部區(qū)域，通過對局部代理模型最優(yōu)解的搜索提高獲得更優(yōu)解的概率。

1 相關(guān)技術(shù)

1.1 徑向基函數(shù)網(wǎng)絡(luò)

徑向基函數(shù)網(wǎng)絡(luò)（Radial Basis Function Network，RBFN）是一種包含輸入層、隱藏層和輸出層共三層的神經(jīng)網(wǎng)絡(luò)。RBFN 作為代理模型在輔助優(yōu)化算法中具有較好的擬合效果，且其擬合效果對于問題維度的增加相對不敏感［25-26］。給定樣本庫{(xi，f(xi))，i=1，2，…，Na}，Na表示樣本庫中初始樣本數(shù)量，RBFN 模型可表示如下：

其中：ω=為RBF 網(wǎng)絡(luò)的輸出權(quán)重；Nc為隱含層節(jié)點數(shù)；φ（·）為徑向基核函數(shù)；ci為第i個隱含節(jié)點徑向基函數(shù)的中心。常見的核函數(shù)有高斯核、線性核、多重二次曲面核、立方核等［27］。本文算法中徑向基核函數(shù)采用立方核函數(shù)。

1.2 差分進化算法

差分進化（Differential Evolution，DE）算法在許多優(yōu)化問題上已被證明是一個簡單有效的進化算法［28-29］，遵循進化算法的一般流程，即首先在問題決策空間中產(chǎn)生一個初始化種群{x1(t)，x2(t)，…，xN()t}，其中，t=0，N為種群大小，xi=(xi1，xi2，…，xiD)表示第i個個體，D表示問題的維度。然后通過變異、交叉和選擇操作找到問題的最優(yōu)解。在DE 算法中，常見的變異策略有DE/rand/1、DE/current-to-best/1和DE/best/1等［30］。本文算法中采用標準的DE/rand/1變異策略，即對于每一代t，隨機選擇3 個不同于當前個體i的個體，并通過以下公式得到變異后的向量vi(t)：

其中：r0、r1和r2為[1，N]中3 個不同的隨機數(shù)；和表示當前種群中不同于個體xi的3 個個體；Fi稱為DE 的變異因子。

每個個體根據(jù)一定的概率在各個維度上進行交叉操作，通過式（3）的交叉方法得到交叉后的向量ui(t+1)=(ui1(t)，ui2(t)，…，uiD(t))。uij(t+1)的計算公式如下：

其中：CRj∈[0，1]為交叉概率；jrandint為［1，D］中隨機產(chǎn)生的一個整數(shù)。對每個向量ui(t+1)計算目標函數(shù)值，并與其父代個體進行適應值的對比，保留較優(yōu)的個體作為下一代的父代個體，即：

2 全局與局部代理模型交替輔助的DE 算法

2.1 算法整體流程

算法1 給出了全局與局部代理模型交替輔助的差分進化算法AGL-DE 的偽代碼。首先，通過拉丁超立方體產(chǎn)生一定數(shù)量的初始樣本，對其使用真實的目標函數(shù)評價并將其存入數(shù)據(jù)集Arc 中。基于這些真實評價的個體確定當前最優(yōu)解，記為gbest。然后，若沒有達到停止條件，即達到最大的評價次數(shù)，則循環(huán)執(zhí)行以下操作：交替建立全局代理模型和局部代理模型并對模型進行最優(yōu)解搜索，搜索到的最優(yōu)解進行真實目標函數(shù)的計算，存入數(shù)據(jù)集Arc 中，并更新最優(yōu)解gbest。最后，詳細介紹全局代理模型和局部代理模型的訓練（步驟6 和步驟10）及其優(yōu)化。

算法1AGL-DE 算法

2.2 全局代理模型的訓練與優(yōu)化

在代理模型輔助的進化算法中，為了保證算法的收斂性，通常選用適應值最優(yōu)的若干個樣本來訓練模型，但是這樣會導致算法很快陷入局部最優(yōu)，使得算法性能下降。本文選擇具有代表性的樣本建立全局代理模型，并通過在決策空間對全局代理模型最優(yōu)解的搜索提高算法探索能力，防止算法陷入局部最優(yōu)。文獻［31］表明全局代理模型并非一定需要與原函數(shù)精確擬合，其主要作用在于平滑掉局部最優(yōu)，加速定位到全局最優(yōu)解附近。為此，本文通過計算每個樣本xi和其最近鄰個體之間的擁擠度（記為C(xi)）來選擇全局代理模型的訓練樣本。計算方式為對Arc 中個體按照目標函數(shù)值從小到大排序，對任意個體xi，其擁擠度為相鄰兩個個體的目標函數(shù)之差。顯然，擁擠度越大，說明該個體和其他個體之間的目標函數(shù)差值越大，擁擠度越小，說明和該個體的目標函數(shù)的相似度較大。為了更好地訓練全局代理模型，選擇擁擠度大且考慮估值小的樣本個體來訓練模型。通過-max 的方式將最大化擁擠度轉(zhuǎn)換成最小化問題，根據(jù)個體擁擠度和其適應值進行非支配排序，并從非支配排序后的第一層開始選擇該層的所有樣本放入訓練樣集，直到當加入第k層的所有樣本選擇出的樣本數(shù)大于預定樣本數(shù)時，在第k層隨機選擇樣本直到達到預定樣本數(shù)，并利用選擇出的所有樣本訓練全局代理模型。使用差分進化算法搜索模型的最優(yōu)解，并對其進行真實的目標函數(shù)計算。需要注意的是對模型進行最優(yōu)解搜索時，初始化種群中的個體來自：1）使用拉丁超立方體采樣技術(shù)得到的初始個體；2）數(shù)據(jù)集Arc 中適應值較優(yōu)的若干個體。初始化種群中增加Arc 中適應值較優(yōu)的個體是為了加快模型最優(yōu)解的搜索速度。將經(jīng)過真實目標函數(shù)計算的模型最優(yōu)解存入樣本庫Arc 中并更新目前找到的最優(yōu)解gbest。算法2 為算法1 中訓練全局代理模型的偽代碼。

算法2全局代理模型訓練算法

2.3 局部代理模型的訓練與優(yōu)化

為快速找到更優(yōu)解，利用數(shù)據(jù)集Arc 中的若干最優(yōu)解建立局部代理模型。算法3 給出了訓練局部代理模型的偽代碼。與訓練全局代理模型類似，從數(shù)據(jù)集Arc 中選擇一定數(shù)量的訓練數(shù)據(jù)訓練局部代理模型。利用差分進化算法進行局部代理模型最優(yōu)解的搜索。對找到的局部代理模型最優(yōu)解使用真實的目標函數(shù)進行計算，存入數(shù)據(jù)集Arc 中并更新目前計算得到的最優(yōu)解。

算法3局部代理模型訓練算法

3 實驗設(shè)計與結(jié)果分析

為評估AGL-DE 算法的性能，在7 個單目標基準問題［7，32］上進行測試，這7 個基準問題的函數(shù)名稱、全局最優(yōu)值和函數(shù)特征如表1 所示。本節(jié)首先給出了AGL-DE 算法的參數(shù)設(shè)置，然后將其與近年來提出的求解費時問題的優(yōu)化算法在測試函數(shù)上進行結(jié)果比較，最后對算法框架、參數(shù)進行敏感性分析。所有算法均獨立運行25 次，并通過顯著性水平為0.05 的帶有Bonferroni校驗的Wilcoxon 秩和檢驗方法［33］對25 次獨立運行結(jié)果進行顯著性統(tǒng)計檢驗。

表1 基準函數(shù)特性Table 1 Characteristics of the benchmark functions

3.1 參數(shù)設(shè)置

在AGL-DE 算法中，不同的代理模型均可作為全局與局部代理模型，本文采用RBF 代理模型，主要原因在于RBF 代理模型對于高維問題具有較好的擬合效果［22］。訓練RBF 代理模型的最小樣本數(shù)為2×D。實驗中初始產(chǎn)生的樣本數(shù)為2×D，隨著評價次數(shù)增多，Arc 中真實計算的樣本數(shù)增多。若樣本過多，則訓練模型的速度會減慢，因此在實驗中設(shè)定訓練模型的最大樣本數(shù)為5×D，在每次模型訓練時訓練模型的樣本數(shù)為［2×D，5×D］中的一個隨機整數(shù)Nt。需要注意的是若產(chǎn)生的隨機整數(shù)Nt大于當前已有樣本數(shù)，則Arc 中所有樣本均參與模型的訓練，否則從Arc 中隨機挑選Nt個數(shù)據(jù)進行模型訓練。對于模型最優(yōu)解的搜索，初始種群大小設(shè)置為50，從Arc中選擇的最優(yōu)解個數(shù)為［40，50］中的一個隨機整數(shù)，剩余的初始解使用拉丁超立方體方法產(chǎn)生。迭代次數(shù)設(shè)置為［D，4×D］中產(chǎn)生的一個隨機整數(shù)。使用DE/rand/1 作為變異策略，二項式交叉作為DE 的交叉策略，變異因子設(shè)置為0.5，交叉概率設(shè)置為0.3。在實驗對比中，所有算法的終止條件均為達到最大的真實評價次數(shù)，在10、20 和30 維的低維測試問題上算法評價11×D次，在50 和100 維的高維測試問題上算法評價1 000 次。

3.2 與其他算法的實驗結(jié)果對比分析

表2 給出了AGL-DE 與GORS-SSLPSO［18］、CAL-SAPSO［21］、DDEA-SE［34］、SHPSO［22］算法在低維測試問題上的統(tǒng)計結(jié)果，其中，符號“+”、“-”和“≈”分別表示AGL-DE 算法相較于其他算法具有顯著性優(yōu)、顯著性差和沒有顯著性差異，加粗數(shù)據(jù)表示該數(shù)據(jù)對應的算法找到的解是所有算法中最優(yōu)的，最后一行的數(shù)字分別表示AGL-DE 算法相較于其他算法具有顯著性優(yōu)的個數(shù)、顯著性差的個數(shù)和沒有顯著性差異的個數(shù)。SHSPO 算法在低維問題上只涉及了30 維，因此僅對SHPSO 算法在30 維問題上的結(jié)果進行比較。從表2 可以看出，除了F5 測試問題以外，AGL-DE 算法在F1～F4 這4 個測試問題上基本優(yōu)于其他算法，雖然GORS-SSLPSO 算法在F4 上的結(jié)果略好，但是與AGL-DE 算法并沒有顯著性差異。

表2 AGL-DE 與GORS-SSLPSO、CAL-SAPSO、DDEA-SE、SHPSO 算法在低維測試問題上的統(tǒng)計結(jié)果Table 2 Statistical results of AGL-DE and GORS-SSLPSO，CAL-SAPSO，DDEA-SE，SHPSO algorithms on low-dimensional test problems

表3 給出了AGL-DE 與GORS-SSLPSO［18］、MGP-SLPSO［12］、DDEA-SE［34］、SHPSO［22］、SAMSO［23］算法在高維測試問題上的統(tǒng)計結(jié)果。從表3 中可以看 出，AGL-DE 算法相比于 GORS-SSLPSO、MDP-SLPSO、DDEA-SE、SHPSO、SAMSO 算法在高維問題上獲得了13/14、8/14、13/14、10/14 和9/14 的更好解。此外，還可以看出AGL-DE 算法在5/7 個100 維測試問題上獲得了比其他算法更優(yōu)的結(jié)果，表明AGL-DE 算法對于高維問題具有較好的求解效果。

表3 AGL-DE 與GORS-SSLPSO、MGP-SLPSO、DDEA-SE、SHPSO、SAMSO 算法在高維測試問題上的統(tǒng)計結(jié)果Table 3 Statistical results of AGL-DE and GORS-SSLPSO，MGP-SLPSO，DDEA-SE，SHPSO，SAMSO algorithms on high-dimensional test problems

為更好地分析算法的收斂性能，圖1、圖2 分別給出了AGL-DE 算法和其他算法在低維和高維測試問題上的函數(shù)收斂曲線圖，橫坐標代表真實適應值的評估次數(shù)，記為T，為了能夠更加明顯地觀察收斂曲線圖的變化情況，縱坐標用25 次獨立運行得到的適應值的中值的對數(shù)表示，記為lg（F（xT）），其中xT為算法第T次真實適應值評估下找到的最優(yōu)解，F(xiàn)（xT）為xT對應的目標函數(shù)值。

圖1 AGL-DE 與GORS-SSLPSO、CAL-SAPSO、SHPSO 算法在低維測試問題上的函數(shù)收斂曲線圖Fig.1 Function convergence curves of AGL-DE and GORS-SSLPSO，CAL-SAPSO，SHPSO algorithms on low-dimensional test problems

圖2 AGL-DE 與GORS-SSLPSO、MGP-SLPSO、SHPSO、SAMSO 算法在高維測試問題上的函數(shù)收斂曲線圖Fig.2 Function convergence curves of AGL-DE and GORS-SSLPSO，MGP-SLPSO，SHPSO，SAMSO algorithms on high-dimensional test problems

由于F6 測試問題的適應值可能是負值，因此在該測試問題的收斂曲線圖上沒有對適應值進行取對數(shù)操作。需要注意的是，DDEA-SE 算法是一種基于數(shù)據(jù)驅(qū)動的離線優(yōu)化算法，在優(yōu)化的過程中不會產(chǎn)生需要真實適應度評估的個體，故沒有給出其收斂曲線圖。

從圖1 可以看出，AGL-DE 在F1～F4 測試問題上都比其他算法具有更快的收斂速度，在低維的單模態(tài)和多模態(tài)問題上都展現(xiàn)了良好的性能。對于高維優(yōu)化問題，從圖2 可以看出，本文所提AGL-DE 算法在大部分優(yōu)化問題上具有較快的收斂速度。但是從圖2 也可以看出其容易陷入局部最優(yōu)，如50 維的F2、F3、F5 和F7 測試問題，在搜索算法到達一定程度后不再繼續(xù)下降。由此分析其早熟收斂的主要原因在于初始樣本的選擇。從Arc 中選擇若干最優(yōu)解作為DE 的初始種群，當這些解的差別較小時，初始種群的多樣性較差。這些解雖然能夠引導算法快速收斂到某一個解，但是很難跳出局部最優(yōu)，從而導致了算法的早熟收斂。

3.3 全局與局部代理模型有效性分析

為驗證全局與局部代理模型交替輔助的有效性，將其與僅使用全局代理模型輔助進化算法（G-DE）和僅使用局部代理模型輔助進化算法（L-DE）進行實驗結(jié)果比較，在實驗過程中其他參數(shù)設(shè)置與3.1 節(jié)的設(shè)置相同。表4 給出了AGL-DE、G-DE 和L-DE 算法在10 維、20 維和50 維的F1、F3 和F4 測試問題上的統(tǒng)計結(jié)果。從統(tǒng)計結(jié)果上來看：AGL-DE 比G-DE 顯著性好3 個，顯著性差1 個，無顯著性差異5 個；AGL-DE 比L-DE 顯著性好3 個，顯著性差2 個，無顯著性差異4 個。統(tǒng)計結(jié)果表明：全局代理模型和局部代理模型交替輔助差分進化算法比單一模型輔助差分進化算法的效果好。

表4 AGL-DE 與G-DE、L-DE 算法在F1、F3 和F4 測試問題上的統(tǒng)計結(jié)果Table 4 Statistical results of AGL-DE and G-DE，L-DE algorithms on F1，F(xiàn)3 and F4 test problems

3.4 參數(shù)敏感性分析

為驗證在一定區(qū)間內(nèi)隨機產(chǎn)生的訓練集樣本數(shù)Nt、種群迭代次數(shù)iter 和從Arc 中選擇的初始樣本數(shù)Na的有效性，在不改變其他參數(shù)設(shè)置的情況下，與固定這3 個參數(shù)的3 種策略進行比較，分別將它們固定為區(qū)間內(nèi)的最小值、中值和最大值，即min-values、med-values 和max-values，具體參數(shù)設(shè)置如表5 所示。在這3 種策略上對50 維和100 維的F1、F2、F4 和F6 測試問題進行測試，表6 給出了AGL-DE 算法和這3 種策略的對比統(tǒng)計結(jié)果，可以看出在一定區(qū)間內(nèi)隨機生成參數(shù)的AGL-DE 算法要比單純固定這些參數(shù)的3 種策略具有更好的性能。

表5 3 種策略的參數(shù)設(shè)置Table 5 Parameter settings of three strategies

表6 AGL-DE 算法與min-values、med-values、max-values策略在F1、F2、F4 和F6 測試問題上的統(tǒng)計結(jié)果Table 6 Statistical results of AGL-DE algorithm and min-values，med-values，max-values strategies on F1，F(xiàn)2，F(xiàn)4 and F6 test problems

4 結(jié)束語

本文提出一種全局與局部代理模型交替輔助的差分進化算法，通過對全局代理模型和局部代理模型最優(yōu)解的交替搜索來更新數(shù)據(jù)集以及原費時優(yōu)化問題的最優(yōu)解，從而在計算資源有限的情況下獲得問題的更優(yōu)解。實驗結(jié)果表明，相比于近年來提出的求解費時問題的優(yōu)化算法，該算法在低維和高維測試問題上均獲得了較好的尋優(yōu)效果，然而在某些高維測試問題上容易陷入局部最優(yōu)，導致早熟收斂。因此在下一步工作中將考慮增強算法多樣性，以便跳出局部最優(yōu)，從而在計算資源有限的情況下找到目標函數(shù)的更優(yōu)解。