基于主从角色分配的气象自动站布局及其优化

魏　叮,滕少华,宋静静,朱海滨

(1.广东工业大学 计算机学院,广州 510006;2.广东省审计厅 计算机中心,广州 510000;3.尼普森大学 计算机系,安大略省 诺斯贝 加拿大)



基于主从角色分配的气象自动站布局及其优化

魏叮1,滕少华1,宋静静2,朱海滨3

(1.广东工业大学 计算机学院,广州 510006;2.广东省审计厅 计算机中心,广州 510000;3.尼普森大学 计算机系,安大略省 诺斯贝 加拿大)

摘要:在成本受限的情况下,通过优化气象自动站布局,提高气象数据收集的准确率。针对自动站作为代理可以同时扮演多个角色,提出了基于主从角色分配的GRA方法,解决多对多情况下组角色分配问题,从而优化气象自动站布局。结合南方某气象局属下气象自动站现有布局和历史数据,并通过仿真实验验证了本方法的可行性,不仅提高了气象数据收集准确率,同时削减了成本。本文的研究可为气象局优化气象自动站布局提供参考。

关键词:主从角色;E-CARGO;气象自动站;GRA;气象预测

气象预测与人们的生产生活息息相关,对人们的生命财产安全以及经济活动至关重要,而提高气象数据收集的准确率是提高气象预测准确率的关键。地面气象预测是实现天气系统监测的重要手段,是气象预报与气候分析以及灾害监测的重要途径和数据基础。气象自动站将无线传感器和传统的面气象观测系统相结合,实现了全天候的实时观测,克服了传统人工观测频率低、空间分辨率低、数据误差不确定等许多缺点,成为地面气象观测新的数据基础[1]。然而气象自动站建设成本较高,在成本有限的情况下,很难通过单一的建设新的气象自动站或者增加气象数据采集设备来提高气象数据收集的准确率。因此,笔者希望通过优化气象自动站的布局,提高气象数据收集的准确率。在气象自动站布局优化问题中,将资金分配到各个气象自动站进行设备的更新与维护以提高整体收集气象数据的准确率是一个协同的过程，而且气象数据与气象自动站的关系也可以用角色与代理的关系来描述。因此,本文使用基于角色协同的E-CARGO模型来对气象自动站布局优化问题进行建模。

E-CARGO[2-3]模型是朱海滨教授在RBC系统的基础上,基于角色协同所提出。RBC(role-based collaboration)系统是一种计算思维方法论,主要通过角色作为底层的机制来帮助抽象、分类。结合E-CARGO模型,将气象自动站与气象数据之间的关系描述为角色与代理的关系,从而将气象自动站布局优化问题转化为一个GRA问题来解决。由于一个气象自动站可以安装多种气象数据采集设备,在同一时刻可以测量多种气象数据,因此,气象自动站与气象数据是多对多的关系,即一个代理可以扮演多个角色,一个角色也可以由多个代理扮演。基于此,笔者提出了基于主从角色的分配方法,用于解决多对多情况下的GRA问题,从而解决气象自动站布局优化问题。

1相关工作

目前,关于气象预测已经进行了大量的研究,并且产生了很多研究成果[4-6]。近几年,主流的研究方法主要基于收集到的气象数据,通过应用人工智能算法、数据挖掘算法等来尽可能的提高气象预测的准确率。例如,JIN et al[7]基于数值天气预报产品,将人工神经网络和遗传算法相结合,提出了一种新的预测方法,并且在中国广西省3个不同的地方分别建立了3个人工神经网络预测模型。经过实验结果表明,文章中所提出的新的预测模型在这三个地方的预测结果都要优于中国气象台的T213模型和日本的NWF模型。此外,滕少华和樊继慧[8]研究了基于KNN的多组合器对气象数据的分析,通过构造多个组合器对局域区域的气象数据进行分析,针对局部地区的降雨情况,获得了较好的分类结果,并且通过对数据的预处理,筛选出了对降雨量有明显影响的气象数据属性,也为本文对气象自动站布局优化时角色的设计提供了参考。同时,气象自动站作为收集地面气象数据的平台,也受到众多科研人员的关注[9-10]。气象自动站高频率的观测数据由于受到观测地面环境的局部影响以及观测仪器的固有缺陷,不免受到噪声的干扰。HASU，KOIVO[11]通过对中尺度气象自动站网络中雨和风的测量错误分析,提出了几种自动对雨和风进行测量错误分析的算法,对其进行修正。通过实验表明,该算法有着很好的降噪效果,提高了气象自动站测量数据的准确率。

2气象自动站布局优化建模

2.1基于主从角色的组角色分配

GRAP(Group Role Assignment Problem)是一个复杂的问题,基于遍历搜索的算法拥有指数级时间复杂度,很难用于解决m较大的情况。在RBC系统中,代理扮演角色有平行模式和顺序模式。平行模式意味着一个代理可在同一时刻扮演两个或者更多的角色;顺序模式表示一个代理在同一时刻只能扮演一个角色。在顺序模式下,朱海滨教授提出了一种基于K-M算法的组角色分配方法,通过复制角色,调整角色和代理的个数,将GRAP转化为一个GAP,解决了顺序模式下的组角色分配问题。在平行模式下,一个类似的解决GRAP问题的方法是复制代理,但复制代理却会导致Q矩阵急剧膨胀。为了避免复制代理,笔者提出了主从角色的概念。

定义1主角色表示需要被代理重点扮演的角色,主角色有且只有一个。在气象自动站优化问题中则表示作为主角色的气象数据需要被某个代理重点测量。

定义2从角色表示代理次要扮演的角色,其个数大于等于零。同样,在自动站优化问题中表示需要被某个代理辅助测量。

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

在这里通过一个简单的例子来说明组角色的分配过程。Q矩阵表示代理扮演角色的能力,是进行角色分配的依据,是随机产生的：

首先,对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气象自动站布局优化问题分析

气象自动站分布在不同的地理位置上,受地理环境的影响,造成自动站测量气象数据的能力也不尽相同。在成本受限时,如何将资金投资到各个自动站上,尽可能的提高气象数据整体收集能力,成为气象自动站布局优化问题。结合E-CARGO模型,将气象数据描述为角色,气象自动站描述为代理,投资组合描述为L矩阵,气象数据与气象自动站之间的关系则描述为代理与角色的关系,从而将其转化为一个组角色分配问题。在E-CARGO中,一个代理只能同时扮演一个角色,即多对一的关系,不能解决多对多的关系。但是,气象自动站可以同时测量多种气象数据,即一个代理可以同时扮演多个角色,是多对多的关系,如图1所示。因此本文提出了基于主从角色的组角色分配方法,解决了多对多情况下组角色分配问题。

图1　代理与角色的关系Fig.1　Relationship of agent and role

采用多对多情况下的组角色分配过程如下：首先,根据不同种类气象数据收集设备的成本,将有限的资金分配给各种设备,形成需求矩阵L。例如,分别用r0，r1，r2,r3分别表示风速、风向、降雨量和气温4种气象数据,测量设备的成本分别为2.5，5，3，7(万元)。在总成本为20万元时,L=[2,1,1,1]表示一种投资组合,其中角色的个数表示每种气象数据收集设备的个数；其次,在Q矩阵上对所有可能的L进行角色分配,得到分配结果,并求出评估值；最后,根据分配结果评估其对气象数据收集准确率的影响,找出一个或者几个结果较优的投资组合,对自动站布局优化提供参考。

3气象自动站布局及其优化算法

气象自动站的布局优化过程可以用多对多情况下的组角色分配过程来描述。为了形成GRA问题,本文用A表示代理集,R表示角色集,m表示代理的个数,n表示角色的个数,同时给出了下面的说明。

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算法,必须根据Lm矩阵将Q矩阵转化为一个平方矩阵,朱海滨给出了一个转换函数Transfer[13]。在此基础上,给出了本文所使用的转换函数MTransfer,主要在对Q矩阵进行转换前,跟据L矩阵中角色个数是否为零,对Q矩阵进行预处理。例如L=[1,0,0,1],因为L[1]和L[2]的值都为零,所以将Q矩阵中所对应的列元素全部置为0,再调用Transfer函数。其次,对Lm调用K-M算法得到其分配矩阵Tk(k=0,…,n),根据Tk中元素值为1的位置将Q矩阵中的值置为0,从而避免二次分配。最后判断LS矩阵中所有元素是否为0,若是,则将Tk相加,得到最终分配结果T,结束分配过程;否则,令L=LS,重复上述分配过程。

首先,给出本文所用转换函数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函数之后,下面给出本文的组角色分配算法:

算法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模型,并利用南方某气象局气象自动站现有布局和历史气象数据进行。仿真实验所使用的硬件平台为台式机,处理器为英特i3-2130(3.4 GHz),内存4 GB。实验开发环境为Windows 7与VC2010。

4.1仿真实验方法及过程

穷举法是解决组角色分配问题的一种传统方法,并且是全局最优算法,但是其指数级的时间复杂度很难在有限的时间内得出结果,难以用于解决规模较大的实际问题。基于主从角色分配方法不是全局最优,但是其在时间效率和准确率的综合下有着很好的效果,因此适用于解决规模较大的实际问题。本实验将与穷举法进行对比,进行验证。本文所提方法计算过程如下:

Step1: 输入L、Q(m×n)矩阵

Step2：调用RatedAssign函数计算得出分配结果

Step3：记录分配结果和时间消耗

穷举法计算过程如下:

Step1: 输入L、Q(m×n)矩阵

Step2：根据L中每列角色个数计算出分配方法数量

Step3: 遍历所有组合，比较每种组合的评估值，得到评估值最大的一种组合即为分配结果。

Step4：记录分配结果和时间消耗

4.2实验结果及其分析

南方某气象局目前共建设了19个气象自动站,所需收集的气象数据为48项,其中去除重复的时间数据项10项和一项缺省数据项,本实验将角色种类m设为37,代理个数n设为19,L被随机赋予1或者2,保证每个角色都有足够的代理来执行。由于穷举法在问题规模较大时,分配一次所花费时间巨大,因此规定其分配一次所花费时间超过10 min,则表示其无法得到分配结果。实验记录了两种方法分配一次的时间,其中,若穷举法花费时间超过10 min,则记录为10 min。

如图2所示,穷举法每次分配花费的时间均超过了10 min,而主从角色分配方法分配一次的平均时间远小于穷举法,仅为178.6 us。这说明本文所提方法在时间效率上远优于穷举法,能够解决自动站布局优化问题。

图2　组角色分配时间分布Fig.2　Distribution of assignment time for group role assignment

随着m的增大，笔者所提方法分配一次消耗的时间增长缓慢，如图3所示。由于实验采用随机生成Q矩阵的方法，值的分布会影响到每次分配所消耗的时间，导致m较小的组消耗的时间大于m较大的组，所以最大消耗时间的增长并不是线性的。最小消耗时间和平均消耗时间的增长慢于O(m3)，出现这种情况是因为K-M算法所使用的平方矩阵是根据Q矩阵产生的，可能出现多列被置为0的情况。因此，本方法所消耗的时间一般情况下要少于O(m3)。实验结果表明，本文所提方法在时间效率上要优于穷举法，后者在m超过15时分配一次所消耗的时间超过数小时甚至数天[14]。

图3　根据组规模的分配时间趋势Fig.3　Trend lines for typical times for different sizes of the groups for group role assignment

图4　准确率对比Fig.4　Comparison of accuracy rate

基于主从角色分配方法虽然在时间上优于穷举法,却是次优化方法。为了对比两种方法的效果,本文选取了一组对比实验,L随机赋予1到n,n=m/2,每次实验重复500次,分别用α1,α2表示穷举法和主从角色分配方法得到的评估值,用α2/α1表示主从角色分配法的准确率。如图4所示，本文所提方法的平均准确率稳定在0.9,而最低准确率稳定在0.8,最高准确率接近1,说明基于主从角色的分配方法能够达到很高的准确率。

综合上述实验结果,笔者所提出方法应用于气象自动站布局优化问题,是正确、有效与可行的。虽然基于主从角色分配方法是次优化方法,但其时间复杂度为O(m3),大大优于穷举法。而且,通过实验证明在与穷举法相比时,仍然具有很高的准确率。但随着m的增大,穷举法所花费时间急剧增大,不能够在合理的时间范围内得到分配结果,而本文所提方法在时间效率和准确率的综合下,取得了很好的效果,适合解决规模较大的问题,能够解决自动站布局优化问题。

5结束语

基于仿真实验,本文提出的角色分配方法得到了正确的角色分配结果,有效的解决了自动站布局优化问题,提高了气象数据收集的准确率。另外,本文在进行角色分配并使用α评价分配结果时,并未考虑气象数据种类与气象预测准确率之间的权重关系,这是下一步的研究工作。

参考文献：

[1]沈军,杨敏华.气象自动站观测站数据处理方法研究[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的多组合器协同挖掘局域气象数据[J].广东工业大学学报,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-)，男，安徽宿州人，硕士生，主要研究领域为基于角色的协同，(E-mail)betterboy3@163.com通讯作者：滕少华，博士，教授，主要研究领域为数据挖掘、信息安全与协同计算，(E-mail)shteng@gdut.edu.cn

中图分类号:TP311

文献标识码:A

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