利用改進(jìn)的并行粒子群算法對變分資料同化的研究

董怡琦，周明睿，劉力源，余一冬，陳 科，童亞拉，2

(1.湖北工業(yè)大學(xué)理學(xué)院，武漢 430068；2.湖北省能源光電器件與系統(tǒng)工程技術(shù)研究中心，武漢 430068)

自20世紀(jì)初以來，數(shù)值天氣預(yù)測作為一種預(yù)測方法，受到了廣泛的關(guān)注.隨著高性能計算機(jī)的誕生，高分辨率數(shù)值模式MM5的使用也成為一種熱門手段.Bjerknes[1]提出從數(shù)值預(yù)測整體來看，其中重要一個環(huán)節(jié)在于初始場，其數(shù)據(jù)是否精準(zhǔn)對最終輸出影響極大.MM5中的資料同化是一種變分資料同化，屬于非線性優(yōu)化問題.近年來，為了改進(jìn)變分同化準(zhǔn)確性和收斂性效率，粒子群算法(PSO)、遺傳算法(GA)等經(jīng)典群智能算法被引到資料同化中.王順風(fēng)、白晨等[2-3]分別提出了兩種遺傳算法(GA)同化方案，鄭琴[4]從PSO著手，改變慣性權(quán)重的變換策略，選擇合適的學(xué)習(xí)因子，設(shè)計了動態(tài)慣性權(quán)重粒子群算法(PSODIWAF)，該算法能有效解決含有不連續(xù)開關(guān)過程的變分資料同化問題.為滿足對精度和同化時間的要求，各種改進(jìn)的粒子群算法被利用到資料同化中，李成、張頂學(xué)[5-6]等對陷入局部最優(yōu)的問題進(jìn)行了改進(jìn)；劉明、袁小平[7-8]等采用不同的學(xué)習(xí)機(jī)制，通過效率更高的迭代公式，在收斂速度上作出了改進(jìn)，減少了收斂時間；何莉等[9]重點從運(yùn)行時間進(jìn)行突破，采用多核處理能力提高了算法處理速度，其采用的是粒子隨機(jī)替換策略，為了保證整個群體能夠進(jìn)行信息交流，同時也設(shè)置了共享區(qū)域；鄭琴[10]和張成興[11]分別設(shè)計了動態(tài)慣性權(quán)重粒子群算法(PSODIWAF)和時變雙重壓縮因子粒子群算法(PSOTVCF)將其用于資料同化.盡管在收斂精度上兩種算法都有了較大的改進(jìn)，但同化時間仍然存在缺陷.因此，受文獻(xiàn)[12]的啟發(fā)，本文設(shè)計了一種改進(jìn)的并行算法.該算法通過并行計算對粒子群完成分組，采用PSOTVCF進(jìn)行深度搜索，同時將具有不連續(xù)“開關(guān)”過程的變分資料同化作為應(yīng)用場景，建立了一種新的同化模型.在幾乎沒有降低同化精度的前提中，極大地提高了同化速度，減少了同化時間.

1 資料同化和粒子群算法簡介

1.1 資料同化的模式方程

文獻(xiàn)[4]中的偏微分方程被用作資料同化處理中的控制方程：

(1)

(2)

模擬參數(shù)化過程中的“on-off”開關(guān).可將(1)式轉(zhuǎn)化為其數(shù)值模式：

(3)

式中，空間格點用i表示，空間步長用Δl表示，且有l(wèi)i=iΔl.Δt為時間步長，tk=kΔt，k為空間層.N=T/Δt為積分過程中總的時間層；M+1=(L/Δl)+1為空間離散點總數(shù).

1.2 粒子群算法

在PSO中，D維空間的搜索個體用粒子表示，粒子擁有位置和速度兩個屬性.其每個時刻所在的位置被看作是待求解問題的一個候選解，粒子位置的變換認(rèn)為是最優(yōu)解的尋找過程.以及其移動速度是受截止到上一時刻自身所經(jīng)歷過的最優(yōu)位置和整個群體到達(dá)最優(yōu)位置的影響，每次迭代進(jìn)行相應(yīng)調(diào)整.

用下列公式對粒子進(jìn)行操作：

(4)

(5)

迭代終止條件沒有固定的要求，通常規(guī)定為當(dāng)前定位到的最優(yōu)位置已經(jīng)達(dá)到了設(shè)定的最小適應(yīng)閾值或者達(dá)到了設(shè)定的最大迭代次數(shù).

2 改進(jìn)的并行粒子群算法

2.1 設(shè)計思路

文獻(xiàn)[11]中設(shè)計了一種時變雙重壓縮因子粒子群算法(PSOTVCF)，在慣性權(quán)重的基礎(chǔ)上引入雙重壓縮因子進(jìn)行迭代.雖然提高了同化精度，但也因此使收斂速度變慢，同化時間增加.為解決同化時間過長的問題，本文受文獻(xiàn)[12]的啟發(fā)，將粒子群分成四個子集，分配多核CPU中一個核給每個子集進(jìn)行計算，迭代的同時粒子與其他子集進(jìn)行信息交流，從而每個粒子都能較好地掌握整個種群的迭代狀況，并且利用PSOTVCF進(jìn)行粒子的更新.

2.2 時變雙重壓縮因子粒子群算法的并行處理

一般地，并行問題的處理有兩種方法：(1)功能分解形式，對問題自身進(jìn)行拆分，將一個大問題拆分成幾個子問題，然后再加以解決；(2)域分解形式，對問題區(qū)域進(jìn)行分解，對分解后的區(qū)域并行處理.P2PSO中采用區(qū)域分解形式進(jìn)行并行，同時引入?yún)f(xié)同進(jìn)化的策略.首先根據(jù)CPU核數(shù)確定分為4組，然后在主線程中依據(jù)分組數(shù)設(shè)定4個線程，再對每個線程進(jìn)行任務(wù)分配.并行中信息交流也有兩種方法：同步和異步.同步形式是4個線程內(nèi)粒子都完成了位置速度更新后，再評估和更新全局最優(yōu)個體的位置和速度.異步形式[12]是只要有其中一個線程內(nèi)完成了個體最優(yōu)粒子位置速度的更新，就馬上評估和更新全局最優(yōu)粒子信息.P2PSO算法屬于并行算法，本質(zhì)上是模擬鳥群捕食行為.因鳥群捕食過程中，只要有一只鳥發(fā)現(xiàn)了食物，便會通過一些形式去告知其他的鳥，而不是等所有的鳥都找到食物再去通知，這就是“即時種群通信行為”.因此該算法在信息交流的并行化中采用異步形式，每個線程完成了組內(nèi)粒子的更新后，申請獲取讀寫同步鎖來更新整個種群內(nèi)全局最優(yōu)粒子信息.

2.3 并行時變雙重壓縮因子粒子群算法

算法引入PSOTVCF進(jìn)行深度搜索，慣性權(quán)重ω用壓縮因子取代，緩解全局與局部探尋間的矛盾關(guān)系.其中通過加速因子計算得到壓縮因子，加速因子的計算公式為

(6)

其中，C1N是第一個加速因子的最大值，C1M是第一個加速因子的最小值，C2N是第二個加速因子的最大值，C2M是第二個加速因子的最小值.MAXITER是設(shè)定的最大迭代數(shù)，ITER是當(dāng)前迭代次數(shù).

PSOTVCF中粒子速度更新公式表示：

v(t+1)=χ(v(t)+φy(t))，

(7)

y(t+1)=χv(t)+(1-χφ)y(t)，

(8)

由此得到系統(tǒng)矩陣：

(9)

φ=C1+C2，

(10)

滿足條件φ>4，由收斂準(zhǔn)則得到壓縮因子的定義：

(11)

其中，壓縮因子χ為正實數(shù)，且χ∈(0，1).

單一壓縮因子[13]在高維多峰函數(shù)應(yīng)用中精度較低且平衡全局和局部搜索中能力極為限制，所以采用雙重壓縮因子.

速度計算公式轉(zhuǎn)換為：

v(t+1)=χ1(v(t)+C1Rand

(Pi-x(t)+C2Rand(Pg+x(t))))，

(12-1)

v(t+2)=χ2?(v(t+1)).

(12-2)

χ1和χ2均由公式(10)和(11)計算，其中χ1中加速因子取得是設(shè)定的初始值，而χ2中采用的是時變的加速因子，先由公式(6)計算加速因子再代入公式(10)(11)中.

設(shè)循環(huán)次數(shù)為N，得到最終簡化的粒子速度：

V(N)=(χ2?χ1)N-1(V(0)+φY).

(13)

時變雙重壓縮因子粒子群算法有效地改進(jìn)了粒子群算法容易陷入局部最優(yōu)的問題.

在變分資料同化應(yīng)用過程中，其中代價函數(shù)通過該公式進(jìn)行計算：

(14)

其中

(15)

表示q0滿足物理約束和相容性條件，這里q為q0代入模式方程(1)的解.

式(14)離散化后得到離散化函數(shù)：

(16)

PSOTVCF算法中采用的適應(yīng)度函數(shù)是：

(17)

其中

(18)

P2PSO的算法流程如下：

1)對算法參數(shù)進(jìn)行初始化，設(shè)定整個群體粒子數(shù)P，慣性權(quán)重ω，加速因子，分組數(shù)C以及在各個分組中的最大迭代次數(shù)I.

2)讀寫同步鎖設(shè)定，按照設(shè)定的分組數(shù)依次建立線程，在各個線程中確定組內(nèi)粒子數(shù)Pi和終止條件最大迭代次數(shù)I.

5)分組線程申請獲取讀寫同步鎖.

6)將更新后的組內(nèi)最優(yōu)解pgi與此時整個種群的最優(yōu)解pg進(jìn)行比較，若pgi優(yōu)于pg，則令pg=pgi.

7)分組線程釋放讀寫同步鎖.

9) 判斷是否滿足迭代終止條件，如果組內(nèi)迭代數(shù)達(dá)到預(yù)先設(shè)置的最大迭代數(shù)I，則停止該線程的計算，若不滿足則轉(zhuǎn)為步驟(4).

10)直至所有線程迭代結(jié)束，產(chǎn)生結(jié)果.

3 數(shù)值實驗結(jié)果分析

3.1 仿真環(huán)境

采取文獻(xiàn)[11]的實驗數(shù)據(jù)和實驗分析方法，將三種算法——PSOTVCF、PSODIWAF和P2PSO分別應(yīng)用于變分資料同化，在精度和時間上進(jìn)行比較.其中，在P2PSO中，慣性權(quán)重ω從0.7線性遞減到0.1，C1N=2.98，C1M=2.78，C2N=1.55，C2M=1.35，種群中含有200個粒子，設(shè)定迭代最大次數(shù)為200，測試環(huán)境為硬件Intel Core i5，軟件MATLAB R2017a.

3.2 收斂精度

圖1表示的是在迭代200次時，三種算法在200次同化實驗后的平均收斂精度圖.圖中，自上而下的橫線分別表示PSODIWAF，P2PSO，PSOTVCF，縱坐標(biāo)是收斂精度的對數(shù)log10J，其值越小表示同化質(zhì)量越好，同化結(jié)果越準(zhǔn)確.從實驗結(jié)果可直觀看出與PSODIWAF相比，P2PSO和PSOTVCF在同化實驗結(jié)果中更為準(zhǔn)確.兩者平均收斂精度相近，但P2PSO略差與PSOTVCF.為了明確三種算法在運(yùn)行過程中的差距緣由，需要繼續(xù)對收斂趨勢進(jìn)行分析.

圖1 三種算法在200次同化實驗中平均收斂精度圖Fig.1 Average convergence accuracy of three algorithms in 200 assimilation experiments

圖2表示的是PSODIWAF、PSOTVCF、P2PSO在迭代200次時收斂精度的變化趨勢.圖中橫坐標(biāo)代表迭代次數(shù)，縱坐標(biāo)同圖1含義相同，即為收斂精度的對數(shù)log10J.星號標(biāo)出的點分別為迭代次數(shù)50，100，150，200.折線從終點來看自上而下分別表示PSODIWAF，P2PSO，PSOTVCF.分段分析，在同化初期(迭代次數(shù)為50)，PSOTVCF與P2PSO結(jié)果大致相同，收斂精度均略低于PSODIWAF；同化中期(迭代次數(shù)為100)，三者同化質(zhì)量相似；同化后期(迭代次數(shù)為150)，PSOTVCF和P2PSO后來居上，同化質(zhì)量最好，PSODIWAF次之，并且粒子基本已經(jīng)收斂；實驗終點(迭代次數(shù)為200)，PSOTVCF同化質(zhì)量最好，其次是P2PSO，最后是PSODIWAF，其收斂數(shù)值依次為-13、-12.9、-11.2.從整體來看，P2PSO與原算法PSOTVCF在同化初期基本保持一致，自同化中期開始，兩者產(chǎn)生細(xì)微差距.因此P2PSO同化結(jié)果的質(zhì)量高于動態(tài)權(quán)重粒子群算法，與PSOTVCF相似.并行算法的精度略低于原算法的原因，應(yīng)該是由于在并行過程中信息交流的程度沒有單線程的高，從而導(dǎo)致收斂精度降低.

圖2 三種算法收斂精度變化趨勢對比圖Fig.2 Comparison of convergence accuracy trends of three algorithms

3.3 同化時間

將PSOTVCF、PSODIWAF和P2PSO應(yīng)用于資料同化問題中，同時記錄三種算法在迭代次數(shù)為50，100，150，200時所花費(fèi)的時間.因為粒子群算法具有一定的隨機(jī)性，為了使數(shù)據(jù)更加有說服力，每一個同化窗口進(jìn)行6組實驗.將6組試驗數(shù)據(jù)平均值記錄于表1中.

表1 三種算法在迭代次數(shù)為50，100，150，200時平均同化時間(s)對比表Tab.1 Comparison of average assimilation time(seconds) of three algorithms with iteration times of 50,100,150,200 s

通過表中數(shù)據(jù)，直觀上可得到無論迭代次數(shù)是在50，100，150還是200，P2PSO的同化速度都要比PSOTVCF和PSODIWAF快，同化時間縮短一半左右.P2PSO迭代200次的時間比PSOTVCF和PSODIWAF迭代100次的時間還要短.數(shù)據(jù)上計算得出在200代迭代之后P2PSO的收斂速度和PSODIWAF相比提高了51.5%左右，和PSOTVCF相比提高了55.1%左右.因此，本文所設(shè)計的并行粒子群算法通過多個CPU的聯(lián)合計算對于提高同化速度，縮短同化時間具有顯著的效果.

4 結(jié)論與展望

本文著重在時間上改進(jìn)了粒子群算法，結(jié)合計算機(jī)CPU的多核處理硬件知識，在不過度影響精度的情況下較大程度上加快了速度.在變分資料同化中采用所設(shè)計的算法，減少了同化時間，與時變雙重壓縮因子PSO和動態(tài)權(quán)重PSO算法相比在收斂速度上有了較大的提升，但在收斂精度上仍需改進(jìn).因此后續(xù)可針對因多線程導(dǎo)致粒子間信息交流程度略有降低的現(xiàn)象，對算法進(jìn)一步改進(jìn)，實現(xiàn)較大程度加快同化速度的同時也能夠進(jìn)一步提高收斂精度.本文將含“開關(guān)”過程的變分資料同化作為該算法的應(yīng)用場景，后續(xù)可嘗試著將P2PSO應(yīng)用于其他場景下的資料同化，擴(kuò)大所設(shè)計算法的適用空間.