高計(jì)算代價動態(tài)優(yōu)化問題的代理模型輔助粒子群優(yōu)化算法

張 勇，胡江濤

(中國礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221118)

在實(shí)際生產(chǎn)生活中存在許多復(fù)雜優(yōu)化問題，其目標(biāo)函數(shù)或約束隨著時間發(fā)生變化，稱其為動態(tài)優(yōu)化問題(dynamic optimization problems, DOP)[1-3]。進(jìn)化算法是模擬自然界生物進(jìn)化機(jī)制提出的一類啟發(fā)式智能優(yōu)化技術(shù)[4]。由于不依賴問題特性、具有并行搜索機(jī)制等優(yōu)點(diǎn)，目前進(jìn)化優(yōu)化算法已成為解決復(fù)雜動態(tài)優(yōu)化問題的一種有效方法[5-7]。針對動態(tài)優(yōu)化問題，尤其是動態(tài)多目標(biāo)優(yōu)化問題，學(xué)者們已經(jīng)提出了諸多進(jìn)化優(yōu)化算法。如陳美蓉等[8]提出的新型動態(tài)多目標(biāo)魯棒進(jìn)化優(yōu)化方法、丁進(jìn)良等[9]提出的基于參考點(diǎn)預(yù)測的動態(tài)多目標(biāo)優(yōu)化算法、梁靜等[10]提出的協(xié)同進(jìn)化動態(tài)粒子群優(yōu)化算法等。但是，現(xiàn)有進(jìn)化優(yōu)化方法大都假設(shè)候選解的評價代價較小，以保證算法有充足的時間響應(yīng)環(huán)境變化。然而，在很多實(shí)際應(yīng)用中，由于需要運(yùn)行仿真軟件或真實(shí)系統(tǒng)來評價每個候選解的優(yōu)劣，其用于評價單個解的代價往往很大。以基于EnergyPlus仿真軟件的建筑節(jié)能進(jìn)化優(yōu)化設(shè)計(jì)為例，在普通電腦上計(jì)算一個候選解的性能指標(biāo)值通常需要十幾分鐘[11]。此時，如果繼續(xù)使用傳統(tǒng)進(jìn)化算法來解決這類高計(jì)算代價的動態(tài)優(yōu)化問題，將很難在有限時間內(nèi)有效跟蹤問題最優(yōu)解的變化。

相對傳統(tǒng)數(shù)值優(yōu)化問題，高計(jì)算代價優(yōu)化問題的目標(biāo)函數(shù)往往沒有確定的數(shù)學(xué)解析式，或者數(shù)學(xué)表達(dá)式計(jì)算復(fù)雜且耗時[12]。這導(dǎo)致使用進(jìn)化算法解決該類問題時計(jì)算量過大，難以直接使用。鑒于此，學(xué)者們提出了許多處理高代價優(yōu)化問題的有效方法[13]，這其中最為典型的是代理模型輔助的進(jìn)化算法(surrogate-assisted evolutionary algorithms, SAEAs)[14-17]。該類算法使用代理模型替代計(jì)算耗時的真實(shí)目標(biāo)函數(shù)來評價進(jìn)化個體[12]。因?yàn)闃?gòu)建和使用代理模型所需的計(jì)算工作量低于真實(shí)目標(biāo)值的評價代價，該類算法可以顯著節(jié)省進(jìn)化算法的計(jì)算成本，有效解決個體評價代價高昂的問題。然而，對于高代價動態(tài)優(yōu)化問題，由于不僅其目標(biāo)函數(shù)會隨時間動態(tài)變化，而且其個體評價的代價高，已有的代理模型輔助進(jìn)化算法變得不再適用[18-19]。針對計(jì)算代價較高的數(shù)據(jù)驅(qū)動動態(tài)優(yōu)化問題，Luo等[20]利用聚類技術(shù)形成的鄰域物種構(gòu)建多個代理模型，給出了一種新且有效的代理輔助進(jìn)化算法(neighborhood-based speciation differential evolution, NSDE)。該算法依據(jù)環(huán)境變化情況將動態(tài)優(yōu)化問題弱化為一系列靜態(tài)優(yōu)化問題，在環(huán)境發(fā)生變化后重新采樣并真實(shí)評價樣本的目標(biāo)函數(shù)值，以此來訓(xùn)練當(dāng)前環(huán)境下的代理模型。由于需要不斷重新采樣，該算法存在樣本產(chǎn)生代價過高的不足。

鑒于此，針對高計(jì)算代價動態(tài)優(yōu)化問題，本文提出一種代理模型輔助的動態(tài)粒子群優(yōu)化算法，用以減少評價個體或粒子真實(shí)目標(biāo)值的次數(shù)，并及時跟蹤不同環(huán)境下問題的最優(yōu)解。主要創(chuàng)新點(diǎn)有：(1)提出一種基于多方向預(yù)測的初始種群產(chǎn)生方法，用來及時響應(yīng)問題環(huán)境的變化。當(dāng)環(huán)境發(fā)生變化時，利用歷史環(huán)境下問題多個最優(yōu)解(包括全局和局部)的變化趨勢，同時預(yù)測新環(huán)境下問題最優(yōu)解的多個可能位置，并由此產(chǎn)生多樣性和收斂性都較好的初始種群。(2)提出一種融合目標(biāo)值預(yù)測的代理模型構(gòu)建方法。采用一種差分策略來預(yù)測歷史樣本在新環(huán)境下的目標(biāo)值，選擇部分優(yōu)秀的歷史樣本來構(gòu)建代理模型；同時，利用優(yōu)秀的歷史樣本和初始種群產(chǎn)生訓(xùn)練樣本集合，在減少真實(shí)函數(shù)評價次數(shù)的基礎(chǔ)上，提高所建初始代理模型的質(zhì)量。

1 基礎(chǔ)工作

1.1 動態(tài)優(yōu)化問題

動態(tài)單目標(biāo)優(yōu)化問題和傳統(tǒng)優(yōu)化問題一樣，包括目標(biāo)函數(shù)、決策變量和約束條件[21-23]。它們的主要區(qū)別在于是否含有依賴于時間的參數(shù)向量。在優(yōu)化問題中，最小化和最大化兩類問題可以互相轉(zhuǎn)換。以最小化問題為例，動態(tài)優(yōu)化問題可以表示為

minY=f(X,ω(t))。

s.t.gi(X,ω(t))≤0,i=1,2,…,q,

hi(X,ω(t))=0,j=1,2,…,p,

X∈S?RD。

(1)

其中:X=(x1,x2,…,xn)是n維決策向量;Y代表其目標(biāo)函數(shù)值;S為問題的搜索空間；ω(t)=(ω1(t),ω2(t),…,ωi(t))是一個依賴于時間的參數(shù)向量；gi(X)表示第i個不等式約束;hj(X)表示第j個等式約束；S中所有滿足約束條件的可行解構(gòu)成的可行域，記為Ω?S；t表示環(huán)境變化時刻。

對于一個動態(tài)優(yōu)化問題，當(dāng)環(huán)境發(fā)生變化時，目標(biāo)函數(shù)f和約束函數(shù)都可能隨之變化。這就意味著，問題的最優(yōu)解是隨著環(huán)境變化而不斷變化的，歷史最優(yōu)解可能已不再適合新的環(huán)境。所以，對一個動態(tài)優(yōu)化算法而言，不僅要具有較好的收斂性，還要能夠快速有效地跟蹤問題變化的最優(yōu)解。

1.2 粒子群優(yōu)化算法

粒子群優(yōu)化算法(particle swarm optimization, PSO)自從1995年被提出以來，已被廣泛應(yīng)用于各種優(yōu)化問題[24-28]，目前已成為進(jìn)化優(yōu)化中的代表性算法[29-30]。該算法通過模擬鳥群等生物尋找食物的過程，通過粒子群中各粒子之間相互協(xié)作、共享信息來尋找問題的全局最優(yōu)解[31-32]。在PSO中，一群粒子在搜索空間中一起進(jìn)化或飛行；在進(jìn)化過程中，每個粒子向著自己經(jīng)歷過的最優(yōu)位置和鄰域粒子經(jīng)歷過的最優(yōu)位置移動。根據(jù)粒子鄰域大小的不同，傳統(tǒng)算法分為全局版粒子群優(yōu)化(global PSO)和局部版粒子群優(yōu)化(local PSO)2種模式。對于每個粒子而言，全局版的鄰域被定義為整個粒子群，而局部版使用了不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來確定粒子的鄰域。

本文考慮收斂速度快的全局版PSO。在全局版中，每個粒子由速度和位置構(gòu)成。具體地，在一個n維搜索空間中，設(shè)Xi(k)=(xi,1,xi,2,…,xi,n)為第k次迭代時第i個粒子的位置，其速度為Vi(k)=(vi,1,vi,2,…,vi,n)；粒子Xi目前為止找到的最佳位置(稱為個體最優(yōu)點(diǎn))為Pbesti(k)=(pbesti,1,pbesti,2,…,pbesti,n)，整個粒子群到目前為止找到的最佳位置(稱為全局最優(yōu)點(diǎn))為Gbest(k)=(gbest1,gbest2,…,gbestn)，那么，在下一次迭代時，該粒子的更新公式如下：

(2)

式中:參數(shù)w為慣性權(quán)重，表示先前速度的慣性大?。籧1和c2是加速度參數(shù)，為粒子向兩個最優(yōu)點(diǎn)飛行的動力系數(shù)；r1和r2為[0, 1]內(nèi)的兩個隨機(jī)數(shù)；k為算法迭代次數(shù)。

1.3 RBF代理模型

在使用進(jìn)化算法解決高計(jì)算代價優(yōu)化問題時，常用方法是利用低代價的代理模型來替代高代價的目標(biāo)函數(shù)，用來評價進(jìn)化過程中產(chǎn)生的候選解或個體[17]。目前，諸多優(yōu)秀的學(xué)習(xí)算法已被用于構(gòu)建代理模型，如高斯過程(Gaussian process, GP)[33]、徑向基函數(shù)網(wǎng)絡(luò)(radial basis functions, RBF)[34]、多項(xiàng)式回歸(polynomial regression, PR)[35]等。

徑向基函數(shù)是由Powell提出的一種多變量插值函數(shù)，其實(shí)質(zhì)是某種沿徑向?qū)ΨQ的標(biāo)最函數(shù)。由于具有較好的光滑性，RBF已被廣泛用于擬合昂貴數(shù)值模擬的工程系統(tǒng)響應(yīng)問題。具體地，常用的RBF的模型如下：

(3)

其中:m是采樣點(diǎn)的數(shù)量;λj是第j個基函數(shù)的系數(shù);φ是基函數(shù);r是歐幾里得范數(shù)；x是過程輸入變量的向量;xj是第j個采樣點(diǎn)向量；逼近函數(shù)f可以是一些權(quán)重不同的RBF的組合。最常用的基函數(shù)是高斯核函數(shù)，形式為φ(r)=e-cr2。

2 代理模型輔助的動態(tài)粒子群優(yōu)化算法

為解決高計(jì)算代價動態(tài)優(yōu)化問題，本文提出一種代理模型輔助的動態(tài)粒子群優(yōu)化算法(surrogate-assisted dynamic particle swarm optimization, SDPSO)。相對傳統(tǒng)粒子群優(yōu)化算法, SDPSO算法主要從如下兩個方面進(jìn)行了改進(jìn):一是環(huán)境變化后種群的初始化。當(dāng)檢測到環(huán)境變化后，提出一種基于多方向預(yù)測的種群初始化方法，平衡了種群中粒子的多樣性和收斂性;另一個是面向高計(jì)算代價目標(biāo)函數(shù)的代理模型。為了縮減訓(xùn)練樣本的產(chǎn)生代價，提出一種融合目標(biāo)值預(yù)測策略的初始代理模型構(gòu)建方法。

2.1 多方向預(yù)測的種群初始化策略

在使用進(jìn)化算法解決動態(tài)優(yōu)化問題時，需要經(jīng)過若干迭代來尋找問題的最優(yōu)解。一個高質(zhì)量的初始種群能夠使算法在一開始就比較接近最優(yōu)解，進(jìn)而減少算法的迭代次數(shù)。對于高計(jì)算代價的動態(tài)單目標(biāo)優(yōu)化問題而言，當(dāng)檢測到環(huán)境變化后及時產(chǎn)生高質(zhì)量的初始種群，不僅可以節(jié)省算法的迭代計(jì)算量，而且可以幫助種群更快地找到變化后問題的最優(yōu)解。鑒于此，提出一種基于多方向預(yù)測的種群初始化方法。根據(jù)第t和t-1個歷史環(huán)境下問題多個代表解的變化趨勢，從多個方向同時預(yù)測第t+1環(huán)境下問題最優(yōu)解的可能位置，進(jìn)而產(chǎn)生一個多樣性好且質(zhì)量高的初始種群。為此，首先給出一種目標(biāo)值引導(dǎo)的聚類技術(shù)，用來確定歷史問題的代表解集合。

2.1.1 歷史問題代表解集合的確定 由于同時具有好的多樣性和目標(biāo)值，問題的全局和局部最優(yōu)解通常最具代表性。然而，對于一個復(fù)雜優(yōu)化問題，因?yàn)闆]有充分的先驗(yàn)知識，決策者往往很難判斷其準(zhǔn)確的全局和局部最優(yōu)解信息。鑒于此，給出一種目標(biāo)值引導(dǎo)的聚類技術(shù)，從種群所得最優(yōu)粒子中尋找問題可能的全局和局部最優(yōu)解。

算法1:基于聚類技術(shù)的歷史問題代表解集的確定

輸入: 針對歷史問題所得最優(yōu)粒子集合Qt，聚類半徑L。

輸出: 歷史問題的代表解集RSt。

步驟4: 輸出代表解集合RSt。

可以看出，通過在決策變量空間中對最優(yōu)粒子進(jìn)行聚類，上述方法可以保證所選代表解的多樣性；通過選擇每一個類中目標(biāo)值最優(yōu)的粒子作為代表粒子，該方法又可以保證所選代表解都具有較好的函數(shù)值。分析優(yōu)化多峰函數(shù)時種群的分布性可知，鄰域中目標(biāo)值最優(yōu)的粒子通常最接近問題的全局或局部最優(yōu)解。這就意味著，從每個類中選擇目標(biāo)值最優(yōu)的粒子，在一定程度上可以反映出問題的全局和局部最優(yōu)解信息。

(4)

(5)

為提高種群中粒子位置的多樣性，僅利用公式(5)初始化種群中一半粒子的位置；對于剩余一半粒子，則在搜索空間中隨機(jī)初始化它們的位置。進(jìn)一步，算法2給出了所提種群初始化策略的偽代碼。

算法2:本文種群初始化策略

輸入: 第t和t-1環(huán)境時刻下所得問題的代表解集合RSt和RSt-1，種群規(guī)模N。

輸出: 初始化后的種群Pt-1。

步驟1: 根據(jù)公式(4)確定RSt中每個解的選擇概率；

步驟2.1:i=1；

步驟3: 在搜索空間中隨機(jī)產(chǎn)生第i+1到第N個粒子的位置；

步驟4: 輸出種群Pt+1。

本文通過預(yù)測方法來尋找動態(tài)優(yōu)化問題最優(yōu)解的大致位置，并在最優(yōu)解附近初始化種群，可以使種群一開始就具有較好的質(zhì)量，進(jìn)而加快算法的搜索速度。與此同時，通過多個方向?qū)Τ跏挤N群進(jìn)行預(yù)測，不僅可以保持良好的種群多樣性，而且能夠避免因?yàn)轭A(yù)測不準(zhǔn)確產(chǎn)生的估計(jì)誤差。

2.2 融合目標(biāo)值預(yù)測策略的代理模型構(gòu)建

對于一個動態(tài)優(yōu)化問題，當(dāng)環(huán)境發(fā)生變化后其表達(dá)式往往隨之變化。這就意味著，先前時刻的代理模型不再準(zhǔn)確甚至不再適用。為提高代理模型的精度，需要重新選擇訓(xùn)練樣本，重新構(gòu)建代理模型。構(gòu)建代理模型有兩大要素，即樣本點(diǎn)的產(chǎn)生和模型的訓(xùn)練。在樣本點(diǎn)的產(chǎn)生方面，本文提出一種融合目標(biāo)值真實(shí)評價和模型預(yù)測的初始樣本產(chǎn)生機(jī)制，用來有效均衡模型構(gòu)建的精度和代價。在模型的訓(xùn)練方面，采用常用的光滑性好的徑向基函數(shù)網(wǎng)絡(luò)來訓(xùn)練代理模型，在此不做闡述。

當(dāng)需要重新構(gòu)建代理模型時，可以利用的種群信息主要包括3部分：①歷史環(huán)境中用來更新代理模型的優(yōu)秀粒子，簡稱歷史優(yōu)秀粒子。由2.3節(jié)內(nèi)容可知，這些用來更新代理模型的樣本都是種群進(jìn)化過程中得到的代表解，不僅具有較好的多樣性，而且具有很好的目標(biāo)值。在很多情況下，歷史優(yōu)化問題往往與當(dāng)前環(huán)境下優(yōu)化問題具有一定的相關(guān)性，甚至具有較高的相似程度。這就意味著，在新環(huán)境下歷史問題中用來更新代理模型的樣本也可能具有較好的質(zhì)量，選擇這部分樣本來訓(xùn)練新代理模型會提高模型的預(yù)測精度。②面向新環(huán)境采用2.1節(jié)預(yù)測方法得到的粒子初始位置，簡稱預(yù)測粒子。顯然，在預(yù)測機(jī)制可靠的情況，這些粒子的位置將位于新問題的最優(yōu)解附近。此時，利用這些位置來產(chǎn)生樣本，并用它們來訓(xùn)練新的代理模型，勢必會提高模型對最優(yōu)解鄰域中候選解的預(yù)測精度。③除第②部分所提及的粒子外，新環(huán)境下初始種群中剩余粒子，簡稱隨機(jī)粒子。因?yàn)檫@些粒子是在搜索空間中隨機(jī)生成的，選擇它們作為樣本可以提高訓(xùn)練樣本的多樣性。

本文利用上述3部分種群信息來產(chǎn)生當(dāng)前第t+1時刻下模型的訓(xùn)練樣本。然而，分析種群進(jìn)化過程可知，上述種群信息中可能包含數(shù)量過多的粒子。利用真實(shí)函數(shù)評價所有這些粒子的目標(biāo)值，并用其訓(xùn)練代理模型，勢必可以保證代理模型的精度，但不免增加算法的計(jì)算代價。鑒于此，給出一種融合目標(biāo)值真實(shí)評價和模型預(yù)測的初始樣本產(chǎn)生機(jī)制。訓(xùn)練樣本的構(gòu)成方法如下：(1)采用一種差分機(jī)制預(yù)測歷史優(yōu)秀粒子在新環(huán)境下的目標(biāo)值，僅選擇目標(biāo)值最好的部分粒子進(jìn)行真實(shí)評價，并利用這些粒子及其真實(shí)目標(biāo)值組成第1部分樣本；(2)真實(shí)評價第二部分中的所有預(yù)測粒子，并利用這些粒子及其真實(shí)目標(biāo)值組成第2部分樣本；(3)從隨機(jī)粒子中選擇與上述兩部分粒子差異較大的粒子，進(jìn)行真實(shí)評價，并利用這些粒子及其真實(shí)目標(biāo)值組成第3部分樣本。因?yàn)榈?部分樣本可以直接得到，此處不再闡述。下面給出第1和第3部分樣本的詳細(xì)產(chǎn)生方法。

第1部分樣本的產(chǎn)生方法：基于目標(biāo)值預(yù)測的初始樣本產(chǎn)生機(jī)制。在每個時刻，更新代理模型的粒子都需要使用真實(shí)函數(shù)來評價，而且這些粒子在當(dāng)前種群中屬于適應(yīng)值較優(yōu)的一類粒子，重復(fù)利用這些粒子的信息，可以在一定程度上減少計(jì)算代價。假設(shè)在第t個環(huán)境時刻用來更新代理模型的歷史優(yōu)秀粒子集合為Ht，首先依據(jù)公式(6)預(yù)測Ht中每個粒子在當(dāng)前第t+1環(huán)境下的目標(biāo)值

(6)

(7)

隨后, 從Rt+1中選擇擁擠程度值最大的前β%的粒子, 并利用真實(shí)目標(biāo)函數(shù)評價這些粒子的目標(biāo)值。這些被選粒子及其真實(shí)目標(biāo)值即組成第3部分樣本。

進(jìn)一步，算法3給出了產(chǎn)生上述3部分樣本的具體執(zhí)行步驟。算法中參數(shù)α和β影響到訓(xùn)練樣本的分布性。假設(shè)需要產(chǎn)生的初始樣本數(shù)目為N1，第t+1個環(huán)境下初始種群中預(yù)測粒子和隨機(jī)粒子的數(shù)目分別為|Ct+1|和|Rt+1|，第t個環(huán)境下的歷史優(yōu)秀粒子集合為|Ht|，那么，有

α|Ht|=N1-|Ct+1|-β|Rt+1|。

(8)

算法3: 融合目標(biāo)值預(yù)測策略的初始訓(xùn)練樣本產(chǎn)生算法

輸入: 第t+1個環(huán)境下的初始種群Pt+1，初始種群中預(yù)測粒子集合Ct+1和隨機(jī)粒子集合Rt+1，Pt+1=Ct+1∪Rt+1；第t個環(huán)境下的歷史優(yōu)秀粒子集合為Ht；

輸出: 第t+1個環(huán)境的訓(xùn)練樣本集合Tt+1。

步驟1: 利用Ht中粒子信息，產(chǎn)生第1部分樣本；

步驟1.1: 依據(jù)公式(6)預(yù)測Ht中每個粒子在當(dāng)前第t+1環(huán)境下的目標(biāo)值；

步驟1.2: 從Ht中選擇目標(biāo)值最優(yōu)的前α%粒子, 并保存到臨時集合A中；

步驟3: 利用Rt+1中粒子信息，產(chǎn)生第3部分樣本；

步驟3.1: 計(jì)算Rt+1中每個粒子的相對擁擠程度；

步驟3.2: 從Rt+1中選擇擁擠程度最大的前β%的粒子，并保存到臨時集合B中；

步驟4: 輸出訓(xùn)練樣本集合Tt+1=T't+1∪T″t+1∪T?t+1。

由此可見，當(dāng)初始樣本數(shù)目N1確定后，參數(shù)α和β可以退化為一個參數(shù)。進(jìn)一步，實(shí)驗(yàn)3.3將分析不同α取值對模型訓(xùn)練結(jié)果的影響。選定上述訓(xùn)練樣本后，使用RBF神經(jīng)網(wǎng)絡(luò)即可構(gòu)建出初始代理模型。神經(jīng)網(wǎng)絡(luò)的輸入為被優(yōu)化問題的決策變量，輸出為預(yù)測得到的目標(biāo)值。本文選擇RBF作為代理模型的原因如下：第一，RBF具有很強(qiáng)的非線性擬合能力，可以映射任意復(fù)雜的非線性關(guān)系，并且學(xué)習(xí)規(guī)則簡單；第二，RBF不僅具有全局逼近能力，而且在局部信息描述上也有很好的精度；第三，RBF具有強(qiáng)的魯棒性和自學(xué)習(xí)能力[34]。

在上述所代理模型更新策略中，代理模型的訓(xùn)練樣本由三部分組成。第一部分是歷史環(huán)境得到的優(yōu)秀粒子，第二部分是采用2.1節(jié)預(yù)測方法得到的預(yù)測粒子?？紤]不同環(huán)境之間的相似性，這兩部粒子形成的樣本通常具體很好的質(zhì)量，甚至逼近當(dāng)前環(huán)境的最優(yōu)解。這些粒子訓(xùn)練得到的代理模型更能精確地預(yù)測最優(yōu)解附近粒子的適應(yīng)值。第三部分是隨機(jī)粒子。因?yàn)檫@些粒子是在搜索空間中隨機(jī)生成的，選擇它們作為樣本可以提高訓(xùn)練樣本的多樣性。

2.3 代理模型的管理

在訓(xùn)練出初始代理模型后，即可使用該模型代替當(dāng)前環(huán)境下的高計(jì)算代價目標(biāo)函數(shù)來評價新粒子。但是，分析2.2節(jié)可知，大部分初始訓(xùn)練樣本源自預(yù)測結(jié)果，而預(yù)測結(jié)果可能存在不同程度的不確定性。因此，并不能完全保證所建初始代理模型可以正確擬合優(yōu)化問題。為進(jìn)一步減小代理模型的誤差，在進(jìn)化過程中仍然需要利用新產(chǎn)生的優(yōu)秀粒子信息來不斷更新代理模型。

本文采用加點(diǎn)訓(xùn)練的方式來更新代理模型[36]。在算法第k次迭代過程中，如果最佳新生粒子的預(yù)測目標(biāo)值優(yōu)于先前最優(yōu)粒子的目標(biāo)值，則計(jì)算該最佳粒子的真實(shí)目標(biāo)值。如果其真實(shí)與預(yù)測目標(biāo)值之間的差值大于規(guī)定閾值，則利用該粒子及其真實(shí)目標(biāo)值組成一個新樣本，存入算法3所得樣本集合Tt+1中；隨后，利用Tt+1中樣本重新訓(xùn)練代理模型。

2.4 所提粒子群優(yōu)化算法的執(zhí)行步驟

基于上述工作，下面給出所提代理模型輔助動態(tài)粒子群優(yōu)化算法的具體執(zhí)行步驟。圖1給出了所提算法的流程圖。需要說明的是，針對第2個環(huán)境后的每個環(huán)境，都利用一個集合Tt保存該環(huán)境所用的訓(xùn)練樣本。

圖1 所提粒子群優(yōu)化算法的流程圖

步驟1：初始化。確定算法所需參數(shù)，包括種群規(guī)模N、初始樣本規(guī)模N1、初始樣本控制參數(shù)α等；在搜索空間中隨機(jī)初始化種群中N個粒子的位置；初始化每個粒子的個體最優(yōu)點(diǎn)為其自身，其全局最優(yōu)點(diǎn)為種群中最優(yōu)粒子的位置；設(shè)置迭代次數(shù)k=1。

步驟2：構(gòu)建當(dāng)前環(huán)境的初始代理模型。對于前2個初始環(huán)境，利用真實(shí)目標(biāo)函數(shù)評價初始種群中所有粒子的目標(biāo)值，并利用這些粒子及其真實(shí)目標(biāo)函數(shù)構(gòu)成訓(xùn)練樣本，訓(xùn)練RBF網(wǎng)絡(luò)得到該環(huán)境的初始代理模型。對于后續(xù)環(huán)境，采用2.2節(jié)方法產(chǎn)生當(dāng)前環(huán)境的初始代理模型。

步驟3：更新粒子位置，產(chǎn)生新解。首先，采用代理模型預(yù)測出所有新生粒子的目標(biāo)函數(shù)值，選出目標(biāo)值最大的粒子；隨后，基于預(yù)測得到的目標(biāo)值，采用標(biāo)準(zhǔn)方法[31]更新每個粒子的個體和全局最優(yōu)點(diǎn)，并由公式(2)產(chǎn)生下一代粒子的位置。

步驟4：管理代理模型。如果步驟3所選最佳粒子的預(yù)測目標(biāo)值優(yōu)于先前最優(yōu)粒子的目標(biāo)值，則計(jì)算該最佳粒子的真實(shí)目標(biāo)值。如果其真實(shí)目標(biāo)值與預(yù)測目標(biāo)值之間的差值大于規(guī)定閾值，則執(zhí)行2.3節(jié)方法，重新訓(xùn)練代理模型。

步驟5：判斷環(huán)境是否發(fā)生變化，并采取相應(yīng)的響應(yīng)策略。重新評價當(dāng)前所得最優(yōu)粒子的真實(shí)目標(biāo)函數(shù)值，如果前后兩代該粒子的目標(biāo)值發(fā)生變化，則認(rèn)為環(huán)境發(fā)生變化。如果環(huán)境發(fā)生變化，采用2.1節(jié)方法初始化種群中粒子位置，初始化迭代次數(shù)為k=1，并返回步驟2；否則，設(shè)置迭代次數(shù)k=k+1，進(jìn)入步驟6。

步驟6：判斷在當(dāng)前環(huán)境內(nèi)算法是否滿足終止條件。如果滿足，則終止算法，輸出當(dāng)前環(huán)境下最優(yōu)解，并等待新環(huán)境出現(xiàn)；否則，返回步驟3。如果不存在新環(huán)境，終止整個算法。

3 實(shí)驗(yàn)與分析

本節(jié)分析本文算法的有效性。首先，給出所用高計(jì)算代價動態(tài)測試問題；其次，給出實(shí)驗(yàn)所涉及的參數(shù)設(shè)置，并分析關(guān)鍵參數(shù)對本文所提算法的影響；然后，分析所提兩個關(guān)鍵算子對算法性能的影響；最后，與傳統(tǒng)代理模型輔助進(jìn)化算法對比，說明所提算法的有效性。

3.1 動態(tài)優(yōu)化測試函數(shù)

廣義動態(tài)基準(zhǔn)生成器(GDBG)常被用于產(chǎn)生動態(tài)優(yōu)化問題[37-38]。本文使用GDBG產(chǎn)生的6個測試函數(shù)驗(yàn)證所提算法的性能，它們分別是旋轉(zhuǎn)峰函數(shù)(F1)、組合Sphere(F2)、組合Rastrigin(F3)、組合Griewank(F4)、組合Ackley(F5)和混合組合函數(shù)(F6)[39]。在這些函數(shù)中，F(xiàn)1和F2有10個局部最優(yōu)，其他函數(shù)有大量的局部最優(yōu)。由于本文針對最小化問題設(shè)計(jì)了相關(guān)算子，因此通過取負(fù)的方式，將上述測試函數(shù)中的最大化問題轉(zhuǎn)換為最小化問題。每個函數(shù)有6種環(huán)境變化類型, 即小階躍變化(T1)、大階躍變化(T2)、隨機(jī)變化(T3)、混沌變化(T4)、循環(huán)變化(T5)和帶噪聲的循環(huán)變化(T6)；后續(xù)實(shí)驗(yàn)設(shè)置環(huán)境變化次數(shù)為60。進(jìn)一步，為了模擬函數(shù)評價的高計(jì)算代價特性，每次函數(shù)評價時設(shè)置一個延時函數(shù)以模擬其真實(shí)的計(jì)算耗時，實(shí)驗(yàn)設(shè)置為1 s。

3.2 參數(shù)設(shè)置與性能測度

在每個環(huán)境中訓(xùn)練代理模型的樣本規(guī)模取值為50個，選擇MATLAB中的newrb函數(shù)訓(xùn)練代理模型[40]。各項(xiàng)參數(shù)設(shè)置如下：均方誤差設(shè)置為0.25，擴(kuò)展速度設(shè)置為0.5，最大神經(jīng)元數(shù)目設(shè)置為50，兩次顯示之間添加的神經(jīng)元數(shù)目設(shè)置為5。對于任意一個測試函數(shù)的每個變化類型，都獨(dú)立運(yùn)行比較算法20次。

本文所提SDPSO算法所需參數(shù)的設(shè)置情況[41]如下：初始種群的規(guī)模設(shè)置為50，收斂因子w設(shè)置為0.729, 加速度常數(shù)c1和c2設(shè)置為2.05。在公式(5)和公式(6)中，噪聲擾動ε和ε′皆設(shè)置為服從標(biāo)準(zhǔn)正態(tài)分布的一個隨機(jī)數(shù)。在算法迭代過程中，需要設(shè)置一個誤差閾值來判斷是否需要更新代理模型。為在減少計(jì)算代價的同時加快進(jìn)化進(jìn)程，誤差閾值的設(shè)置需要兼顧算法的計(jì)算速度和結(jié)果的精度。對于函數(shù)F1，由于在算法后期種群所得最優(yōu)解的變化并不明顯，因此設(shè)置其誤差閾值為5；對于函數(shù)F2—F6，由于在算法后期種群所得最優(yōu)解的誤差仍然比較大，故此設(shè)置它們的誤差閾值為50。當(dāng)全局最優(yōu)的變化超過這個閾值時，即刻重新選擇樣本點(diǎn)更新代理模型。

使用最優(yōu)解誤差來度量算法的性能，其值為針對所有環(huán)境算法得到的最優(yōu)結(jié)果與真實(shí)最優(yōu)解之間的平均距離[42]，公式為

(9)

其中：E代表環(huán)境數(shù)目；ri是第i個環(huán)境中算法得到的最優(yōu)值；oi為第i個環(huán)境中的真實(shí)全局最優(yōu)。

3.3 關(guān)鍵參數(shù)分析

在所提SDPSO算法中，參數(shù)α決定了代理模型的初始訓(xùn)練樣本，直接影響到算法的最終性能。本實(shí)驗(yàn)選擇F1-T1、F1-T6、F3-T2和F4-T2等問題作為測試對象，分析參數(shù)α取值變化對SDPSO算法性能的影響。依次取α={0.1,0.2,…,1}，圖2給出了不同取值下SDPSO所得最優(yōu)解的誤差。

圖2 不同α取值下所提算法所得誤差曲線

可以看出，對于測試問題F1-T1、F1-T6和F4-T2，當(dāng)參數(shù)α取值為0.3時所提算法得到了最佳結(jié)果；對于測試問題F3-T2，當(dāng)參數(shù)α取值為0.4時所提算法得到了最佳結(jié)果；當(dāng)參數(shù)α取值為0.3時，所提算法得到了排名第2的優(yōu)化結(jié)果。隨著參數(shù)α取值的不斷增加，所提算法處理4個問題的性能逐漸變差。當(dāng)參數(shù)α取值為1時，針對4個問題所提算法都得到了最差結(jié)果。產(chǎn)生這種現(xiàn)象的主要原因是，當(dāng)α=1時用于構(gòu)建代理模型的初始數(shù)據(jù)全都來自歷史環(huán)境的最優(yōu)解。一方面，這些解的多樣性相對較差；另一方面, 相對新環(huán)境其函數(shù)值也可能較差。利用分布性和最優(yōu)性相對較差的樣本集合來構(gòu)建代理模型，勢必會降低進(jìn)化過程中粒子目標(biāo)值的預(yù)測精度，進(jìn)而影響算法的性能。鑒于此，后續(xù)實(shí)驗(yàn)設(shè)置α=0.3。

3.4 關(guān)鍵策略分析

本節(jié)實(shí)驗(yàn)分析本文種群初始化策略和代理模型更新策略的有效性。

3.4.1 基于多方向預(yù)測的種群初始化策略 為了驗(yàn)證本文基于多方向預(yù)測的種群初始化策略的有效性，將SDPSO中種群初始化策略替換成隨機(jī)初始化種群策略[43]，并記改變后算法為NA-SAPSO。通過比較SDPSO和NA-SAPSO的結(jié)果，用來驗(yàn)證本文所提種群初始化策略的有效性。為了避免其他因素的干擾，NA-SAPSO采用與SDPSO相同的參數(shù)設(shè)置，而且NA-SAPSO和SDPSO中的代理模型都采用RBF代理模型。

圖3展示了NA-SAPSO和SDPSO處理6個測試問題時所得結(jié)果的平均誤差?？梢钥闯觯瑢τ贔1-T3、F2-T2、F2-T3、F2-T5、F2-T6和F4-T6等6種情況，SDPSO所得誤差要略小于NA-SAPSO所得誤差值；然而，對于剩余全部30種情況，在所提種群初始化策略的幫助下，SDPSO的誤差值都明顯小于NA-SAPSO的誤差值。其原因如下：一方面，在算法初始階段，本文所提種群初始化策略既可獲得一個高質(zhì)量的初始種群，這在一定程度上可以加快算法的搜索速度；另一方面，本文方法可以從多個方向同時預(yù)測新環(huán)境下問題最優(yōu)解的可能位置，這在一定程度上可以提高種群的多樣性，增加種群找到問題真實(shí)最優(yōu)解的概率。

圖3 NA-SAPSO和SDPSO處理6個測試問題(36種情況)時所得結(jié)果的平均誤差

3.4.2 融合目標(biāo)值預(yù)測機(jī)制的代理模型更新策略 為了驗(yàn)證本文融合目標(biāo)值預(yù)測機(jī)制的代理模型更新策略的有效性，將其與基于初始種群的樣本產(chǎn)生策略進(jìn)行對比。具體地，將SDPSO中的樣本產(chǎn)生策略替換成基于初始種群的樣本產(chǎn)生策略，并記改變后的算法為IP-SAPSO。通過比較SDPSO和IP-SAPSO的結(jié)果，用來驗(yàn)證本文代理模型更新策略效果。為了避免其他因素的干擾，IP-SAPSO采用與SDPSO相同的參數(shù)設(shè)置。

圖4展示了IP-SAPSO和SDPSO處理6個測試問題時所得結(jié)果的平均誤差?？梢钥闯?，除F2-T5、F2-T6、F3-T3和F4-T6等4種情況外，對于剩余全部32種情況，在本文種群初始化策略的幫助下，SDPSO所得誤差都明顯小于NA-SAPSO所得誤差值。其原因如下：一方面，本文代理模型更新策略重復(fù)利用了歷史環(huán)境信息，減少了真實(shí)函數(shù)的評價次數(shù)，大大降低了算法的計(jì)算代價；另一方面，本文策略使用得到的最優(yōu)解不斷更新代理模型，使代理模型在真實(shí)最優(yōu)解附近更為精確,這在一定程度上可以充分保證算法的局部開發(fā)能力。因此，本文代理模型更新策略也是非常有效的。

圖4 IP-SAPSO和SDPSO處理6個測試問題時所得結(jié)果的平均誤差

3.5 對比結(jié)果分析

為了驗(yàn)證本文算法的有效性，本文對已有的動態(tài)進(jìn)化優(yōu)化算法(DPSO)[44]進(jìn)行擴(kuò)展，并將其作為對比算法。具體地，在DPSO的框架下加入RBF神經(jīng)網(wǎng)絡(luò)作為代理模型，每次環(huán)境變化后利用初始種群重新構(gòu)建代理模型，記擴(kuò)展后的DPSO算法為RBF-DPSO。

將本文算法SDPSO與RBF-DPSO進(jìn)行對比，表1—6分別展示了兩種算法處理6個測試問題時所得平均誤差值和運(yùn)行時間以及每個環(huán)境下真實(shí)函數(shù)的平均評價次數(shù)。其中，T1—T6表示問題環(huán)境變化的6種狀態(tài)，計(jì)算時間為單個環(huán)境下算法的執(zhí)行時間。進(jìn)一步，利用置信度為0.05的t檢驗(yàn)比較兩種算法的顯著差異性，其中，“+”表示SDPSO所得結(jié)果顯著優(yōu)于選定對比算法，“-”表示選定對比算法的結(jié)果顯著優(yōu)于SDPSO，“=”兩者所得結(jié)果無明顯差異。

關(guān)于測試問題F1，由表1可以看出：(1)對于問題采用的所有6種環(huán)境變化類型，本文SDPSO算法都得到了明顯優(yōu)于RBF-DPSO的平均誤差。以T1環(huán)境類型為例，SDPSO所得結(jié)果的平均誤差為69.555 8，相對RBF-DPSO降低了10.146 2。(2)對比它們的平均運(yùn)行時間可知，在顯著提升結(jié)果精度的同時，SDPSO的計(jì)算代價也小于RBF-DPSO。

表1 兩種算法處理F1時所得平均誤差和時間以及評價次數(shù)

關(guān)于測試問題F2，由表2可以看出：在6種環(huán)境變化類型中，所提SDPSO算法針對3種變化類似(T1、T4和T6)都得到了明顯優(yōu)于RBF-DPSO的平均誤差；對于環(huán)境變化類型T2，SDPSO也得到了與RBF-DPSO相近的平均誤差；剩余兩種變化類型，盡管RBF-DPSO所得結(jié)果的平均誤差明顯小于SDPSO，但其運(yùn)算時間要高于本文SDPSO算法。

表2 兩種算法處理F2時所得平均誤差和時間以及評價次數(shù)

關(guān)于測試問題3，由表3可以看出：對于問題采用的所有6種環(huán)境變化類型，本文SDPSO算法都得到了明顯優(yōu)于RBF-DPSO的平均誤差。以T2環(huán)境類型為例，SDPSO所得結(jié)果的平均誤差為718.769 3, 相對RBF-DPSO降低了89.131 8。并且，在取得較低平均誤差的前提下，對于6種環(huán)境變化類型SDPSO所用時間也要少于RBF-DPSO。

表3 兩種算法處理F3時所得平均誤差和時間以及評價次數(shù)

關(guān)于測試問題4，由表4可以看出：在所有6種環(huán)境變化類型中，本文SDPSO算法對4種變化類型(T2—T5)都得到了明顯優(yōu)于RBF-DPSO的平均誤差，而且其運(yùn)行時間也要少于RBF-DPSO；對于剩余兩種變化類型(T1和T6)，盡管RBF-DPSO算法所得誤差要小于SDPSO，但是SDPSO的運(yùn)行時間要小于RBF-DPSO。

表4 兩種算法處理F4時所得平均誤差和時間以及評價次數(shù)

關(guān)于測試問題5，由表5可以看出：對于問題采用的所有6種環(huán)境變化類型，本文SDPSO算法都得到了明顯優(yōu)于RBF-DPSO的平均誤差。以T4變化類型為例，SDPSO所得結(jié)果的平均誤差為1 555.106 5，相對RBF-DPSO降低了173.346 5。并且，在取得較低平均誤差的前提下，對于6種環(huán)境變化類型SDPSO所用時間也要少于RBF-DPSO。

表5 兩種算法處理F5時所得平均誤差和時間以及評價次數(shù)

關(guān)于測試問題6，由表6可以看出：對于問題采用的所有6種環(huán)境變化類型，本文SDPSO算法都得到了明顯優(yōu)于RBF-DPSO的平均誤差。以T5變化類型為例，SDPSO所得結(jié)果的平均誤差為1 688.508 1，相對RBF-DPSO降低了62.852 8。并且，在取得較低平均誤差的前提下，對于6種環(huán)境變化類型SDPSO所用時間也要少于RBF-DPSO。

表6 兩種算法處理F6時所得平均誤差和時間以及評價次數(shù)

4 結(jié)論

高計(jì)算代價的動態(tài)優(yōu)化問題普遍存在于日常生產(chǎn)生活中。本文針對該類復(fù)雜優(yōu)化問題，提出了一種代理模型輔助的動態(tài)粒子群優(yōu)化算法(SDPSO)。通過引入一種融合目標(biāo)值預(yù)測的代理模型構(gòu)建方法和一種基于多方向預(yù)測的種群初始化策略，該算法不僅可以得到優(yōu)異的問題最優(yōu)解，而且可以有效減少個體真實(shí)評價次數(shù)、加快種群尋優(yōu)速度。實(shí)驗(yàn)結(jié)果表明，針對6個典型測試問題和6種環(huán)境變化類型組合而成的36種情況，除F2-T2、F2-T3、F2-T5和F4-T6等少數(shù)情況外，本文算法都能以較少的運(yùn)算時間得到最優(yōu)結(jié)果。

然而，代理模型的構(gòu)建和管理仍然需要較高的計(jì)算代價，因此，選擇或設(shè)計(jì)更為有效的代理模型是需要進(jìn)一步研究的課題。此外，將所提算法應(yīng)用于實(shí)際的昂貴動態(tài)優(yōu)化問題也是今后的研究方向。