基于模糊c-均值(FCM)聚类算法的给水管网压力监测点优化布置

林英姿 刘 览 刘思宏 吕尊敬

(吉林建筑大学 市政与环境工程学院,长春 130118)

0 引言

在城市给水管网系统中,作为全面掌握给水管网运行状态以及正确调度给水系统的重要参数[1-2],且是直接反映城市供水服务质量指标之一的水压,在对其进行布置压力监测装置时,要求监测装置监测到的压力能够反映节点流量变化,便于监控管网漏失和爆管事故.随着模糊聚类理论完善和发展,越来越多的被运用到给水管网压力监测点优化布置当中去[3-5].把压力监测点的聚类分析转化成一个带约束的非线性规划问题,通过基于目标函数聚类算法对其优化求解,得到数据集的最优模糊划分和聚类中心,可使压力监测点的布置较为均匀且具有代表性.

基于上述所说,本文利用FCM聚类算法进行城市给水管网压力监测点优化布置,得出一种较为完整的城市给水管网压力监测点优化选址的方法.

1 FCM聚类算法

1969年,Ruspini系统的提出了关于数据集模糊划分概念的模糊聚类算法后[6],Zadeh[7]和Tarmura[8]学者也相继提出基于相似关系和模糊关系的聚类方法.在模糊聚类研究方面,随着与各类群智能算法、图论等技术进行交叉融合,学者们陆续提出了许多种方法[9-11].在其中运用最广、设计简单、参数较少的是基于目标函数的聚类算法,而在此类聚类算法中比较典型[12-13]的为模糊C-均值聚类法(FCM).1974年,Dunn首次提出FCM模糊聚类算法[14],Bezdek则在1981年进一步完善了该算法[15].随着FCM算法的不断完善,该算法在各个领域被广泛应用,列如国外学者Kannan的基于FCM算法的图像医学分割[16],我国的杨浩把FCM算法应用于电力负荷分析研究[17]等.

设待聚类分析的样本集有n个元素为X={X1,X2,X3,…,Xn},每个样本Xk(k=1,2,…,n)都有s个特性Xk=(Xk1,Xk2,…,Xks),称为Xk的模式矢量,相对应的为特征空间的一点.若将样本集X划分为c个类别,那么c个类别中拥有全部的n个样本,且引入模糊划分矩阵U=[μik]c×n(也称为隶属度矩阵).

其中，μik(1≤i≤c,1≤k≤n)为第k个样本Xk的第i个类别的隶属度,Bezdek把模糊c均值模糊聚类算法描述为:

(1)

约束条件:

m∈[1，∞)

0≤μik≤1,1≤i≤c,1≤k≤n

式中,U为模糊划分矩阵U=[μik]c×n,μik∈[0,1],U中每个元素代表隶属度;P为聚类中心矩阵P=(p1,p2,…,pc),pi(i=1,2,…,c),为第i类的聚类中心;m为模糊加权指数,通常取m=2;dik为样本Xk与第i类的聚类中心pi之间的欧式距离;

FCM算法就是最小化优化解目标函数Jm(X,U,P)的过程,因为矩阵U中各列都是独立的,因此:

(2)

上式极值用拉格朗日乘数法来求解:

(3)

若样本集X、聚类类别c和模糊权重值m都已知,运用迭代算法对min{Jm(U,P)}求解出最佳模糊分类矩阵U和聚类中心P:

(4)

(5)

(6)

2 FCM聚类算法应用于管网压力监测点优化布置

当实际的给水管网处于某供水工况并正常工作时,管网各个节点的水压值会受到许多不同因素的影响,其中最敏感的外界影响因素为管网节点流量.当某个节点流量发生变化时,各个管网节点水压必然发生变化,但节点流量变化时对各个节点水压的影响程度是各不相同的.在对城市管网系统进行压力监测点优化布置时,应首先建立城市管网水力模型,并对模型进行校正.聚类对象为给水管网中的节点,对象特性为各个节点压力所对应的节点流量的变化程度,利用FCM聚类算法对管网节点进行聚类分析,求出给水管网压力监测点.

在FCM聚类算法参数中,管网有n个节点,在j节点处节点流量Q增加一微小节点变化流量ΔQj,则整个给水管网的各个节点压力都会受到不同程度的影响,ΔHi则表示为被考察节点i处的水压变化值,且j节点自身受ΔQj影响最大,j节点水压变化值为ΔHj.i节点处利用ΔHi/ΔQj表示为单位节点流量变化产生的节点水压变化率,即i节点水压受其它节点流量变化影响的大小.但给水管网各个节点流量大小相差悬殊,则各个ΔQj在各个Qj中所占的比例不同,所以各个节点水压变化值ΔHi相差很大.基于此ΔHi/ΔQj可比性较差,固而选用ΔHi/ΔHj表示.即用ΔHi/ΔHj表示j节点流量变化对i节点水压的影响程度,为了利于编程则记为,X(i,j)=ΔHi/ΔHj,且对ΔHi和ΔHj取微分:

(7)

式中,X(i,j)为j节点对i的影响系数.

直接对管网进行微观分析,简化上式来求得X(i,j).在莫工况下进行管网水力计算,求出该工况下的各个节点的压力Hi,然后在j节点上增加微小流量ΔQj,其余节点流量不变,再对管网进行水力计算,求出各个节点压力Hi′.其影响系数可表示:

(8)

式中,Hi,Hj为在基准工况下i,j的节点水压;Hi′,Hj′为在i节点流量改变后i,j的节点水压.

所有的节点影响系数X(i,j)用影响系数矩阵[X]n×n阵来表示, 且该矩阵的对角线上的元素X(i,k)=1,其余元素0

FCM聚类法应用于管网压力监测点优化布置步骤:

(1) 求出影响系数矩阵. 在基准工况下,调用Epanet进行水力计算,求出各个节点水压,然后根据上述在j节点上按一定比例增加节点流量ΔQj,其余条件不变,再次进行调用Epanet进行水力计算,根据上述公式(8)求出节点水压影响系数矩阵.

(2) FCM算法初始化. 依据FCM聚类法,n为给水管网管段数目,且权重设定为m通常取2,迭代停止阀值ε,开始时设定聚类类别c(2≤c≤n),当迭代计数器b=0,初始化聚类中心矩阵P0=[p10,p20,…,pc0],不同的聚类类别数c相对应不同的聚类中心和模糊分类矩阵.第k管段对第i类别的隶属度由模糊划分矩阵U=[μik]c×n中μik的值来表示.该类的代表节点为每行中数值最大的μik对应的节点.基于此就可得到每一类划分中的代表节点.

(3) 计算欧式距离dij. 本文距离测度采用欧式距离,利用式(6)分别计算样本xj到Pi(b)的欧式距离.

(4) 根据公式(4)计算μik(b).

(5) 根据公式(5)计算Pi(b+1).

(6) 若条件满足‖P(b)-P(b+1)‖<ε,则算法停止迭代并输出模糊划分矩阵U和聚类中心P,若不满足以上条件,则令b=b+1,返回步骤(3)继续进行计算.

(7) 根据输出的模糊划分矩阵U和聚类中心P得出聚类方案和每一类的代表节点.

(8) 最后判断聚类类别c是否划分合理,需要注意聚类中心是否相互距离之间离的太近,各类别之间差异性是否明显,并借鉴压力监测点布置经验法,若聚类合理,则输出最佳聚类类别c,聚类方案和每一类中的代表节点.若不合理,则转到步骤(2),重新设置c值,并调用Epanet且根据公式进行计算,直到满足迭代停止条件,输出最优的节点模糊c划分以及代表节点.

3 工程实例

表1为J市管网基准工况下节点流量表,不考虑两水源节点,对其中编号1～56的节点进行聚类分析,找出代表性的节点.

表1 基准工况下节点流量Table 1 Node traffic under baseline conditions (L·s-1)

具体计算为:首先计算基准工况下节点压力,然后依次在各个节点增加节点流量ΔQj=10%×Qj,然后调用Epanet进行水力计算,根据公式(8)进行计算求出影响系数矩阵.求出的影响系数矩阵为[X]56×56,对角线上元素X(i,k)=1,其余元素0

表2是由公式(4)求得的模糊划分矩阵U=[μik]6×56,表3为公式(5)求解出的聚类中心矩阵P,表4为将节点聚类划分c=6类的情况下得到节点分类.

表2 模糊划分矩阵UTable 2 Fuzzy partition matrix U

表3 聚类中心矩阵PTable 3 Cluster center matrix P

表4 c=6时的节点分类Table 4 Node classification at c=6

在c=6时,每个分类中的节点中隶属度最大的最具代表性的节点且隶属度见表5.

表5 c=6时代表性节点及隶属度Table 5 Representative node and membership degree at c=6

用上述计算欧式距离公式计算当c=6时,各个节点到6个聚类中心的距离,表6为到各类聚类中心的最小欧式距离的节点.

表6 c=6时代表性节点及欧式距离Table 6 Representative node and euclidean distance at c=6

当c=6时,经过模糊分类矩阵,由隶属度最大而划分的代表节点:43,49,17,19,29,11,而由聚类中心的最小欧式距离求得的代表节点:43,49,21,19,29,11,可以看出得到的代表节点大致一致,17节点和21节点的欧式距离分别为0.229 4和0.225 2相差几乎为零.由上述结果推出,当聚类分类c=6时,由FCM聚类算法求得的监测点效果较为理想且分布比较均匀.某市管网压力监测点布置示意图见图1.

图1 J市管网压力监测点布置示意图Fig.1 Schematic diagram of J city pipe network pressure monitoring point layout

4 结语

本文通过FCM聚类算法,以影响系数矩阵为基础,进行J市给水管网压力监测点的优化布置,经过FCM聚类法最优求解得出的压力监测点在城市管网分布中比较有代表性且较均匀,能够较好地反映节点流量变化情况,据此实时监测某市给水管网爆管、漏水等事故的发生.在实际操作中,还应该结合人工经验及现场条件等进行布置,使压力监测点更具代表性和实际性.