基于主從角色分配的氣象自動站布局及其優(yōu)化

魏　叮,滕少華,宋靜靜,朱海濱

(1.廣東工業(yè)大學 計算機學院,廣州 510006;2.廣東省審計廳 計算機中心,廣州 510000;3.尼普森大學 計算機系,安大略省 諾斯貝 加拿大)

?

基于主從角色分配的氣象自動站布局及其優(yōu)化

魏叮1,滕少華1,宋靜靜2,朱海濱3

(1.廣東工業(yè)大學 計算機學院,廣州 510006;2.廣東省審計廳 計算機中心,廣州 510000;3.尼普森大學 計算機系,安大略省 諾斯貝 加拿大)

摘要:在成本受限的情況下,通過優(yōu)化氣象自動站布局,提高氣象數(shù)據(jù)收集的準確率。針對自動站作為代理可以同時扮演多個角色,提出了基于主從角色分配的GRA方法,解決多對多情況下組角色分配問題,從而優(yōu)化氣象自動站布局。結合南方某氣象局屬下氣象自動站現(xiàn)有布局和歷史數(shù)據(jù),并通過仿真實驗驗證了本方法的可行性,不僅提高了氣象數(shù)據(jù)收集準確率,同時削減了成本。本文的研究可為氣象局優(yōu)化氣象自動站布局提供參考。

關鍵詞:主從角色;E-CARGO;氣象自動站;GRA;氣象預測

氣象預測與人們的生產(chǎn)生活息息相關,對人們的生命財產(chǎn)安全以及經(jīng)濟活動至關重要,而提高氣象數(shù)據(jù)收集的準確率是提高氣象預測準確率的關鍵。地面氣象預測是實現(xiàn)天氣系統(tǒng)監(jiān)測的重要手段,是氣象預報與氣候分析以及災害監(jiān)測的重要途徑和數(shù)據(jù)基礎。氣象自動站將無線傳感器和傳統(tǒng)的面氣象觀測系統(tǒng)相結合,實現(xiàn)了全天候的實時觀測,克服了傳統(tǒng)人工觀測頻率低、空間分辨率低、數(shù)據(jù)誤差不確定等許多缺點,成為地面氣象觀測新的數(shù)據(jù)基礎[1]。然而氣象自動站建設成本較高,在成本有限的情況下,很難通過單一的建設新的氣象自動站或者增加氣象數(shù)據(jù)采集設備來提高氣象數(shù)據(jù)收集的準確率。因此,筆者希望通過優(yōu)化氣象自動站的布局,提高氣象數(shù)據(jù)收集的準確率。在氣象自動站布局優(yōu)化問題中,將資金分配到各個氣象自動站進行設備的更新與維護以提高整體收集氣象數(shù)據(jù)的準確率是一個協(xié)同的過程，而且氣象數(shù)據(jù)與氣象自動站的關系也可以用角色與代理的關系來描述。因此,本文使用基于角色協(xié)同的E-CARGO模型來對氣象自動站布局優(yōu)化問題進行建模。

E-CARGO[2-3]模型是朱海濱教授在RBC系統(tǒng)的基礎上,基于角色協(xié)同所提出。RBC(role-based collaboration)系統(tǒng)是一種計算思維方法論,主要通過角色作為底層的機制來幫助抽象、分類。結合E-CARGO模型,將氣象自動站與氣象數(shù)據(jù)之間的關系描述為角色與代理的關系,從而將氣象自動站布局優(yōu)化問題轉化為一個GRA問題來解決。由于一個氣象自動站可以安裝多種氣象數(shù)據(jù)采集設備,在同一時刻可以測量多種氣象數(shù)據(jù),因此,氣象自動站與氣象數(shù)據(jù)是多對多的關系,即一個代理可以扮演多個角色,一個角色也可以由多個代理扮演?；诖?筆者提出了基于主從角色的分配方法,用于解決多對多情況下的GRA問題,從而解決氣象自動站布局優(yōu)化問題。

1相關工作

目前,關于氣象預測已經(jīng)進行了大量的研究,并且產(chǎn)生了很多研究成果[4-6]。近幾年,主流的研究方法主要基于收集到的氣象數(shù)據(jù),通過應用人工智能算法、數(shù)據(jù)挖掘算法等來盡可能的提高氣象預測的準確率。例如,JIN et al[7]基于數(shù)值天氣預報產(chǎn)品,將人工神經(jīng)網(wǎng)絡和遺傳算法相結合,提出了一種新的預測方法,并且在中國廣西省3個不同的地方分別建立了3個人工神經(jīng)網(wǎng)絡預測模型。經(jīng)過實驗結果表明,文章中所提出的新的預測模型在這三個地方的預測結果都要優(yōu)于中國氣象臺的T213模型和日本的NWF模型。此外,滕少華和樊繼慧[8]研究了基于KNN的多組合器對氣象數(shù)據(jù)的分析,通過構造多個組合器對局域區(qū)域的氣象數(shù)據(jù)進行分析,針對局部地區(qū)的降雨情況,獲得了較好的分類結果,并且通過對數(shù)據(jù)的預處理,篩選出了對降雨量有明顯影響的氣象數(shù)據(jù)屬性,也為本文對氣象自動站布局優(yōu)化時角色的設計提供了參考。同時,氣象自動站作為收集地面氣象數(shù)據(jù)的平臺,也受到眾多科研人員的關注[9-10]。氣象自動站高頻率的觀測數(shù)據(jù)由于受到觀測地面環(huán)境的局部影響以及觀測儀器的固有缺陷,不免受到噪聲的干擾。HASU，KOIVO[11]通過對中尺度氣象自動站網(wǎng)絡中雨和風的測量錯誤分析,提出了幾種自動對雨和風進行測量錯誤分析的算法,對其進行修正。通過實驗表明,該算法有著很好的降噪效果,提高了氣象自動站測量數(shù)據(jù)的準確率。

2氣象自動站布局優(yōu)化建模

2.1基于主從角色的組角色分配

GRAP(Group Role Assignment Problem)是一個復雜的問題,基于遍歷搜索的算法擁有指數(shù)級時間復雜度,很難用于解決m較大的情況。在RBC系統(tǒng)中,代理扮演角色有平行模式和順序模式。平行模式意味著一個代理可在同一時刻扮演兩個或者更多的角色;順序模式表示一個代理在同一時刻只能扮演一個角色。在順序模式下,朱海濱教授提出了一種基于K-M算法的組角色分配方法,通過復制角色,調整角色和代理的個數(shù),將GRAP轉化為一個GAP,解決了順序模式下的組角色分配問題。在平行模式下,一個類似的解決GRAP問題的方法是復制代理,但復制代理卻會導致Q矩陣急劇膨脹。為了避免復制代理,筆者提出了主從角色的概念。

定義1主角色表示需要被代理重點扮演的角色,主角色有且只有一個。在氣象自動站優(yōu)化問題中則表示作為主角色的氣象數(shù)據(jù)需要被某個代理重點測量。

定義2從角色表示代理次要扮演的角色,其個數(shù)大于等于零。同樣,在自動站優(yōu)化問題中表示需要被某個代理輔助測量。

有了主從角色,平行模式下的組角色分配通過先分配主角色,再分配從角色完成。例如L=[2,1,1,2],其主角色矩陣Lm=[1,1,1,1],從角色矩陣LS=L-Lm=[1,0,0,1]。

在這里通過一個簡單的例子來說明組角色的分配過程。Q矩陣表示代理扮演角色的能力,是進行角色分配的依據(jù),是隨機產(chǎn)生的：

首先,對Lm=[1,1,1,1]和LS=[1,0,0,1]分別進行角色分配,得到其分配矩陣TS和Tm,如下所示，

其中T[i][j]=1表示將角色r[j]分配給代理A[i]。從而,可以得到L=[2,1,1,2]的分配矩陣T=Tm+TS,如下所示：

分配矩陣Tm分配矩陣TS

組角色分配矩陣

2.2氣象自動站布局優(yōu)化問題分析

氣象自動站分布在不同的地理位置上,受地理環(huán)境的影響,造成自動站測量氣象數(shù)據(jù)的能力也不盡相同。在成本受限時,如何將資金投資到各個自動站上,盡可能的提高氣象數(shù)據(jù)整體收集能力,成為氣象自動站布局優(yōu)化問題。結合E-CARGO模型,將氣象數(shù)據(jù)描述為角色,氣象自動站描述為代理,投資組合描述為L矩陣,氣象數(shù)據(jù)與氣象自動站之間的關系則描述為代理與角色的關系,從而將其轉化為一個組角色分配問題。在E-CARGO中,一個代理只能同時扮演一個角色,即多對一的關系,不能解決多對多的關系。但是,氣象自動站可以同時測量多種氣象數(shù)據(jù),即一個代理可以同時扮演多個角色,是多對多的關系,如圖1所示。因此本文提出了基于主從角色的組角色分配方法,解決了多對多情況下組角色分配問題。

圖1　代理與角色的關系Fig.1　Relationship of agent and role

采用多對多情況下的組角色分配過程如下：首先,根據(jù)不同種類氣象數(shù)據(jù)收集設備的成本,將有限的資金分配給各種設備,形成需求矩陣L。例如,分別用r0，r1，r2,r3分別表示風速、風向、降雨量和氣溫4種氣象數(shù)據(jù),測量設備的成本分別為2.5，5，3，7(萬元)。在總成本為20萬元時,L=[2,1,1,1]表示一種投資組合,其中角色的個數(shù)表示每種氣象數(shù)據(jù)收集設備的個數(shù)；其次,在Q矩陣上對所有可能的L進行角色分配,得到分配結果,并求出評估值；最后,根據(jù)分配結果評估其對氣象數(shù)據(jù)收集準確率的影響,找出一個或者幾個結果較優(yōu)的投資組合,對自動站布局優(yōu)化提供參考。

3氣象自動站布局及其優(yōu)化算法

氣象自動站的布局優(yōu)化過程可以用多對多情況下的組角色分配過程來描述。為了形成GRA問題,本文用A表示代理集,R表示角色集,m表示代理的個數(shù),n表示角色的個數(shù),同時給出了下面的說明。

1) 角色范圍向量 L:表示為L[j](0≤j

2) Q矩陣:A×R→[0,1],Q[i,j]表示代理Ai扮演角色rj的能力。

3) 角色分配矩陣T:A×R→{0,1},如果T[i,j]=1,表示將角色rj分配給代理Ai;如果T[i,j]=0,則相反(0≤i

組角色分配問題即找到一個分配矩陣(T,max{α})

Subject to

在進行組角色分配前,我們將L矩陣拆分成Lm和LS,然后對Lm調用K-M算法。為了應用K-M算法,必須根據(jù)Lm矩陣將Q矩陣轉化為一個平方矩陣,朱海濱給出了一個轉換函數(shù)Transfer[13]。在此基礎上,給出了本文所使用的轉換函數(shù)MTransfer,主要在對Q矩陣進行轉換前,跟據(jù)L矩陣中角色個數(shù)是否為零,對Q矩陣進行預處理。例如L=[1,0,0,1],因為L[1]和L[2]的值都為零,所以將Q矩陣中所對應的列元素全部置為0,再調用Transfer函數(shù)。其次,對Lm調用K-M算法得到其分配矩陣Tk(k=0,…,n),根據(jù)Tk中元素值為1的位置將Q矩陣中的值置為0,從而避免二次分配。最后判斷LS矩陣中所有元素是否為0,若是,則將Tk相加,得到最終分配結果T,結束分配過程;否則,令L=LS,重復上述分配過程。

首先,給出本文所用轉換函數(shù)MTransfer:

算法1MTransfer

輸入:m,n,m×n矩陣Q,n維向量L

輸出:m×m平方矩陣M

Mtransfer(Q,L,m,n,M)

{for(j=0;j

Ltmp[j]=L[j];

for(i=0;i

for(j=0;j

{IF(Ltmp[j]==1)

Qtmp[i][j]=Q[i][j];

ELSE

Qtmp[i][j]=0;

}

Transfer(Qtmp,Ltmp,m,M);

}

在給出MTransfer函數(shù)之后,下面給出本文的組角色分配算法:

算法2組角色分配.

輸入:m,n,m×n矩陣Q,n維L向量

RatedAssign(L,Q,m,n,β)

{

Step1:將L向量中非零元素減1,得到LS,Lm=L-LS;

step2:M Transfer(Q,Lm,m,n,M);

Step3:K-M(M);

Step4:從step3結果得到分配矩陣Tk(0≤k

Step5:若LS元素不全為0,則轉到step1;

Step7:若T為成功分配,則計算

Step8:返回T與α;

}

此算法的時間復雜度為O(m3),m=max{m,n};其中:

O(m):step1 step5

O(m2):step2 step4 step6

O(1):step7

O(m3):step3

4仿真實驗及結果分析

本仿真實驗在主從角色概念的基礎上結合E-CARGO模型,并利用南方某氣象局氣象自動站現(xiàn)有布局和歷史氣象數(shù)據(jù)進行。仿真實驗所使用的硬件平臺為臺式機,處理器為英特i3-2130(3.4 GHz),內存4 GB。實驗開發(fā)環(huán)境為Windows 7與VC2010。

4.1仿真實驗方法及過程

窮舉法是解決組角色分配問題的一種傳統(tǒng)方法,并且是全局最優(yōu)算法,但是其指數(shù)級的時間復雜度很難在有限的時間內得出結果,難以用于解決規(guī)模較大的實際問題?；谥鲝慕巧峙浞椒ú皇侨肿顑?yōu),但是其在時間效率和準確率的綜合下有著很好的效果,因此適用于解決規(guī)模較大的實際問題。本實驗將與窮舉法進行對比,進行驗證。本文所提方法計算過程如下:

Step1: 輸入L、Q(m×n)矩陣

Step2：調用RatedAssign函數(shù)計算得出分配結果

Step3：記錄分配結果和時間消耗

窮舉法計算過程如下:

Step1: 輸入L、Q(m×n)矩陣

Step2：根據(jù)L中每列角色個數(shù)計算出分配方法數(shù)量

Step3: 遍歷所有組合，比較每種組合的評估值，得到評估值最大的一種組合即為分配結果。

Step4：記錄分配結果和時間消耗

4.2實驗結果及其分析

南方某氣象局目前共建設了19個氣象自動站,所需收集的氣象數(shù)據(jù)為48項,其中去除重復的時間數(shù)據(jù)項10項和一項缺省數(shù)據(jù)項,本實驗將角色種類m設為37,代理個數(shù)n設為19,L被隨機賦予1或者2,保證每個角色都有足夠的代理來執(zhí)行。由于窮舉法在問題規(guī)模較大時,分配一次所花費時間巨大,因此規(guī)定其分配一次所花費時間超過10 min,則表示其無法得到分配結果。實驗記錄了兩種方法分配一次的時間,其中,若窮舉法花費時間超過10 min,則記錄為10 min。

如圖2所示,窮舉法每次分配花費的時間均超過了10 min,而主從角色分配方法分配一次的平均時間遠小于窮舉法,僅為178.6 us。這說明本文所提方法在時間效率上遠優(yōu)于窮舉法,能夠解決自動站布局優(yōu)化問題。

圖2　組角色分配時間分布Fig.2　Distribution of assignment time for group role assignment

隨著m的增大，筆者所提方法分配一次消耗的時間增長緩慢，如圖3所示。由于實驗采用隨機生成Q矩陣的方法，值的分布會影響到每次分配所消耗的時間，導致m較小的組消耗的時間大于m較大的組，所以最大消耗時間的增長并不是線性的。最小消耗時間和平均消耗時間的增長慢于O(m3)，出現(xiàn)這種情況是因為K-M算法所使用的平方矩陣是根據(jù)Q矩陣產(chǎn)生的，可能出現(xiàn)多列被置為0的情況。因此，本方法所消耗的時間一般情況下要少于O(m3)。實驗結果表明，本文所提方法在時間效率上要優(yōu)于窮舉法，后者在m超過15時分配一次所消耗的時間超過數(shù)小時甚至數(shù)天[14]。

圖3　根據(jù)組規(guī)模的分配時間趨勢Fig.3　Trend lines for typical times for different sizes of the groups for group role assignment

圖4　準確率對比Fig.4　Comparison of accuracy rate

基于主從角色分配方法雖然在時間上優(yōu)于窮舉法,卻是次優(yōu)化方法。為了對比兩種方法的效果,本文選取了一組對比實驗,L隨機賦予1到n,n=m/2,每次實驗重復500次,分別用α1,α2表示窮舉法和主從角色分配方法得到的評估值,用α2/α1表示主從角色分配法的準確率。如圖4所示，本文所提方法的平均準確率穩(wěn)定在0.9,而最低準確率穩(wěn)定在0.8,最高準確率接近1,說明基于主從角色的分配方法能夠達到很高的準確率。

綜合上述實驗結果,筆者所提出方法應用于氣象自動站布局優(yōu)化問題,是正確、有效與可行的。雖然基于主從角色分配方法是次優(yōu)化方法,但其時間復雜度為O(m3),大大優(yōu)于窮舉法。而且,通過實驗證明在與窮舉法相比時,仍然具有很高的準確率。但隨著m的增大,窮舉法所花費時間急劇增大,不能夠在合理的時間范圍內得到分配結果,而本文所提方法在時間效率和準確率的綜合下,取得了很好的效果,適合解決規(guī)模較大的問題,能夠解決自動站布局優(yōu)化問題。

5結束語

基于仿真實驗,本文提出的角色分配方法得到了正確的角色分配結果,有效的解決了自動站布局優(yōu)化問題,提高了氣象數(shù)據(jù)收集的準確率。另外,本文在進行角色分配并使用α評價分配結果時,并未考慮氣象數(shù)據(jù)種類與氣象預測準確率之間的權重關系,這是下一步的研究工作。

參考文獻：

[1]沈軍,楊敏華.氣象自動站觀測站數(shù)據(jù)處理方法研究[D].長沙：中南大學,2011.

[2]ZHUHaibin.Collectivegrouproleassignmentanditscom-lexity[C]∥IEEE.ProceedingsoftheSystems,Man,andCybernetics.Alaska:[s.n.],2011:351-356.

[3]ZHUHaibin,ZHOUMengchu.Role-basedcollaborationanditskernelmechanisms[J].Systems,ManandCybernetics,partC:ApplicationsandReviews,2006,36(4):578-589.

[4]SHARMAA,MANORIAM.Aweatherforecastingsystemusingconceptofsoftcomputing:anewapproach[C]∥IEEE.ProceedingsoftheAdvancedComputingandCommunication.Salem,India:[s.n.],2006:353-356.

[5]GIllJ,SINGHB,SINGHS.Trainingbackpropagationonneuralnetworkswithgeneticalgorithmforweatherforecasting[C]∥ProceedingsoftheIntelligentSystemsandInformatics.Subotica,Yugoslavia:[s.n.],2010:465-469.

[6]ASADIS,SHAHRABIJ,ABBASZADEHP,etal.Anewhybridartifi-cialneuralnetworksforrainfall-runoffprocessmodeling[J].Neurocomputing,2013,121:470-480.

[7]JINLong,LINJianling,LINKaiping.Precipitationmodelingusingnetworkandempiricalorthogonalfunctionbasedonnumericalweatherforecastproduction[C]∥IEEE.ProceedingsoftheIntelligentControlandAutomation.Dalian:[s.n.],2006:2723-2727.

[8]滕少華,樊繼慧,張巍,等.基于KNN的多組合器協(xié)同挖掘局域氣象數(shù)據(jù)[J].廣東工業(yè)大學學報,2014,31(1):25-31.

[9]王小蕾,林捷.自動氣象站溫度傳感器的輻射誤差[J].解放軍理工大學學報,2006,7(4):405-408.

[10]LIJianming,HANLei,ZHENShuyong,etal.TheassessmentofautomaticweatherstationoperatingqualitybasedonfuzzyAHP[C]∥ProceedingsoftheMachinelearningandCybernetics.Qingdao,China,2010:1164-1168.

[11]HASUV,KOIVOH.Automaticrainandwindmeasurementfaultidentificationinmesoscaleweatherstationnetwork[C]∥IEEE.ProceedingsoftheInstrumentationandMeasurementTechnology.Victoria,BC,Canada：[s.n.],2008:489-494

[12]ZHUHaibin,ZHOUMengchu,ALKINR.GrouproleassignmentviaaKuhn-Munkresalgorithm-basedsolution[J].Systems,ManandCybernetics,partA:SystemsandHumans,2012,42(3):739-750.

[13]ZHUHaibin,ZHOUMengchu.EfficientroletransferbasedonKuhn-Munkersalgorithm[J].Systems,ManandCybernetics,partA:SystemsandHumans,2012,42(2):491-496.

[14]ZHUHaibin,ZHOUMengchu,ALKINSR.Grouproleassign-ment[C]∥IEEE.ProceedingsoftheACM/IEEEint’lSymposium,onCollaborativeTechnologyandSystems,Baltimore,USA:[s.n.],2009:431-439.

(編輯：賈麗紅)

Automatic Weather Station Layout and its Optimization Based on Master-slave Role Assignment

WEI Ding1,TENG Shaohua1,SONG Jingjing2,ZHU Haibin3

(1.SchoolofComputerScienceandTechnology,GuangdongUniversityofTechnology,Guangzhou510006,China;2.DepartmentofComputerTechnology,AuditOfficeofGuangdongProvince,Guangzhou510000,China;3.DepartmentofComputerScience,NipissingUniversity,Ontario,Canada)

Abstract:The key to weather forecast is to improve the accuracy of the meteorological data collection.Although we can increase the amount of meteorological data collection equipment and the number of collection points, we are unable to improve the accuracy of the meteorological data collection.Under cost-constrained condition, this paper improved the accuracy of the meteorological data collection by optimizing the layout of automatic weather station. Based on the existing automatic weather station layout and historical weather data of a southern meteorological bureau,the E-CARGO model was used to model and optimize the layout of automatic weather station and convert the problem to a GRA problem. Because an automatic weather station as an agent can play multiple roles at the same time,a revised GRA method based on master-slave role assignment was proposed to solve the group role assignment problem and optimize the layout of automatic weather stations.The data for the simulation experiment come from the existing automatic weather station layout and historical meteorological data of a southern meteorological bureau. The results of the experiments indicate that the proposed method is effective, valid and feasible. This study may provide references for automatic weather station layout optimization of meteorological bureau.

Key words:master-slave role;E-CARGO;automatic weather station;GRA;weather forecast

文章編號:1007-9432(2016)02-0233-06

*收稿日期：2015-05-30

基金項目：國家自然科學基金資助項目：RBAC授權決策支持模式研究(61104156)

作者簡介：魏叮(1989-)，男，安徽宿州人，碩士生，主要研究領域為基于角色的協(xié)同，(E-mail)betterboy3@163.com通訊作者：滕少華，博士，教授，主要研究領域為數(shù)據(jù)挖掘、信息安全與協(xié)同計算，(E-mail)shteng@gdut.edu.cn

中圖分類號:TP311

文獻標識碼:A

DOI：10.16355/j.cnki.issn1007-9432tyut.2016.02.021